x, y, z

На каждой клетке доски 5×5 сидит жучок

# 17 Июл 2015 02:14:37
ABC
На каждой клетке доски 5×5 сидит жучок. В некоторый момент времени все жучки переползают на соседние по стороне клетки. Возможно ли, что в итоге снова в каждой клетке будет по одному жучку, то есть ни в одной клетке не будет более одного жучка?
# 17 Июл 2015 07:58:41
Evgeniy

Перемещение жучков можно отождествить с перестановкой $\sigma$ на множестве из 25 точек. Например, если жучок с $i$ клетки переползает в $j$ клетку, значит $\sigma(i)=j$. Известно, что любая перестановка раскладывается в произведение циклов. По условию задачи жучки не должны оставаться на месте, поэтому у нас циклы длины не меньше 2. Перемещение жучков происходит по горизонтали или по вертикали, поэтому в любом цикле кол-во движений вниз равно кол-ву движений вверх, а также кол-во движений влево равно кол-ву движений вправо, следовательно все циклы имеют четную длину. Число 25 нечетное, его нельзя разбить в сумму четных, т.е. не существует перестановки на 25 точках, состоящей из циклов четной длины.
# 13 Авг 2015 16:45:49
math
Есть более наглядное объяснение. Предположим, что клеточки раскрашены в черный и белый цвета в шахматном порядке. По условию получается, что каждый жук из белой клетки переползает в черную, а из черной - в белую. Т.к. всего клеток 25, то клеток одного цвета будет на 1 больше чем другого, значит неизбежно в какой-то из клеток будет не менее 2-х жуков.
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

* Сколько символов на картинке?
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.