Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2011/04/Samovol.pdf Дата изменения: Thu Jan 10 13:56:20 2013 Дата индексирования: Sun Feb 3 06:47:21 2013 Кодировка: Windows-1251

МАТЕМАТИЧЕСКИЙ КРУЖОК
Три года назад (в 'Кванте' ?1 за 2008 г.) в нашем журнале была опубликована статья И. Акулича (Минск, Белоруссия) 'Призрак Леонардо'. Рассмотренные в ней задачи и поставленные автором вопросы вызвали заметный отклик. В этом номере мы публикуем две статьи: 'Охота на призрак Леонардо' (ее авторы П. Самовол из города Беер-Шева в Израиле и В.Журавлев из Москвы) и 'Раскраски графов и линейные уравнения' (ее авторы В. Дорофеев из Мытищ и А. Спивак из Москвы), которые отвечают на некоторые вопросы, поставленные И.Акуличем. Прочитав эти статьи, вы познакомитесь с двумя разными подходами к одной и той же теме.
А-а-а, понимаю Кажется, упоминания о дуалистах находили в рукописях самого Леонардо да Винчи, а крашеные блондинки яркие представители этого тайного общества Не ерничайте, агент Малдер, лучше обратите внимание на перехват переговоров дуалистов, который я обнаружила по этому делу: За один ход разрешается одновременно перекрасить в противоположный цвет любую клетку шахматной доски, а также все клетки, имеющие с ней общую сторону. Можно ли за несколько ходов перекрасить в противоположный цвет все клетки доски? 2 Как интересно! Но эти дуалисты, по моим агентурным данным, кроме прямоугольных, используют также доски весьма причудливой формы и совершенно произвольной начальной раскраски. Вот посмотрите на рисунок 1.

ОХОТА НА ПРИЗРАК ЛЕОНАРДО
П.САМОВОЛ, В.ЖУРАВЛЕВ
Шахматы Агент Малдер ! Нам только что сообщили, что на чемпионате мира по шахматам стали происходить очень странные вещи. Во время трансляции матча на мониторах черные клетки доски хаотически перекрашиваются в белые и, наоборот, белые в черные. После нескольких перекрасок все прекращается. Болельщики недоумевают, руководители федерации в панике, судьи поговаривают о новом компьютерном вирусе. Руководство ФБР подозревает, что рецидив может не ограничиться шахматными досками. Ведь скоро чемпионат мира по стоклеточным шашкам!.. Надо же сколько замечательных событий!.. Но вы уверены, агент Скалли, что перекраска действительно является хаотической? Хороший вопрос, агент Малдер! Давайте-ка посмотрим полученные видеозаписи. Так и есть! Вы правы перекраска происходит по определенному правилу. Одновременно с каждой клеткой перекрашиваются в противоположный цвет все ее соседи клетки, имеющие с ней общую сторону. А вы заметили, Дана, что перекраска прекращается тогда, когда исходный цвет всех клеток доски меняется на противоположный? Неужели, агент Малдер, мы опять имеем дело с дуалистами? Кого вы имеете в виду? Фокс, это же одно из тайных обществ, считающих, что весь мир двуцветный. При этом для соблюдения баланса в мире необходимо совершать перекраску его объектов в противоположный цвет, придерживаясь определенных правил.
1

Рис. 1

