#11 Mixed Problems I

The last digit must be \(2\) or \(4\): \(2\) choices. Then the hundreds digit has \(4\) choices and the tens digit has \(3\). Total: \(2\cdot4\cdot3=24\).

One can take \(4\) socks of all different colors. The next, fifth, sock must match one of them. Answer: \(5\).

Initially there are \(0\) minus signs. Changing two signs changes the number of minus signs by \(-2\), \(0\), or \(2\), so its parity is preserved. The number \(3\) is odd, so exactly \(3\) minus signs cannot be obtained.

The board area is \(25\), while a domino covers \(2\) cells. The total area covered by dominoes is even, so \(25\) cells cannot be tiled.

The degree sum is \(12\), so parity does not forbid it. Construct one explicitly. Name the vertices \(A,B,C,D,E\). Connect \(A\) to all other vertices: then \(A\) has degree \(4\), and all others currently have degree \(1\). Now add edges \(BC\) and \(BD\). The degrees are \(\deg A=4\), \(\deg B=3\), \(\deg C=2\), \(\deg D=2\), \(\deg E=1\). Therefore such a graph exists.

Let \(a_n\) be the number of such subsets of \(\{1,\ldots,n\}\). Then \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Thus \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\).

Group the numbers by their residues modulo \(10\). There are \(10\) residues and \(11\) numbers, so two numbers have the same residue. Their difference is divisible by \(10\).

Multiples of \(5\) are losing. Since \(34\equiv4\pmod5\), the first player takes \(4\) stones and leaves \(30\). Then the first player complements the opponent’s move to \(5\).

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

Choose a pair of players from \(9\). The number of games is \(\binom{9}{2}=36\).

Let \(a_n\) be the number of such strings. Then \(a_0=1\), \(a_1=2\), \(a_n=a_{n-1}+a_{n-2}\). We get \(a_7=34\).

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 tiling is impossible.

There are \(9\) residues modulo \(9\). Among \(10\) numbers, two have the same residue. Their difference is divisible by \(9\).

Counting pairs \((student, club)\) by students gives \(12\cdot3=36\). If there are \(k\) clubs, counting by clubs gives \(4k\). Hence \(4k=36\), so \(k=9\).

After the first player adds \(a\), the second adds \(8-a\). Then after the second player’s moves the totals are \(8,16,24,\ldots,64\). Therefore the second player wins.

Possible acquaintance numbers are from \(0\) to \(9\). But \(0\) and \(9\) cannot occur together: if someone knows everyone, nobody has \(0\) acquaintances. Thus there are at most \(9\) different possible values, but \(10\) people. By pigeonhole, two degrees are equal.

Let \(a_n\) be the number of tilings. Then \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=1\). We get \(a_7=21\).

Both changes are divisible by \(3\), so the number modulo \(3\) is invariant. Initially \(5\equiv2\pmod3\), while \(100\equiv1\pmod3\). Therefore \(100\) cannot be obtained.

Under coloring by \(i+j\pmod3\), every straight tromino covers one cell of each color. On the \(5\times5\) board the color counts are \(9,8,8\). The cell \((1,1)\) has one of the colors occurring \(8\) times, so after removal the counts are not equal. No tiling exists.

Total paths: \(\binom{8}{4}=70\). Through \((2,2)\): \(\binom{4}{2}\cdot\binom{4}{2}=36\). Hence the answer is \(70-36=34\).

Let \(A\) be any person. This person has at least \(6\) acquaintances. If among these acquaintances there is an acquaintance pair, then together with \(A\) we get a triple. If there are no acquaintance pairs among them, then each of these \(6\) people knows \(A\) and can know only the three people outside this set and outside \(A\), so their degree is at most \(4\). This contradicts the condition that every degree is at least \(6\).

Color cell \((i,j)\) by \(i+j\pmod4\). Any straight tetromino covers one cell of each of the four colors. On the full \(8\times8\) board each color occurs \(16\) times. The corners have colors \(2,1,1,0\), so after removal the color counts become \(15,14,15,16\), not equal. Hence no tiling exists.

Let \(a_n\) be the number of strings. Then \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\), with \(a_0=1\), \(a_1=2\), \(a_2=4\). We get \(a_3=7\), \(a_4=13\), \(a_5=24\), \(a_6=44\), \(a_7=81\), \(a_8=149\), \(a_9=274\).

Let the numbers be \(a_1,\ldots,a_{20}\). Consider partial sums \(S_k=a_1+\cdots+a_k\) for \(k=1,\ldots,20\). If some \(S_k\) is divisible by \(20\), then the segment \(a_1,\ldots,a_k\) works. If none is divisible by \(20\), then the \(20\) partial sums have only \(19\) nonzero residues modulo \(20\). Hence two of them, \(S_i\) and \(S_j\) with \(i