Question

На каждой клетки доски размером 9×9 сидит жук,По свистку свистка каждий жучок переползает в одну из соседних клеток.При етом в некоторих клетках может оказаться больше одного жука а некоторие клетки окажутся незанятими.Докажите что при етом не занятих клеток не меньше 9.​

Answer 1

Ответ:

Пошаговое объяснение:

Задача слегка похожа на замощение домино шахматной доски (в условии той задачи стоял следующий вопрос: можно ли замостить всю шахматную доску домино размерами 2x1, если вырезать 2 противоположные угловые клетки).

Здесь можно воспользоватся тем же принципом:

Доску 9x9 превратим в шахматную.Тогда окажется, что из 81 клеток 45 одного цвета, а 36-другого.

Жуки могут переползать только на клетки другого цвета.

После свистка 36 жуков, которые были на 36 клетках одного цвета, переместились на 36 клеток другого цвета.Но у этого другого цвета 45 клеток.Следовательно, 9 клеток точно окажутся незанятыми.

Answer 2

Давайте докажем это утверждение по принципу Дирихле.

Предположим, что на доске размером 9×9 сидит 8 или менее жуков, и все клетки заняты. Рассмотрим ситуацию, где каждый жук начинает перемещаться на соседнюю клетку, как описано в задаче.

Поскольку клеток всего 9×9 = 81, а жуков 8 или менее, то по принципу Дирихле, какой-то из чисел (1, 2, 3, 4, 5, 6, 7, 8) должно встретиться как минимум в двух клетках. Это означает, что какие-то две клетки содержат одинаковое количество жуков.

Теперь представьте, что жуки, находящиеся в этих двух клетках, одновременно начинают двигаться. В какой-то момент они попробуют переползти на одну и ту же клетку, так как они начали с одинакового количества жуков и могут перемещаться только на соседние клетки. Это противоречие с условиями задачи, так как два жука не могут одновременно находиться в одной клетке.

Из этого противоречия следует, что предположение о том, что на доске меньше 9 незанятых клеток, неверно. Следовательно, на доске должно быть как минимум 9 незанятых клеток.