Вы попали в самую точку, агент Малдер! Они используют доски произвольной формы для доступа к своим базам данных. При этом кодами доступа являются определенные наборы ходов. Ну что, будем использовать хакеров для взлома парочки сайтов или обратимся к специалистам-теоретикам, чтобы разобраться с проблемой до конца? Что скажете, агент Скалли? Думаю, и то, и другое. Кроме того, подключим наших зарубежных коллег. Выходит, что все эти дуальные перекраски на произвольных досках не исследованы математиками нашего аналитического управления? По ряду случаев неплохо продвинулись русские, но у них возникли нерешенные вопросы 3 : Вопрос 1. Существует ли хотя бы одна фигура из клетчатой бумаги (клетчатая доска), клетки которой нельзя перекрасить в противоположный цвет, как бы мы ни ходили? (Ход в клетку это перекраска в противоположный цвет клетки и всех клеток, имеющих с ней общую сторону.) Вопрос 2. Верно ли, что количество различных кодов доступа (наборов ходов, позволяющих перекрасить в противоположный цвет все клетки фигуры) для прямоугольника является целой неотрицательной степенью числа 2? Вы заметили, агент Скалли, что все примеры, которые мы встречали до настоящего времени, позволяли определить этот набор ходов или, как говорится, определить код доступа. Но можно было бы предположить, что есть пример фигуры, для которой кода доступа просто не существует, я бы даже сказал, не пример а контрпример. Агент Малдер, а ведь дуалисты верят, что контрпримера нет!
3 Ответы на другие вопросы из статьи И. Акулича 'Призрак Леонардо' даны в статье 'Раскраски графов и линейные уравнения' В.Дорофеева и А.Спивака

1 Фокс Малдер и Дана Скалли персонажи сериала 'X-files'. 2 Задача предлагалась в конкурсе имени А.П.Савина 'Математика 68' в 2007/08 учебном году.


МАТЕМАТИЧЕСКИЙ

КРУЖОК

В данном вопросе мы не можем полагаться на веру, нам нужны доказательства! Погодите-ка, вот пришло сообщение с Ближнего Востока. Похоже, они что-то откопали. Графы Я же говорил, что во всех этих головоломках имеются скрытые связи. Все разнообразие досок и кодов дуалистов легко перекладывается на язык графов. В данном случае, агент Скалли, граф это некоторое множество точек (вершин), при этом отдельные вершины соединены между собой не более чем одной дугой (ребром). Предполагается, что любая вершина сама с собой дугой не соединяется (в графе нет петель). Тогда на языке графов вопрос 1 можно переформулировать: Пусть вершины графа окрашены в два цвета (черный и белый). За один ход разрешается одновременно перекрасить в противоположный цвет любую вершину графа и все смежные с ней вершины (соединенные с ней ребром). Можно ли за несколько ходов перекрасить в противоположный цвет все вершины графа? Я поняла. Каждую клетку фигуры вы заменяете вершиной графа. Если клетки являются соседями, то соединяете вершины ребром графа. Так каждой доске или фигуре из клеточек можно сопоставить граф. Точно, это называется обобщением первоначальной задачи. Теперь на языке графов мы можем рассматривать все приведенные ранее примеры. Как интересно, я подумала, что если в графе из каждой вершины выходит четное число ребер, то код доступа или раскраску для такого графа получить легко нужно просто сходить в каждую вершину. Верное наблюдение, Дана! Кстати, агент Скалли, а ведь скан полученного древнего изображения с Ближнего Востока содержит доказательство отсутствия контрпримера! Я немного его адаптировал, и вот что получилось. Докажем, что код доступа всегда существует, т.е. всегда можно перекрасить в противоположный цвет все вершины графа. Заметьте, Дана, очередность ходов не играет никакой роли. Если вы выберете некоторый набор вершин для ходов, то тем самым определите конечную раскраску графа. Надеюсь, агент Скалли, вам знакомы рассуждения по индукции. С одной вершиной справится легко просто покрасим ее. Предположим, что мы имеем соответствующий код доступа (набор ходов) для любого графа с n вершинами, и рассмотрим теперь граф с вершинами A1, A2,..., An , An +1 . Отбросим временно некоторую вершину Ak , тогда мы получим граф с n вершинами, и для него, по нашему предположению, существует код доступа (необходимый набор ходов). Если вершина Ak связана с нечетным числом вершин из этого набора, то этот набор подойдет и для нашего графа с n + 1 вершиной. Однако возможен случай, когда для каждой вершины Ak , где 1 k n + 1 , мы найдем такой код доступа (набор ходов) на оставшихся n вершинах, что Ak будет соединена с четным числом вершин из этого набора. Заметьте, Дана: если в этом случае мы проделаем один за другим процессы перекраски для двух разных вершин Ak Ai , то получим, что все вершины останутся с начальным цветом, кроме вершин Ak и Ai . Но ведь это означает, агент Малдер, что мы можем перекрасить в противоположный цвет любые две вершины, которые выберем, не меняя цвета остальных вершин. Совершенно верно! Осталась самая малость. Что делать, агент Скалли, если в графе четное число вершин?

