For teachers / Printable sets /Stage 6 · Combinatorics

Stage 6 · Combinatorics

10 problems · National olympiad, first round · mathsolympiadprep.com

The answer key prints on its own page at the end.

$(\mathbf{C Z S} 1)^{\mathrm{IMO} 2}$ On a circle, $2 n-1(n \geq 3)$ different points are given. Find the minimal natural number $N$ with the property that whenever $N$ of the given points are colored black, there exist two black points such that the interior of one of the corresponding arcs contains exactly $n$ of the given $2 n-1$ points.

Combinatorics Solution and answer checking →
Let $n$ be an integer with $n \geqslant 2$ . On a slope of a mountain, $n^{2}$ checkpoints are marked, numbered from 1 to $n^{2}$ from the bottom to the top. Each of two cable car companies, $A$ and $B$ , operates $k$ cable cars numbered from 1 to $k$ ; each cable car provides a transfer from some checkpoint to a higher one. For each company, and for any $i$ and $j$ with $1 \leqslant i<j \leqslant k$ , the starting point of car $j$ is higher than the starting point of car $i$ ; similarly, the finishing point of car $j$ is higher than the finishing point of car $i$ . Say that two checkpoints are linked by some company if one can start from the lower checkpoint and reach the higher one by using one or more cars of that company (no movement on foot is allowed). Determine the smallest $k$ for which one can guarantee that there are two checkpoints that are linked by each of the two companies. (India) Answer: $k=n^{2}-n+1$ .

Combinatorics Solution and answer checking →
A calendar is a (finite) rectangular grid. A calendar is valid if it satisfies the following conditions:
(i) Each square of the calendar is colored white or red, and there are exactly 10 red squares.
(ii) Suppose that there are $N$ columns of squares in the calendar. Then if we fill in the numbers $1,2,\ldots$ from the top row to the bottom row, and within each row from left to right, there do not exist $N$ consecutive numbers such that the squares they are in are all white.
(iii) Suppose that there are $M$ rows of squares in the calendar. Then if we fill in the numbers $1,2,\ldots$ from the left-most column to the right-most column, and within each column from bottom to top, there do not exist $M$ consecutive numbers such that the squares they are in are all white. In other words, if we rotate the calendar clockwise by $90^{\circ}$ , the resulting calendar still satisfies (ii).
How many different kinds of valid calendars are there?
(Remark: During the actual exam, the contestants were confused about what counts as different calendars. So although this was not in the actual exam, I would like to specify that two calendars are considered different if they have different side lengths or if the $10$ red squares are at different locations.)

