|
|
 |
Условие
У фокусника и помощника есть колода с картами; одна сторона ("рубашка") у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд n > 1 карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем k фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?
Решение
Положим k = 2017.
При n = k + 1 фокус устроить легко. Фокусник и помощник нумеруют цвета числами от 1 до k. Помощник, видя цвет последней, (k+1)-й карты (пусть его номер равен a), оставляет открытой a-ю карту. Фокусник, увидев, какая по номеру карта открыта, восстанавливает цвет последней карты.
Осталось показать, что при n ≤ k фокус не удастся. Предположим противное и рассмотрим возможные действия фокусника. Пусть, видя на i-м месте карту цвета a, он объявляет, что на j-м месте карта цвета b (j ≠ i); будем называть это инструкцией (a, i) → (b, j). Можно считать, что для каждой пары (a, i) существует только одна инструкция вида (a, i) → (b, j) (и фокусник при возможности всегда применяет её – поскольку никакой информации о том, какую из таких инструкций применять, у него нет). Тогда инструкций не больше, чем kn.
Будем говорить, что исходная раскладка карт удовлетворяет инструкции (a, i) → (b, j), если в ней на i-м и j-м местах лежат карты цветов a и b соответственно. Тогда каждой инструкции удовлетворяет ровно kn–2 раскладок. С другой стороны, если фокус гарантированно удаётся, то каждая возможная раскладка удовлетворяет хотя бы одной инструкции – той, которую применят помощник с фокусником. Значит, общее число раскладок не может превосходить knkn–2, то есть kn ≤ kn–1n, откуда k ≤ n. Значит, k = n, и неравенство выше обращается в равенство. Это значит, что каждая раскладка удовлетворяет ровно одной инструкции, и с каждой пары (a, i) начинается ровно одна инструкция.
Рассмотрим произвольную инструкцию (a, i) → (b, j); тогда есть и инструкция вида (b, j) → (c, k). Поскольку не существует раскладки, удовлетворяющей обеим инструкциям, должны выполняться условия i = k и a ≠ c.
С другой стороны, для любых двух инструкций (a, i) → (b, j) и (c, k) → (d, l) среди номеров i, j, k, l должны быть совпадающие – иначе опять существует раскладка, удовлетворяющая обеим инструкциям. Рассмотрим граф с вершинами 1, 2, ..., k, в котором i и j соединены ребром [i, j], если существует инструкция вида (a, i) → (b, j) (по доказанному выше, существует также и инструкция вида (b, j) → (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) → (a, 1). Из сказанного выше следует, что разным местам не может быть сопоставлен один и тот же цвет. Поскольку таких мест k – 1, а цветов k < 2(k – 1), какому-то месту i сопоставлен только один цвет a, то есть имеются все k инструкций вида (c, i) → (a, 1) при всевозможных c. Однако существует также инструкция вида
(a, 1) → (c, i) для некоторого c. Но она не может существовать вместе с инструкцией (c, i) → (a, 1). Противоречие.
Ответ
n = 2018.