Тогда, агент Малдер, перекрасим каждую пару вершин в противоположный цвет, пока все они не изменят цвет на противоположный. А если в графе нечетное число вершин? Дайте подумать В этом случае граф должен содержать вершину, у которой четное число соседних вершин. Иначе общее число 'соседей' у всех вершин графа было бы нечетным, а это невозможно, поскольку общее число 'соседей' в два раза больше чем количество ребер в графе. Ага! Выберем эту вершину и перекрасим ее вместе с четным числом всех ее соседей. При этом окажется, что мы перекрасили в противоположный цвет нечетное число вершин. Так как в графе нечетное количество вершин, то остались неперекрашенными четное количество вершин. Разобьем эти вершины по парам и перекрасим, как мы это уже обсуждали! Вот и ответ на первый вопрос. Мы нашли строгое доказательство того, что код доступа всегда существует! Группы Для поиска ответа на второй вопрос шеф отправляет нас в Европу. И все про какую-то теорию групп говорит. Что это за теория такая, никогда о ней не слышала. Она никак не связана с теорией заговора? К примеру, группа заговорщиков готовит переворот Нет, агент Скалли, про теорию групп пишут в толстых учебниках, а про теорию заговора пишут в детективных и исторических романах. Впрочем, в нашем бюро недавно выпустили методичку по теории заговора Иронизируете, агент Малдер! А ведь мы сейчас пытаемся раскрыть заговор дуалистов, и теория групп всего лишь инструмент в этой большой игре. С вами, агент Скалли, не поспоришь. Но вернемся к идее шефа. Ведь стоит только применить к нашим доскам теорию групп, и мы как на блюдечке получаем ответ на второй вопрос. При этом имеет место даже более сильное утверждение, касающееся графов: Для рассматриваемых графов количество различных кодов доступа (наборов ходов, позволяющих перекрасить в противоположный цвет все вершины графа) является целой неотрицательной степенью числа 2. Коды доступа мы считаем различными, если отличаются наборы вершин, куда сделаны ходы. Это следует из известного всем алгебраистам факта, что порядок подгруппы делит порядок группы. Этот факт известен как теорема Лагранжа. Впрочем, для вас, агент Скалли, я нашел доказательство с применением элементарных методов. Итак, агент Скалли, рассмотрим граф с n вершинами. Дальнейшие рассуждения мы могли бы проводить для любой фиксированной раскраски графа. Но не будем забивать себе голову и возьмем раскраску, при которой все вершины графа покрашены в белый цвет. Рассмотрим множество всевозможных наборов ходов в вершины графа. Как по-вашему, агент Скалли, сколько их? Поскольку в любую вершину ход либо сделан, либо нет, то различных наборов ходов ровно 2n . При подсчете я учла 'нулевой' набор ходов, т.е. такой, при котором ни в одну вершину ходы не делаются. Хорошо. Теперь в этом множестве выделим подмножество наборов ходов, которые оставляют все вершины графа покрашенными в белый цвет, т.е. не меняют исходной раскраски графа. Количество элементов этого подмножества обозначим через s. Очевидно, что оно содержит 'нулевой' набор, поэтому s > 0. Назовем это подмножество 'нейтральным'.


