#12 Mock Olympiads I

There are \(5\) choices for the hundreds digit, \(4\) for the tens digit, and \(3\) for the units digit. Total: \(5\cdot4\cdot3=60\).

There are \(12\) months and \(13\) people. By the pigeonhole principle, two people fall in the same month.

The number of heads changes by \(-2\), \(0\), or \(2\), so its parity is invariant. It starts at \(9\) and would need to become \(0\). Odd cannot become even, so it is impossible.

The degree sum is \(10\), so the number of edges is \(10/2=5\).

Need \(3\) right moves and \(2\) up moves. Choose positions for the \(2\) up moves: \(\binom{5}{2}=10\).

In chessboard coloring, opposite corners have the same color. After removing them, the color counts are unequal. Each domino covers one cell of each color, so no tiling exists.

\(22\equiv2\pmod4\). The first player takes \(2\) stones and leaves \(20\). Then the first player complements the opponent’s move to \(4\).

The number of games equals the number of pairs of players: \(\binom{7}{2}=21\).

Counting by students gives \(15\cdot2=30\) pairs. If there are \(k\) clubs, counting by clubs gives \(5k\). Thus \(5k=30\), so \(k=6\).

With \(a_0=1\), \(a_1=2\), we get \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\).

There are \(8\) residues modulo \(8\), and \(9\) numbers. By pigeonhole, two numbers have the same residue.

The minimum is \(12-1=11\). It is achieved by a path on \(12\) vertices.

Let \(S_k=a_1+\cdots+a_k\). If some \(S_k\) is divisible by \(8\), done. Otherwise the \(8\) partial sums have only \(7\) nonzero residues, so two have the same residue. Their difference is the sum of a consecutive block and is divisible by \(8\).

For \(a_n\), \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=1\). The values give \(a_7=21\).

The first player adds \(1\). Then after an opponent move \(a\), the first adds \(7-a\). After the first player’s moves the totals are \(1,8,15,\ldots,50\), so the first wins.

Possible acquaintance numbers are from \(0\) to \(9\), but \(0\) and \(9\) are incompatible. Thus there are at most \(9\) different values for \(10\) people. By pigeonhole, two degrees are equal.

Under coloring by \(i+j\pmod3\), each tromino covers all three colors. On a \(5\times5\) board the counts are \(9,8,8\), and after removing \((1,1)\) they do not become equal. Hence no tiling exists.

Both changes are divisible by \(3\), so the residue modulo \(3\) is invariant. \(5\equiv2\pmod3\), while \(100\equiv1\pmod3\). Impossible.

The first player takes \(6\) stones from the pile \(21\), leaving two piles of \(15\). Then the first player copies the opponent’s move in the other pile. This strategy gives the first player the last move.

The endpoints of a longest simple path cannot have additional neighbors: otherwise the path could be extended or a cycle would appear. Hence both endpoints have degree \(1\).

Choose a vertex \(v\) and \(5\) of its neighbors. If two neighbors are adjacent, they form a triangle with \(v\). If no two of them are adjacent, then each of these neighbors is adjacent to \(v\) and to at most the three remaining vertices, so its degree is at most \(4\), contradiction.

Every straight tetromino covers one cell of each of the four colors \(i+j\pmod4\). On the full board each color occurs \(16\) times, and the corners have colors \(2,1,1,0\). After removal the counts are \(15,14,15,16\), not equal. Hence no tiling exists.

There are \(\binom{8}{4}=70\) paths total. Bad paths that first go above the diagonal reflect to paths from \((-1,1)\) to \((4,4)\), of which there are \(\binom{8}{3}=56\). Therefore the number of good paths is \(70-56=14\).

Choose a person \(A\). Among the other \(5\), there are either \(3\) who know \(A\), or \(3\) who do not know \(A\). Suppose \(A\) knows \(B,C,D\). If among \(B,C,D\) there is an acquaintance pair, together with \(A\) we get three mutual acquaintances; if not, then \(B,C,D\) are mutual strangers. The case of three people not acquainted with \(A\) is analogous.