ЗаЗа: Жук в кубе
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 12:07
Оценка:
Большой куб состоит и 27 маленьких. Может ли жук выползти из центрального и, последовательно прогрызая стенки, побывать во всех?

17.01.03 00:01: Ветка выделена из темы Занимательные задачки
Автор: fAX
Дата: 07.08.02
— ХД
Re[2]: Жук в кубе (ЗаЗа)
От: Кодт Россия  
Дата: 30.12.02 12:39
Оценка: 10 (1)
Здравствуйте, Pushkin, Вы писали:

P>Большой куб состоит и 27 маленьких. Может ли жук выползти из центрального и, последовательно прогрызая стенки, побывать во всех?


Нет.
Доказательство: свойство четности.
Покрасим кубики в шахматном порядке.
Смежные кубики имеют разный цвет.
Угловые — черные, центры ребер — белые, центры сторон — черные, центр куба — белый. Итого 14 черных и 13 белых.

Жук должен начать и кончить в черном кубике.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: Жук в кубе (ЗаЗа)
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 13:10
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Жук должен начать и кончить в черном кубике.


Re[3]: Жук в кубе (ЗаЗа)
От: DemAS http://demas.me
Дата: 03.01.03 05:53
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Жук должен начать и кончить в черном кубике.


Честно говоря не понял. Поясни как из всего предыдущего (14 черных и 13 белых, в центре белый) следует это утверждение ? Что за свойство четности ?
... << Играет Martin L. Gore — In a Manner of Speaking>>
Re[4]: Жук в кубе (ЗаЗа)
От: Andy77 Ниоткуда  
Дата: 03.01.03 19:04
Оценка: 1 (1)
Здравствуйте, DemAS, Вы писали:

DAS> Честно говоря не понял. Поясни как из всего предыдущего (14 черных и 13 белых, в центре белый) следует это утверждение ? Что за свойство четности ?


Потому что следующий куб, в который переползёт жук, будет отличного от предыдущего цвета. Следовательно, для того, чтобы сгрызть 27 кубиков, из которых 14 черных и 13 белых, жук должен начать с черного. Но, по условию, он начинает с белого => значит, сгрызть кубики не получится.

Есть очень похожая задача про пятнашки — можно ли собрать пятнашки, если исходное расположение таково — берём "собранную" позицию и меняем местами единичку и двойку, т.е.

2  1  3  4
5  6  7  8
9  10 11 12
13 14 15
Re[5]: Пятнашки
От: IO Украина  
Дата: 04.01.03 07:28
Оценка:
Здравствуйте, Andy77, Вы писали:

A>Есть очень похожая задача про пятнашки — можно ли собрать пятнашки, если исходное расположение таково — берём "собранную" позицию и меняем местами единичку и двойку, т.е.


A>
A>2  1  3  4
A>5  6  7  8
A>9  10 11 12
A>13 14 15
A>

Наверно нельзя. А вот доказательство?
Re[6]: Пятнашки
От: KonstantinA Россия  
Дата: 06.01.03 14:13
Оценка:
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 --- нечетная ).
Re[7]: Пятнашки
От: ilya123 Россия  
Дата: 10.01.03 17:18
Оценка:
Здравствуйте, 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 --- нечетная ).

Что означает в данном случае "нечетная перестановка"?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.