Большой куб состоит и 27 маленьких. Может ли жук выползти из центрального и, последовательно прогрызая стенки, побывать во всех?
Здравствуйте, Кодт, Вы писали:
К>Жук должен начать и кончить в черном кубике.
Здравствуйте, Кодт, Вы писали:
К>Жук должен начать и кончить в черном кубике.
Честно говоря не понял. Поясни как из всего предыдущего (14 черных и 13 белых, в центре белый) следует это утверждение ? Что за свойство четности ?
... << Играет Martin L. Gore — In a Manner of Speaking>>
Здравствуйте, DemAS, Вы писали:
DAS> Честно говоря не понял. Поясни как из всего предыдущего (14 черных и 13 белых, в центре белый) следует это утверждение ? Что за свойство четности ?
Потому что следующий куб, в который переползёт жук, будет отличного от предыдущего цвета. Следовательно, для того, чтобы сгрызть 27 кубиков, из которых 14 черных и 13 белых, жук должен начать с черного. Но, по условию, он начинает с белого => значит, сгрызть кубики не получится.
Есть очень похожая задача про пятнашки — можно ли собрать пятнашки, если исходное расположение таково — берём "собранную" позицию и меняем местами единичку и двойку, т.е.
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15
Здравствуйте, Andy77, Вы писали:
A>Есть очень похожая задача про пятнашки — можно ли собрать пятнашки, если исходное расположение таково — берём "собранную" позицию и меняем местами единичку и двойку, т.е.
A>A>2 1 3 4
A>5 6 7 8
A>9 10 11 12
A>13 14 15
A>
Наверно нельзя. А вот доказательство?
A>>A>>2 1 3 4
A>>5 6 7 8
A>>9 10 11 12
A>>13 14 15
A>>
Например так.
Предположим можно их поменять местами. Видно, что ходов должно быть четное число.
Сопоставим пустой клетке фишку с номером 16.
Текущее положение описывается перестановкой. Например, позиция, где 1 и 2 поменяли местами описывается
перестановкой ( 2 1 3 ... 15 16 ) = транспозиция (1 2). Каждый ход --- умножение перестановки текущей позиции слева на транспозицию (a b), где a и b --- номера полей, участвующих в ходе (с одного на другое двигается фишка).
Если возможно получить позицию с переставленными 1 и 2, то
(1 2) = a_1 * a_2 * ... * a_{2n}, где a_i --- транспозиции, но это невозможно, так как
транспозиция --- нечетная перестановка,
а при умножении перестановок, четность перемножается ( +1 --- четная; -1 --- нечетная ).
Здравствуйте, KonstantinA, Вы писали:
A>>>A>>>2 1 3 4
A>>>5 6 7 8
A>>>9 10 11 12
A>>>13 14 15
A>>>
KA>Например так.
KA>Предположим можно их поменять местами. Видно, что ходов должно быть четное число.
KA>Сопоставим пустой клетке фишку с номером 16.
KA>Текущее положение описывается перестановкой. Например, позиция, где 1 и 2 поменяли местами описывается
KA>перестановкой ( 2 1 3 ... 15 16 ) = транспозиция (1 2). Каждый ход --- умножение перестановки текущей позиции слева на транспозицию (a b), где a и b --- номера полей, участвующих в ходе (с одного на другое двигается фишка).
KA>Если возможно получить позицию с переставленными 1 и 2, то
KA>(1 2) = a_1 * a_2 * ... * a_{2n}, где a_i --- транспозиции, но это невозможно, так как
KA>транспозиция --- нечетная перестановка,
KA>а при умножении перестановок, четность перемножается ( +1 --- четная; -1 --- нечетная ).
Что означает в данном случае "нечетная перестановка"?
Перекуём баги на фичи!
