Задача: У фокусника и помощника есть колода с картами; одна сторона («рубашка») у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд \( n > 1 \) карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем \( n \) фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?
Решение: Положим \( k = 2017 \).

При \( n = k + 1 \) фокус устроить легко. Фокусник и помощник нумеруют цвета числами от 1 до \( k \). Помощник, видя цвет последней, \((k + 1)\)-й карты (пусть его номер равен \( a \)), оставляет открытой \( a \)-ю карту. Фокусник, увидев, какая по номеру карта открыта, восстанавливает цвет последней карты.

Осталось показать, что при \( n \leqslant k \) фокус не удастся. Предположим противное и рассмотрим возможные действия фокусника. Пусть, видя на \( i \)-м месте карту цвета \( a \), он объявляет, что на \( j \)-м месте карта цвета \( b \) (тогда \( i \neq j \)); будем называть это инструкцией \((a, i) \rightarrow (b, j)\). Можно считать, что для каждой пары \((a, i)\) существует только одна инструкция вида \((a, i) \rightarrow (b, j)\) (и фокусник при возможности всегда применяет её — поскольку никакой информации о том, какую из таких инструкций применять, у него нет). Тогда инструкций не больше, чем \( kn \).

Будем говорить, что исходная раскладка карт удовлетворяет инструкции \((a, i) \rightarrow (b, j)\), если в ней на \( i \)-м и \( j \)-м местах лежат карты цветов \( a \) и \( b \) соответственно. Тогда каждой инструкции удовлетворяет ровно \( k^{n-2} \) раскладок. С другой стороны, если фокус гарантированно удаётся, то каждая возможная раскладка удовлетворяет хотя бы одной инструкции — той, которую применяют помощник с фокусником. Значит, общее число раскладок не может превосходить \( kn \cdot k^{n-2} \), то есть \( k^n \leqslant k^{n-1} n \), откуда \( k \leqslant n \). Значит, \( k = n \), и неравенство выше обращается в равенство. Это значит, что каждая раскладка удовлетворяет ровно одной инструкции, и с каждой пары \((a, i)\) начинается ровно одна инструкция.

Рассмотрим произвольную инструкцию \((a, i) \rightarrow (b, j)\); тогда есть и инструкция вида \((b, j) \rightarrow (c, k)\). Поскольку не существует раскладки, удовлетворяющей обеим инструкциям, должны выполняться условия \( i = k \) и \( a \neq c \).

С другой стороны, для любых двух инструкций \((a, i) \rightarrow (b, j)\) и \((c, k) \rightarrow (d, l)\) среди номеров \( i, j, k, l \) должны быть совпадающие — иначе опять же существует раскладка, удовлетворяющая обеим инструкциям. Рассмотрим граф с вершинами \( 1, 2, \ldots, k \), в котором \( i \) и \( j \) соединены ребром \([i, j]\), если существует инструкция вида \((a, i) \rightarrow (b, j)\) (по доказанному выше, существует также и инструкция вида \((b, j) \rightarrow (a', i)\)). Тогда любые два ребра в этом графе имеют общую вершину, и из каждой вершины выходит хотя бы одно ребро. Пусть для определённости \([1, 2]\) — ребро этого графа. Из вершины 3 выходит ребро, имеющее общую вершину с первым — пусть для определённости это \([1, 3]\). Тогда любое ребро из вершины \( k > 3 \) обязано иметь вид \([1, k]\), чтобы иметь общие вершины с каждым из рёбер \([1, 2]\) и \([1, 3]\). Наконец, любое ребро вообще должно иметь общую вершину с каждым из рёбер \([1, 2]\), \([1, 3]\) и \([1, 4]\), то есть должно содержать вершину 1. Итак, в каждой инструкции один из номеров мест равен 1.

Наконец, сопоставим каждому месту \( i > 1 \) все такие цвета \( a \), что существует инструкция вида \((c, i) \rightarrow (a, 1)\). Из сказанного выше следует, что разным местам не может быть сопоставлен один и тот же цвет. Поскольку таких мест \( k - 1 \), а цветов \( k < 2(k - 1) \), какому-то месту \( i \) сопоставлен только один цвет \( a \), то есть имеются все \( k \) инструкций вида \((c, i) \rightarrow (a, 1)\) при всевозможных с. Однако существует также инструкция вида \((a, 1) \rightarrow (c, i)\) для некоторого c. Но она не может существовать вместе с инструкцией \((c, i) \rightarrow (a, 1)\); противоречие.
Ответ: 2018