Combinatorics Solution and answer checking →
Bread draws a circle. He then selects four random distinct points on the circumference of the circle to form a convex quadrilateral. Kwu comes by and randomly chooses another 3 distinct points (none of which are the same as Bread's four points) on the circle to form a triangle. Find the probability that Kwu's triangle does not intersect Bread's quadrilateral, where two polygons intersect if they have at least one pair of sides intersecting.
Proposed by Nathan Cho

Combinatorics Solution and answer checking →
A pack of $2008$ cards, numbered from $1$ to $2008$ , is shuffled in order to play a game in which each move has two steps:
(i) the top card is placed at the bottom;
(ii) the new top card is removed.
It turns out that the cards are removed in the order $1,2,\dots,2008$ . Which card was at the top before the game started?

Combinatorics Solution and answer checking →
There are $n$ students in a class, and some pairs of these students are friends. Among any six students, there are two of them that are not friends, and for any pair of students that are not friends there is a student among the remaining four that is friends with both of them. Find the maximum value of $n$ .

Combinatorics Solution and answer checking →
Tom is searching for the $6$ books he needs in a random pile of $30$ books. What is the expected number of books must he examine before finding all $6$ books he needs?

Combinatorics Solution and answer checking →
p1. Give a fake proof that $0 = 1$ on the back of this page. The most convincing answer to this question at this test site will receive a point.
p2. It is often said that once you assume something false, anything can be derived from it. You may assume for this question that $0 = 1$ , but you can only use other statements if they are generally accepted as true or if your prove them from this assumption and other generally acceptable mathematical statements. With this in mind, on the back of this page prove that every number is the same number.
p3. Suppose you write out all integers between $1$ and $1000$ inclusive. (The list would look something like $1$ , $2$ , $3$ , $...$ , $10$ , $11$ , $...$ , $999$ , $1000$ .) Which digit occurs least frequently?
p4. Pick a real number between $0$ and $1$ inclusive. If your response is $r$ and the standard deviation of all responses at this site to this question is $\sigma$ , you will receive $r(1 - (r - \sigma)^2)$ points.
p5. Find the sum of all possible values of $x$ that satisfy $243^{x+1} = 81^{x^2+2x}$ .
p6. How many times during the day are the hour and minute hands of a clock aligned?
p7. A group of $N + 1$ students are at a math competition. All of them are wearing a single hat on their head. $N$ of the hats are red; one is blue. Anyone wearing a red hat can steal the blue hat, but in the process that person’s red hat disappears. In fact, someone can only steal the blue hat if they are wearing a red hat. After stealing it, they would wear the blue hat. Everyone prefers the blue hat over a red hat, but they would rather have a red hat than no hat at all. Assuming that everyone is perfectly rational, find the largest prime $N$ such that nobody will ever steal the blue hat.
p8. On the back of this page, prove there is no function f $(x)$ for which there exists a (finite degree) polynomial $p(x)$ such that $f(x) = p(x)(x + 3) + 8$ and $f(3x) = 2f(x)$ .
p9. Given a cyclic quadrilateral $YALE$ with $Y A = 2$ , $AL = 10$ , $LE = 11$ , $EY = 5$ , what is the area of $YALE$ ?
p10. About how many pencils are made in the U.S. every year? If your answer to this question is $p$ , and our (good) estimate is $\rho$ , then you will receive $\max(0, 1 -\frac 12 | \log_{10}(p) - \log_{10}(\rho)|)$ points.
p11. The largest prime factor of $520, 302, 325$ has $5$ digits. What is this prime factor?
p12. The previous question was on the individual round from last year. It was one of the least frequently correctly answered questions. The first step to solving the problem and spotting the pattern is to divide $520, 302, 325$ by an appropriate integer. Unfortunately, when solving the problem many people divide it by $n$ instead, and then they fail to see the pattern. What is $n$ ?
PS. You should use hide for answers. Collected here.

Combinatorics Solution and answer checking →
Determine all triplets $(a,b,c)$ of real numbers such that sets $\{a^2-4c, b^2-2a, c^2-2b \}$ and $\{a-c,b-4c,a+b\}$ are equal and $2a+2b+6=5c$ . In every set all elements are pairwise distinct

Combinatorics Solution and answer checking →
For each positive integer $n$ , let $f(n)$ denote the smallest possible value of $|A_1 \cup A_2 \cup \dots \cup A_n|$ where $A_1, A_2, A_3 \dots A_n$ are sets such that $A_i \not\subseteq A_j$ and $|A_i| \neq |A_j|$ whenever $i \neq j$ . Determine $f(n)$ for each positive integer $n$ .

Combinatorics Solution and answer checking →

Answer key — Stage 6 · Combinatorics

Worked solutions for every problem are on the site, one page per problem.

$N=n \text{ for } 3 \nmid 2 n-1 \text{ and } N=n-1 \text{ for } 3 \mid 2 n-1$ open
$k=n^{2}-n+1$ open
$10!$ open
$\frac{1}{5}$ open
$1883$ open
$25$ open
$14.7$ open
$-\frac{3}{4}$ open
$(1, 1, 2)$ open
$f(n) = n+2$ open

Problems belong to the competitions that set them and are reproduced from open datasets under their licences; every problem page names its source. Free to copy for classroom use.