11.4. A magician and an assistant have a deck of cards; one side (the "back") of all cards is the same, while the other is painted in one of 2017 colors (the deck contains 1,000,000 cards of each color). The magician and the assistant are going to perform the following trick. The magician leaves the room, and the audience lays out a row of $n>1$ cards face down on the table. The assistant looks at these cards and then turns all but one of them face up, without changing their order. Then the magician enters, looks at the table, points to one of the face-down cards, and names its color. For what smallest $n$ can the magician and the assistant agree in advance so that the trick is guaranteed to succeed?

(I. Bogdanov, K. Knop)
Answer. $n=2018$.

Solution. Let $k=2017$.

For $n=k+1$, the trick is easy to arrange. The magician and the assistant number the colors from 1 to $k$. The assistant, seeing the color of the last, $(k+1)$-th card (let its number be $a$), leaves the $a$-th card open. The magician, seeing which numbered card is open, can restore the color of the last card.

It remains to show that the trick cannot be performed for $n \leqslant k$. Suppose the contrary and consider the possible actions of the magician. Let, seeing a card of color $a$ in the $i$-th position, he announces that the card in the $j$-th position is of color $b$ (then $i \neq j$); we will call this an instruction $(a, i) \rightarrow(b, j)$. We can assume that for each pair $(a, i)$ there is only one instruction of the form $(a, i) \rightarrow(b, j)$ (and the magician always applies it when possible - since he has no information on which of such instructions to apply). Then there are no more than $k n$ instructions.

We will say that the initial layout of cards satisfies the instruction $(a, i) \rightarrow(b, j)$ if in it the $i$-th and $j$-th positions have cards of colors $a$ and $b$ respectively. Then each instruction is satisfied by exactly $k^{n-2}$ layouts. On the other hand, if the trick is guaranteed to succeed, then each possible layout satisfies at least one instruction - the one that the assistant and the magician will apply. Therefore, the total number of layouts cannot exceed $k n \cdot k^{n-2}$, that is, $k^{n} \leqslant k^{n-1} n$, from which $k \leqslant n$. Thus, $k=n$, and the inequality above turns into an equality. This means that each layout satisfies exactly one instruction, and from each pair $(a, i)$ exactly one instruction starts.

Consider an arbitrary instruction $(a, i) \rightarrow(b, j)$; then there is also an instruction of the form $(b, j) \rightarrow(c, k)$. Since there is no layout that satisfies both instructions, the conditions $i=k$ and $a \neq c$ must be met.

On the other hand, for any two instructions $(a, i) \rightarrow(b, j)$ and $(c, k) \rightarrow(d, \ell)$, among the numbers $i, j, k, \ell$ there must be coinciding ones - otherwise there is again a layout that satisfies both instructions. Consider a graph with vertices $1,2, \ldots, k$, in which $i$ and $j$ are connected by an edge $[i, j]$, if there is an instruction of the form $(a, i) \rightarrow(b, j)$ (by the above, there is also an instruction of the form $\left.(b, j) \rightarrow\left(a^{\prime}, i\right)\right)$. Then any two edges in this graph have a common vertex, and from each vertex at least one edge goes out. Let, for definiteness, $[1,2]$ be an edge of this graph. From vertex 3 an edge goes out, having a common vertex with the first - let, for definiteness, this be $[1,3]$. Then any edge from vertex $k>3$ must have the form $[1, k]$, to have a common vertex with each of the edges $[1,2]$ and $[1,3]$. Finally, any edge must have a common vertex with each of the edges $[1,2],[1,3]$ and $[1,4]$, that is, it must contain vertex 1. Thus, in each instruction one of the position numbers is 1.

Finally, we associate with each position $i>1$ all such colors $a$ for which there is an instruction of the form $(c, i) \rightarrow(a, 1)$. From the above, it follows that different positions cannot be associated with the same color. Since there are $k-1$ such positions and $k<2(k-1)$ colors, some position $i$ is associated with only one color $a$, that is, there are all $k$ instructions of the form $(c, i) \rightarrow(a, 1)$ for all possible $c$. However, there is also an instruction of the form $(a, 1) \rightarrow(c, i)$ for some $c$. But it cannot exist together with the instruction $(c, i) \rightarrow(a, 1)$; contradiction.