В каждой клеточке клетчатой доски 7 x 11 сидит жук. В какой то момент времени все жуки переползают в одну из соседних клеточек, которые имеют с ними общую сторону. Докажите, что после этого, какая-то из клеток будет пустой (т.е. без жука)
Допустим обратное. Пусть и после переползания жуков в соседние клетки, все клетки останутся заполненными жуками. Достаточно рассмотреть вариант, когда в каждой паре соседних клеток все жуки просто меняются местами. То есть в первой строке жук из первого столбца переползает во второй столбец, а жук из второго столбца переползает в первый столбец, жук из третьего столбца перебирается в четвертый столбец, а жук из четвертого в третий и так далее по другим строкам. Однако, поскольку число столбцов нечетно мы сможем выполнить эти операции по всем строкам лишь до шестого столбца. В итоге у нас останется еще один столбец. Перемещаем жуков теперь по строкам таким же образом. Жук из первой строки седьмого столбца переползает во вторую строку седьмого столбца, а жук из второй строки в первую и так далее. Но, так как и количество строк у нас является нечетным, то в итоге жук из последней 11-й строки должен будет переползти или в десятую строку или в шестой столбец своей строки и его клетка окажется пустой. Приходим к противоречию, следовательно одна из клеток обязательно окажется пустой.
Answers & Comments
Verified answer
Допустим обратное. Пусть и после переползания жуков в соседние клетки, все клетки останутся заполненными жуками. Достаточно рассмотреть вариант, когда в каждой паре соседних клеток все жуки просто меняются местами. То есть в первой строке жук из первого столбца переползает во второй столбец, а жук из второго столбца переползает в первый столбец, жук из третьего столбца перебирается в четвертый столбец, а жук из четвертого в третий и так далее по другим строкам. Однако, поскольку число столбцов нечетно мы сможем выполнить эти операции по всем строкам лишь до шестого столбца. В итоге у нас останется еще один столбец. Перемещаем жуков теперь по строкам таким же образом. Жук из первой строки седьмого столбца переползает во вторую строку седьмого столбца, а жук из второй строки в первую и так далее. Но, так как и количество строк у нас является нечетным, то в итоге жук из последней 11-й строки должен будет переползти или в десятую строку или в шестой столбец своей строки и его клетка окажется пустой. Приходим к противоречию, следовательно одна из клеток обязательно окажется пустой.