|
|
 |
Условие
16 карточек с целыми числами от 1 до 16 разложены лицевой стороной вниз в виде таблицы $4\times4$ так, что карточки, на которых записаны соседние числа, лежат рядом (соприкасаются по стороне). Какое наименьшее число карточек нужно одновременно перевернуть, чтобы наверняка определить местоположение всех чисел (как бы ни были разложены карточки)?Решение
Оценка. Занумеруем клетки, как показано на рисунке 1.
Заметим, что одна из клеток с номером 1 должна быть открыта, иначе красный и синий способы заполнения таблицы на рисунке 2 были бы неразличимы. Одна из клеток с номером 2 также должна быть открыта, иначе красный и синий способы заполнения таблицы на рисунке 3 были бы неразличимы.
Аналогично, должны быть открыты хотя бы по одной из клеток с номерами 3, 4, 5, 6, 7, 8, то есть должно быть открыто не менее 8 карточек.
Пример. Докажем, что увидев числа во втором и третьем столбце, мы сможем восстановить числа в первом и четвёртом столбцах. Заметим, что в чёрных клетках шахматной раскраски все числа одной чётности, в белых – другой. Увидев второй и третий столбцы, мы понимаем, в какой клетке какая чётность.
Из открытых клеток выделим те, для которых у записанного в клетке числа не все соседние числа открыты. Из каждой такой клетки проведём ребро в единственную неперевёрнутую соседнюю клетку и однозначно восстановим в ней число.
Заметим, что если в угол ведёт ребро, то мы восстановим число в нём. Если же в угловую клетку не ведёт ребро, то в ней стоит крайнее число, то есть 1 или 16, а так как мы знаем чётность числа в каждой клетке, то в этом случае мы тоже восстановим число в углу. Итак, числа в углах заведомо восстановлены.
Если среди угловых есть клетки, для которых не все соседние числа открыты, из каждого такого угла проведём ребро в неперевёрнутую соседнюю клетку и однозначно восстановим число в ней.
Остались не восстановленными разве что числа в неугловых клетках первого и четвёртого столбца. Рассмотрим любую из них. В неё не ведёт ребро ни из соседнего столбца, ни из угла, а тогда в этой клетке точно крайнее число (так как у неё осталась максимум одна клетка с соседним числом). По чётности легко узнаём, какое крайнее число там должно стоять.
Таким образом, мы восстановили числа во всех клетках.
