PDA

Просмотр полной версии : Задачи о часовых


СЛАУ
07.09.2012, 19:24
В первую очередь опишем задачи, которым посвящена тема.

Имеются круги, расположенные в n рядов по m в ряд и попарно касающиеся друг друга. Круги заключены в прямоугольную рамочку и касаются её. Пример на рисунке 1, здесь n=8, m=8.

http://www.razgovorium.ru/attachment.php?attachmentid=546&stc=1&d=1357957775

Рис. 1. (ссылка на эту же картинку: _http://www.10pix.ru/img1/4763/8449631.jpg )

В каждом круге по 2 стрелки. Каждая стрелка смотрит или на 3, или на 6, или на 9, или на 12 часов. Требуется, поворачивая круги на углы, кратные 90о, добиться того, чтобы стрелки образовывали границы стран на карте. То есть чтобы ломаные, образованные стрелками, не обрывались в точках касания кругов друг с другом, а обрывались только в точках касания кругов с прямоугольной рамочкой (или не обрывались вообще, представляя собой замкнутые ломанные - многоугольники). Допускается некоторые круги не поворачивать, это считается за поворот на 0о. Эту задачу будем называть ЗАДАЧЕЙ О ЧАСОВЫХ, из-за ассоциаций с часами и упоминания границы.

Та конкретная задача о часовых, что представлена на рисунке 1, имеет 2 решения. Первое решение представлено на рисунке 2, второе - на рисунке 3.

http://www.razgovorium.ru/attachment.php?attachmentid=547&stc=1&d=1357957862

Рис. 2 (ссылка на эту же картинку: _http://www.10pix.ru/img1/3476/8447436.jpg )

http://www.razgovorium.ru/attachment.php?attachmentid=548&stc=1&d=1357957909

Рис. 3 (ссылка на эту же картинку: _http://www.10pix.ru/img1/836137/8447629.jpg )

Справедливо следующее

У т в е р ж д е н и е 1.
Любая задача о часовых имеет чётное количество решений.

ПРОДОЛЖЕНИЕ СЛЕДУЕТ (возможно).

Добавлено через 16 минут
З. Ы. Некрасиво, конечно, что я в качестве примера взяла случай, когда n=m - какой-то частный случай получился. Но во-первых, я люблю квадраты; во-вторых, я рисунки 1, 2, 3 рисовала целый день, в пойнте это то ещё удовольствие, и рисовать теперь плюс к этому "прямоугольный случай" было бы чересчур.

СЛАУ
08.09.2012, 21:25
ПРОДОЛЖЕНИЕ.

ДОКАЗАТЕЛЬСТВО УТВЕРЖДЕНИЯ 1.

Для доказательства утверждения 1 хорошо представить себе, что на кругах не по 2 стрелки, а по 4. Одна стрелка смотрит на 3 часа, другая на 6 часов, третья на 9 часов и четвёртая на 12 часов. Только 2 стрелки – чёрные и они видны на белом круге, а 2 стрелки белые и они не видны на белом круге. Окрасим круги, словно циферблаты часов, в зелёный цвет. Тогда мы увидим все 4 стрелки. Всего с точностью до поворотов будет 2 вида кругов. Назовём их круг вида 0 (он изображён на рисунке 4) и круг вида 1 (он изображён на рисунке 5). Названия видов кругов связаны с тем, что на кругах вида 0 между двумя чёрными стрелками 0 белых стрелок, а на кругах вида 1 между двумя чёрными стрелками одна белая стрелка.

http://www.razgovorium.ru/attachment.php?attachmentid=549&stc=1&d=1357958041

Рис. 4. (Ссылка на тот же рисунок: _http://www.10pix.ru/img1/1663/8457122.jpg ).

http://www.razgovorium.ru/attachment.php?attachmentid=550&stc=1&d=1357958096

Рис. 5. (Ссылка на тот же рисунок: _http://www.10pix.ru/img1/2962/8457132.jpg ).

Пусть нам дана конкретная задача о часовых. У неё либо есть решения, либо нет решений. Рассмотрим сначала случай, когда у этой задачи нет решений. В этом случае число решений 0, а это число чётное. Пусть теперь у этой задачи есть решение, обозначим его Р. Значит, можно повернуть круги так, чтобы чёрные стрелки образовывали границы стран. Повернём круги в это положение. Теперь белые стрелки на кругах тоже будут образовывать границы стран. Обоснуем это утверждение. Так как чёрные стрелки образуют границы стран, значит, ни в одной точке касания кругов друг с другом ломанные, образованные чёрными стрелками, не обрываются. Следовательно, ни в одной точке касания кругов друг с другом не «встречаются»/не «соединяются» стрелки разных цветов, чёрная и белая стрелки. Значит, ломанные, образованные белыми стрелками, тоже не обрываются в точках касания кругов друг с другом. Следовательно, белые стрелки будут образовывать границы стран, что и требовалось доказать.

При этом поворотами кругов вокруг их собственных центров можно перевести все чёрные стрелки на место белых стрелок, потому что в круге вида 0 комбинация чёрных стрелок переводится в комбинацию белых стрелок (и наоборот) поворотом круга на 180 градусов в любую сторону, а в круге вида 1 комбинация чёрных стрелок переводится в комбинацию белых стрелок (и наоборот) поворотом круга на 90 градусов в любую сторону. Значит, границы, образованные белыми стрелками, тоже являются решением данной задачи о часовых. Это решение назовём сопряжённым к решению Р. Сопряжённые решения будем обозначать при помощи символа звёздочка. В данном конкретном случае решение, сопряжённое решению Р, будем обозначать Р*. Понятно, что (Р*)*=Р.

И так у каждого решения данной задачи о часовых будет сопряжённое решение. Следовательно, всё множество решений данной задачи о часовых состоит из пар взаимносопряжённых решений. Значит, этих решений чётное количество. ВСЁ ДОКАЗАНО.

Собственно, пара взаимносопряжённых решений представлена на рисунках 2 и 3 (предыдущий пост).

ПРОДОЛЖЕНИЕ СЛЕДУЕТ (возможно).