Далее разобьем все наборы ходов на классы. Будем считать, что два набора ходов принадлежат одному классу, если результаты их разрозненного применения к белой раскраске вершин графа (фиксированной раскраске) совпадают. Пусть k обозначает количество таких классов. Как думаете, Дана, сколько может быть наборов в классе? Думаю, как повезет! Везение в нашей работе, конечно, очень важно. Однако в этой ситуации нам более важно, что во всех классах таких наборов одинаковое количество. Сможете ли вы доказать, агент Скалли, что в каждом классе ровно s наборов ходов? Ну, хотя бы попробуйте разобраться Рассмотрим два набора ходов из одного класса. Обозначим их через h1 и h2 и рассмотрим их объединение (двойной ход в одну и ту же вершину графа в объединении двух наборов приравниваем к отсутствию хода). Заметьте, что объединение наборов h1 и h2 лежит в нейтральном подмножестве. Действительно, каждая вершина после применения объединения h1 и h2 поменяет цвет четное количество раз и, следовательно, исходная раскраска вершин графа не изменится. Что получится, если набор ходов h1 объединить с объединением h1 и h2 ? Очевидно, агент Малдер, что мы получим набор ходов h2 . Значит, агент Скалли, h2 получается объединением набора ходов h1 с некоторым уникальным набором ходов из нейтрального подмножества. Следовательно, количество элементов в этом классе не больше, чем количество элементов из нейтрального подмножества, т.е. не больше чем s. С другой стороны, если мы возьмем какой-нибудь набор ходов в некотором классе, то в этом классе лежит набор ходов, получающиеся объединением исходного набора ходов с любым набором ходов из нейтрального подмножества. Следовательно, в этом классе число наборов не меньше чем s. В итоге получаем, что в каждом классе ровно s наборов ходов. К слову сказать, и в классе, в котором находятся наборы ходов, перекрашивающие все вершины графа в противоположный цвет, также s элементов. Теперь все понятно. Все наборы ходов разбились на k классов по s элементов, т.е. ks = 2n . Следовательно, и k и s являются степенями двойки. Что и требовалось доказать, агент Малдер! Осталось подготовить отчет для шефа Опять шахматы Неплохо мы все-таки поработали, да? Раскололи этих дуалистов! А ведь все, вроде бы, началось с шахмат Шахматы! Какая фантастическая игра! Как их только не трансформируют А вот, кстати, смотрю, у вас на полочке раритет с выставки в Париже. Гексагональные шахматы Глинского (рис.2). Можно посмотреть? Где взяли? Поклонники прислали... Странно, здесь одна ячейка неплотно прилегает Да это тайник, а в нем записка: За один ход разрешается осуществлять одновременную перекраску любой клетки гексагональной шахматной доски и всех клеток, имеющих с ней общую сторону, с такой заменой цветов: белый желтый черный белый. Можно ли за несколько ходов перекрасить все клетки доски в белый цвет? На дуалистов не похоже, три цвета, все-таки. Что скажете, агент Скалли? Да, агент Малдер, это не дуалисты, это плюралисты!

Рис. 2

Упражнения
1. Найдите последовательность ходов, перекрашивающую в противоположный цвет: a) цилиндрическую шахматную доску, склеенную из доски 8 Ч 8 (рис.3,а); б) тороидальную шахматную доску, склеенную из доски 8 Ч 8 (рис.3,б); в) доску в форме листа Мебиуса, склеенную из доски 8 Ч 8 (рис.3,в).

Рис. 3

Нарисуйте соответствующие графы. 2. За один ход разрешается одновременно перекрасить в противоположный цвет любую клетку доски, а также все клетки, в которые можно попасть из нее ходом коня. Найдите последовательности ходов, перекрашивающие в противоположный цвет клетки квадратных досок размеров 3 Ч 3 , 4 Ч 4 , и постройте соответствующие графы. 3. Приведите пример раскраски некоторой трехцветной гексагональной доски, все клетки которой нельзя перекрасить в один цвет. 4. Решите сформулированную в статье задачу для доски Глинского. Как, зная решение, при котором все клетки доски Глинского перекрашиваются в белый цвет, получить решение, при котором все клетки доски Глинского перекрашиваются в черный цвет? 5. Докажите, что если для произвольной трехцветной гексагональной доски соответствующее решение существует, то число этих решений является целой неотрицательной степенью числа 3.