|
|
 |
Условие
На каждой из 2013 карточек написано по числу, все эти 2013 чисел различны.
Карточки перевёрнуты числами вниз. За один ход разрешается указать на десять карточек, и в ответ сообщат одно из чисел, написанных на них (неизвестно, какое).
Для какого наибольшего t гарантированно удастся найти t карточек, про которые известно, какое число написано на каждой из них?
Решение
1) Покажем сначала, что 1987 = 2013 – 26 карточек угадать не удастся. Занумеруем карточки A1, ..., A2013, разместим на них числа от 1 до 2013 в том же порядке и укажем, как отвечать, чтобы ни одно из чисел на карточках A1, ..., A27 определить не удалось.
При каждом i = 1, ..., 9 объединим карточки A3i–2, A3i–1, A3i в тройку Ti. Если среди указанных 10 карточек присутствуют карточки с числами, большими 27, то назовём наименьшее такое число. Если же все 10 карточек лежат в тройках, то в какой-то тройке Ti лежат хотя бы две карточки; в этом случае мы назовём число, стоящее на ребре между этими карточками на рисунке (если таких пар несколько, то называеи наименьшее из чисел на соответствующих рёбрах).
Заметим, что если на карточках A1, A1, A1 стоят соответственно числа 3, 1, 2 (а не 1, 2, 3), то наши ответы не изменятся. Также нет "однозначности" в остальных тройках. Значит, ни одно из чисел на карточках в тройках определить нельзя.
2) Осталось доказать, что числа на всех карточках, кроме 27, определить удастся. Для этого мы покажем, что если задать все возможные вопросы о каких-то 28 карточках, то по ответам удастся определить число на одной из них. После этого эту карточку можно будет заменить на одну из оставшихся и повторить процедуру. Действуя так, мы в результате определим числа на всех карточках, кроме 27.
Нам потребуется следующая лемма.
Лемма. Пусть в графе не менее чем 3n – 2 вершины и не более чем 3n – 2 ребра (n ≥ 2). Тогда найдутся n вершин, между которыми нет рёбер.
Доказательство. Индукция по n. Сразу заметим, что можно выкинуть несколько вершин и после этого добавить несколько рёбер так, чтобы вершин и рёбер стало по 3n – 2.
База. При n = 2 на четырёх вершинах меньше шести рёбер; значит, какая-то пара вершин не соединена, и можно выбрать эти две вершины.
Шаг индукции. Обозначим степени вершин через d1, ..., d3n–2; тогда d1 + ... + d3n – 2 = 2(3n – 2). Значит, либо найдётся число di < 2 и число dj > 2, либо все степени равны 2. В первом случае выкинем из графа i-ю и j-ю вершину, а также единственного соседа i-й вершины (если он есть); мы выкинули не более трёх вершин и не менее трёх рёбер. Во втором случае выкинем произвольную вершину (пусть её номер равен i) и двух её соседей; так как их степени равны 2, то мы выкинули не менее трёх рёбер и ровно три вершины. В оставшемся графе по предположению индукции найдутся n – 1 вершин без рёбер между ними; добавив к ним i-ю вершину, получаем требуемый набор из n вершин (поскольку мы выкинули всех соседей i-й вершины).
Вернёмся к решению задачи. Пусть мы задали все вопросы о 28 карточках, и пусть c1, ..., ck – все числа, встречающиеся в ответах (тогда
k ≤ 28). Для каждого i = 1, 2, ..., k рассмотрим все десятки карточек, в ответ на которые мы получали число ci; обозначим их пересечение через Si (это множество непусто, ибо содержит карточку с числом ci). Если в этом множестве один элемент, то это и есть карточка с числом ci, и мы определили число на ней.
В противном случае, в каждом из множеств хотя бы по две карточки. При каждом i выберем две карточки в Si и соединим их ребром. Мы получили граф, удовлетворяющий условию леммы при n = 10; значит, в нём можно выбрать 10 карточек без рёбер между ними. Ответом на эту десятку было какое-то число ci. Поэтому в этой десятке должно содержаться множество Si, а следовательно, две карточки из десятки соединены соответствующим ребром. Противоречие.
Ответ
t = 1986.
