|
|
 |
Условие
Было 100 дверей, у каждой свой ключ (отпирающий только эту дверь). Двери пронумерованы числами 1, 2, ..., 100, ключи тоже, но, возможно, с ошибками: номер ключа совпадает с номером двери или отличается на 1. За одну попытку можно выбрать любой ключ, любую дверь и проверить, подходит ли этот ключ к этой двери. Можно ли гарантированно узнать, какой ключ какую дверь открывает, сделав не более
а) 99 попыток;
б) 75 попыток;
в) 74 попытки.
Решение
а) Попробуем, подходит ли первый ключ к первой двери. Если да, то первый ключ опознан. Если нет, то он подходит ко второй двери, а к первой двери – второй ключ. В этом случае опознаны два ключа. Берём очередной слева неопознанный ключ, проверяем его на соответствующей ему двери, распознаём хотя бы один ключ. Если после 99 таких попыток останется нераспознанное, то это последний ключ и для него осталась только одна дверь.
б) Попробуем, подходит ли третий ключ к третьей двери. Если он подходит, то с первыми двумя ключами мы сможем разобраться за одну попытку. Итого за две попытки опознаны первые три ключа.
Если он не подошёл, то попробуем, подходит ли он ко второй двери. Если да, то первый ключ может подойти только к первой двери, а второй – к третьей. Снова за две попытки опознаны три первых ключа. Если снова не подошёл, то он подходит к четвёртой двери. Первые два ключа могут обслужить только две двери, следовательно, третью дверь открывает четвёртый ключ. С первыми двумя ключами и дверьми разберёмся за одну попытку. В этом случае за три попытки опознаны четыре ключа.
Повторяем процесс: пробуем третий слева неопознанный ключ к соответствующей двери. Распознаём за две попытки три ключа или за три попытки четыре ключа. Если мы уже не можем выполнить этот шаг, то осталось менее трёх нераспознанных ключей. С двумя ключами разберёмся за одну попытку, с одним – за 0 попыток. Поскольку каждый раз количество попыток не превосходило ¾ распознаваемых дверей, то всего попыток будет не более 75.
в) Предположим, что Хвастун умеет это делать за 74 попытки. Разобьём двери и ключи на 25 четвёрок подряд идущих. Облегчим Хвастуну задачу. Будем предлагать ему только такие расположения ключей, в которых ключи не могут открывать двери из других четвёрок, и сообщим Хвастуну об этом. Тогда бессмысленно будет пробовать ключ к двери из другой четвёрки, и у Хвастуна всё равно есть стратегия за 74 попытки. По этой стратегии в какой-то четвёрке он делает не более двух попыток. У пары попыток есть лишь четыре различных исхода, и для каждого из них Хвастун указывает какое-то расположение ключей в четвёрке. Но вариантов соответствия четырёх ключей и дверей больше: (1234), (2134), (1324), (1243), (2143). Противоречие.
Ответ
а) Можно; б) можно; в) нельзя.
Замечания
Баллы: 1 + 3 + 4.
