Задачи о часовых Опции

[СЛАУ]

В первую очередь опишем задачи, которым посвящена тема.

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



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

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

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



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



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

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

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

ПРОДОЛЖЕНИЕ СЛЕДУЕТ.

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

Сообщение отредактировал СЛАУ - 7.09.2012, 17:43

[СЛАУ]

ПРОДОЛЖЕНИЕ.

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

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



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



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

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

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

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

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

ПРОДОЛЖЕНИЕ СЛЕДУЕТ.

Сообщение отредактировал СЛАУ - 9.09.2012, 16:02