Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?work=106 Дата изменения: Fri May 5 15:25:18 2006 Дата индексирования: Tue Oct 2 02:38:51 2012 Кодировка: koi8-r Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п п

Сушко Д.В.

Кольцо фигур на целочисленной решетке


1. Основные определения.

Рассмотрим клетчатую плоскость, т.е. множество квадратов со стороной 1
и целыми координатами (координатами квадрата будем называть декартовы
прямоугольные коор-динаты его левого нижнего угла). Эти квадраты будем
называть элементами нашей клетчатой плоскости. Каждый из них может
находиться в одном из 2-х состояний : быть закрашенным ( этому состоянию
соответствует 1) , или незакрашенным ( этому состоя-нию соответствует 0).
Фигура - основной объект исследования - это совокупность состояний всех
элементов целочисленной решетки (клетчатой плоскости). Мы будем
рассматривать только конечные фигуры, т.е. фигуры с конечным числом
закрашенных элементов. На рис.1 приведены примеры конечных фигур ( буквой
О помечен квадрат с координатами (0,0)).
[pic]
Фигуру, у которой нет закрашенных элементов, будем называть нулем и
обозначать 0, фигуру с единственным закрашенным элементом (0,0) будем
называть единицей и обозначать 1.
Фигуры будем называть равными , если все их соответствующие (т.е.
имеющие одинаковые координаты) элементарные фигуры ( квадратики )
находятся в одинако- вых состояниях и неравными в противном случае.

Суммой фигур а и b назовем фигуру с, состоящую из элементов,
состояние кото- рых определяется как сумма по модулю 2 состояний
соответствующих элементов фигур а и b. При этом а + а = 0. На рис.2
приведен пример сложения.
[pic]
Элементарным вектором фигуры а назовем вектор с началом в центре
квадрата с координатами (0,0) и концом в центре какого-либо закрашенного
квадрата фигуры а. Тогда фигура полностью определяется множеством всех ее
элементарных векторов. Для двух фигур а и b рассмотрим мультимножество
(т.е. множество, где каждый элемент встречается произвольное число раз),
каждый элемент которого - вектор, равный сумме какого-то элементарного
вектора фигуры а и элементарного вектора фигуры b. Из полученного множества
исключаем пары одинаковых векторов до тех пор, пока это возможно.
Получается множество векторов с началом в 0 и концами в центрах цело-
численной решетки. Это множество элементарных векторов для фигуры с,
которую и назовем произведением фигур а и b. Эквивалентный способ,
используемый на практике: а(b равно сумме всех фигур, получающихся из а
сдвигом на элементарные векторы фигуры b. На рис.3 приведен пример
умножения.

[pic]
Нетрудно убедиться, что введенные операции коммутативны и
ассоциативны, ум- ножение дистрибутивно относительно сложения. Кроме того,
a + 0 = a, a • 1 = a, a + a = 0 для любого a. При этом вычитание
эквивалентно сложению. Таким образом, множество конечных фигур является
кольцом. Обозначим его Zf.





2. Дополнительные определения и
обозначения.
Обозначим количество закрашенных элементов фигуры А через #А.
при a ( 0 размером фигуры S(а) вдоль Ox будем называть разность R -
L, где R - наибольшая х-координата закрашенного элемента фигуры а, а L -
наименьшая х-ко-ордината. Аналогично определяется размер вдоль другой оси.
Нетрудно видеть, что имеет место равенство S (а(b) = S (а) + S (b), где
а и b - ненулевые фигуры.

Проекцией ах фигуры а на ось Ox будем называть фигуру, у которой
элемент с ко- ординатами (т,0) закрашен тогда и только тогда, когда в
фигуре а нечетное коли-чество закрашенных элементов имеют х-координату
т. Все остальные элементы незакрашены. Аналогично, проекцией ay фигуры a
на ось Оy назовем фигуру, у которой элемент (0,п) закрашен лишь тогда,
когда в фигуре a есть нечетное количество закра-шенных элементов с y-
координатой п, а все другие элементы не закрашены (см. рис. 4).

[pic]
Имеют место равенства (а(b)х = ах(bх , (а + b)х = ах + bх (и то
же для Oу).

Единичной фигурой будем называть фигуру, у которой закрашен лишь один
квадратик.
Фигурами одинакового вида будем называть фигуры, получающиеся друг из
друга умножением на единичную. Фактически, эти фигуры отличаются сдвигом на
вектор с целочисленными координатами.
Будем говорить, что фигура а делится на фигуру b, если существует
такая конечная фигура с, что а = b(с. При этом b и c назовем делителями a
и будем писать a ( b ( a ( c). Кроме того, b = a/c, c = a/b.
Простой назовем такую неединичную фигуру р, делителями которой
являются лишь единичные фигуры и фигуры одинакового с р вида.
Введем также обозначения для некоторых наиболее часто используемых
нами фигур. Закрашенный прямоугольник 1(n, расположенный вдоль оси Ох будем
обозначать [n], (при этом мы предполагаем, что его левый край - квадрат
(0, 0)).Такой же прямоуголь- ник, но расположенный вертикально, будем
обозначать{n}. Квадрат n(n c левым ниж-ним углом (0,0) обозначим [pic]
(cм. рис.5).

[pic]

3. Основные результаты.

Основным результатом работы является следующая теорема (аналог
основной теоре-мы арифметики).

Теорема 1. Каждая неединичная фигура разлагается в произведение
простых фигур, причем единственным образом.
(Разложения мы рассматриваем с точностью до фигур одинакового вида,
например варианты на рис.6 - одно и то же разложение).
[pic] Доказательство.
Докажем существование разложения.
Либо фигура а простая, либо у нее есть делитель d. Для а/d
справедливо то же самое и т.д., причем :

Sх(а) + Sу(а) = Sх(а/d) + Sу(а/d) + Sх(d) +
Sу(d)
Пусть L(а) = Sх(а) + Sу(а) . Тогда имеем : L(а) = L(а/d) + L(d),
L(а/d) < L(а), поскольку L(d)>0.


Так как L(а) - конечное целое число и уменьшается оно каждый раз не
меньше, чем на 1, то процесс конечен, и разложение получено.
Докажем единственность разложения.

Кольцо Zf оказывается неевклидовым, поэтому ввести норму и
доказать теорему так, как это делается для целых чисел не удается. Поступим
по-другому.
Заметим, что можно рассматривать разложения только в 1-й
четверти: х[pic]0, у[pic]0. Действительно, пусть мы доказали теорему для
этой четверти. Допустим, что существует фигура А, которая имеет два (или
больше) различных разложения. Легко видеть, что существует такая единичная
фигура (, что фигура (А и все простые разложения А лежат в 1-й четверти.(
Действительно, пусть n - наибольшее количество простых фигур в разложениях,
d - единичная фигура, такая, что самый удаленный от квадрата (0,0)
делитель А(d перемещается в 1-ю четверть. Тогда (dn- искомый элемент). Все
получив-шиеся делители - различного вида, значит, мы получили два
разложения для (А, чего быть не может по предположению. Итак, достаточно
доказать теорему для 1-й четверти.
Пусть (х - единичная фигура с координатами (1,0). Для любой фигуры А
положим, как всегда, Аn = [pic], А0= l. Тогда легко видеть, что (хn есть
единичная фигура c за-крашенным элементом (n,0) (короче, (хn = (n,0)).
Аналогично, (у = (0,1); (уn = (0,n). Тогда любая фигура в 1-й четверти
представляется в виде [pic]аij (хi (уj, где аij - единица, если квадрат
(i,j) в фигуре А закрашен, и ( - если не закрашен. Нетрудно видеть, что
полученные суммы перемножаются и складываются точно как многочлены от (х
и (у с коэффициентами из поля , состоящего из 0 и 1 с умножением и
сложением по модулю 2. Легко убедиться, что фигура будет простой в том и
только том случае, если соот-ветствующий многочлен неприводим.
Осталось сделать последний шаг - известно, что кольцо многочленов
от 2-х пере-менных факториально, т.е. в нем справедлива теорема,
аналогичная теореме 1. Значит, эта теорема справедлива и для фигур (с
учетом результата предыдущего абзаца).

Сформулируем два следствия из основной теоремы:
Следствие 1. Если ab ( c, и b взаимно просто с c (т.е. b и c не имеют
общих делителей, кроме единичных фигур), то a ( c.
Следствие 2. Если a ( b, a ( c и b взаимно просто с c, то a ( bc.
Следующая теорема выражает одно из свойств делимости фигур и полезна
для реше-ния задач.

Теорема 2. Пусть все закрашенные квадраты фигуры А имеют у -
координату 0. Тог-да, если число закрашенных элементов фигуры А делится на
2, то сама фигура делится на [2] (и наоборот).



Доказательство. Легко проверяется, что

#(А + В) = #А + #В (mod 2), #(А(В) = #А (
#В (mod 2) .
Итак, пусть #А ( 2. Сложим А с фигурой одного вида с [2], причем
так, чтобы правый конец [2] совпадал с самой правой элементарной фигурой А
(рис 7).
[pic][pic]
Поскольку #(А + В) = #А + #В (mod 2), то полученная фигура А( также
содержит четное число закрашенных квадратов. И если Sх( А) > 1, Sх(А() <
Sх(А). С А можно проделать ту же операцию и т.д. Но Sх(А)-натуральное
число, поэтому убывание должно когда-либо остановиться. Это случится тогда,
когда очередная фигура будет иметь размер Sх ( 1. Но т.к. #А ( 2, то это
может быть только [2] или 0. Т.к. на каждом шаге мы прибавляем кратное [2],
а результат также кратен [2] (т.к. это или 0 или [2] ), то и первоначальная
фигура А кратна [2]. Обратное утверждение очевидно ( #( В([2] ) ( 2(#В (
0(mod 2)).
Аналогичный результат можно доказать и для вертикальных фигур (т.е.
тех, у кото-рых все закрашенные элементы имеют х-координату 0) - если #А
( 2, то А ( {2}.

Следствие. Если у фигуры А каждый столбец (т.е. множество единичных
элементов, имеющих фиксированную х-координату) содержит четное число
закрашенных клеток, то фигура А кратна {2}.

По теореме 2 каждый столбец кратен {2}, их сумма - фигура А тоже
кратна {2}. Аналогичный результат имеет место для [2] и строк. Так как

(а + b)2 = (а + b)(а + b) = а2 + а(b + b(а + b2 = а2 + b2 ,
и (а1 + а2 + ...+аn )2 = а12 + а22 +... + аn2 ,
то x2 получается из х следующим образом : координаты каждого закрашенного
элемен- та[pic]удваиваются (т.к. ( (xi (уj )2 = (x2i (у2j ). Из этого
следует, что [2m] = [2]([m]2,
[2n] = [2][pic].

4. Решение задач.

Построенный нами аппарат эффективно применяется при решении задач,
связанных с разрезаниями, замощениями и раскрасками (собственно, для этого
он и был построен).
Приведем решения некоторых задач этого класса.

Задача 1. Докажите, что шахматную доску 8(8 нельзя замостить 15
прямоугольни-ками 1(4 и одной фигуркой L- тетрамино рис. 8.

Решение. Достаточно доказать, что фигура в виде закрашенного квадрата
8(8 не может быть представлена в виде суммы фигурок вида [4], {4} и фигуры
L (рис.8). Допустим, что это возможно. Тогда [8]({8}= [pic]7 (А([4] + В({4}
+ L ,где А[pic]и В - некоторые конечные фигуры. Под L мы подразумеваем
фигуру одного вида с той, что изображена на рис.8, или повернутую на 90(
фигуру. Но мы всегда можем повернуть и отразить квадрат 8(8 так, чтобы
фигура оказалась именно в том положении, как на рис.7. Итак, пусть [pic]7
= А([4] + +В({4}+ L. Спроецируем это равенство на ось Ох : 0 = Ах
([4] + (хn ([2], где n - некоторое целое число. Так как делителей нуля в
Zf нет, то можно заключить, что 0 = (xn + Ах([2]2. Но этого не может
быть, т.к. левая часть равенства делится на [2], а правая - нет. Значит,
действительно, искомое замощение невозможно.
[pic]



Задача 2. Можно ли квадрат 10(10 замостить прямоугольниками 1(4 ?


Решение. Допустим, это возможно. Тогда [10]({10} = А([4] + В({4}, где
А и В - неко-торые фигуры. Иначе, [pic]([pic]2 = А([4] + В({4}. А([4] (
[2], [pic]([pic]2 ( [2], значит В({4}( [2], следовательно, В ( [2] (т.к.
{4} взаимно просто с [2] - следствие из теоремы 1).
Пусть В = В([2] . [pic]([pic]2 = А([4] + В(([2]({4}. На [2] можно
сократить : {2}([pic]2 = А([2]2+В(({4}. Аналогично можно
заключить, что А ( {2}, А = А(({2}. Тогда равенство принимает вид: [pic]2
= А(([2]2 + В(({2}2. Но это невозможно, поскольку #[pic]2 (
#[5](#{5}=25(mod 2) , а #(А(([2]2 + В(({2}2 ) ( #А((2 + #В((2 ( 0 (
25(mod 2). Таким образом, квадрат 10(10 нельзя замостить фигурами 1(4.

Можно было достичь того же результата, если спроецировать
последнее равенство сначала на ось Ох, а затем на ось Оу. Результат этой
задачи верен и для любого прямоугольника, если ни одна из его сторон не
делится на 4.

С одной стороны, этот метод дает для подобных задач больше, чем
требуется, т.к. он доказывает не только невозможность прямого замощения,
но и невозможность замощения с наложениями по модулю 2. Однако некоторые
задачи не решаются таким способом, как задачи 1 и 2. Рассмотрим,
например, задачу 3.

Задача 3. Докажите, что доску 10(10 нельзя замостить фигурками Т-
тетрамино рис.9.

Решение. Сначала будем пытаться доказать, что доска 10(10 не может
быть линейной комбинацией фигуры рис.9 и ее поворотов и отражений. Такие
попытки не приводят к цели, поскольку такая комбинация существует. На
рис.10 приведена комби-нация, результат которой - домино 1(2 (или [2] ).
Аналогично можно получить {2}. Поскольку квадрат 10(10 кратен этим фигурам,
то и его можно получить в таком виде.
[pic]
Для решения подобных задач нужно применять другие соображения. В
этой задаче легко заметить, что количество фигур будет равно 25. Проекция
на ось Ох каждой фигуры есть [2]2 или [2] (фигура одного вида с одним из
примеров). Количество первых пусть будет А, а вторых В. Тогда в проекции
на ось Ох имеем : 0 = Ах [2]2 + Вх[2], где Ах и Вх - некоторые фигуры на
оси Ох. Иначе, Ах ([2] + Вх = 0. В проекции на ось Оу фигура типа А дает
проекцию типа [2], а фигура типа В - проекцию [2]2 (наоборот оси Ох ).
Имеем : Ау + Ву[2]=0. Сложим последние равенства. Имеем : Вх + Ау +(Ах
+Ву)([2] = 0. Но очевидно, что #Вх ( #В(mod 2), #Ау ( А(mod 2).
С другой стороны, #(Ах + Вy )([2] ( 0(mod 2). Тогда А+В ( 0(mod 2),
что невозможно, т.к. А + В = 25 (общее количество фигур). Значит, требуемое
замощение невозможно.


Задача 4. В таблице 8(8 одна из клеток закрашена черным цветом, все
остальные - белым. Докажите, что с помощью перекрашивания строк и столбцов
нельзя добиться того, чтобы все клетки стали белыми. Под перекрашиванием
строки или столбца понимается изменение цвета всех клеток в строке или
столбце.

Решение. Из определения сложения фигур следует, что перекрашивание
строки (столбца) есть сложение с закрашенной строкой (столбцом). Значит,
нам нужно дока-зать, что равенство 1 = А([8] + В({8} невозможно ( начало
координат поместим таким образом, что закрашенный элемент имеет координаты
(0,0)). Спроектируем равенство на ось Ох. Имеем : 1 = Ах([8], что
невозможно. Задача решена.


Задача 5. Решить ту же задачу, если исходно в черный цвет покрашены 4
угловые клетки.

Решение. Нетрудно видеть, что первоначально закрашенная фигура -
это[pic]([pic]. Таким образом, нужно доказать, что равенство [pic]([pic] =
А([8] + В({8} невозможно. Имеем : [pic]([pic] = А([2]7 + В({2}7
.Отсюда следует, что В ( [2], В = В(([2].Сокращая на [2], получим
{2}([pic] = А([2]6 + В(({2}7( А = А(({2}.Получаем : [pic] = А(([2]6 +
В(({2}6,что невозможно , т.к. #[pic] = 49 ( #(А(([2]6 + В(({2}6) .

Обычно применение метода нацелено на доказательство невозможности
чего-ли- бо, однако с его помощью можно получить и положительные
результаты.

Задача 6. Некоторые клетки бесконечного клетчатого листа покрашены в
черный цвет, а все остальные - в белый, как показано на рис.11.
Разрешается поменять цвета на противоположные у любых четырех клеток,
образующих квадрат 2(2. Можно ли за несколько таких операций добиться того,
чтобы все клетки стали белыми?
[pic]
Решение. Очевидно, каждая операция есть сложение фигуры с [pic]. В
каждой строке фигуры четное число клеток. По следствию из теоремы 2 эта
фигура делится на [2]. В каждом столбце также четное число закрашенных
клеток. Значит, эта фигура делится на {2}. Т.к. фигуры [2] и {2} взаимно
просты, то фигура рис.11 делится на их произведение, т.е. на [pic] .
Значит, получить белую плоскость можно.

Теперь три более сложные задачи.

Задача 7. Дно прямоугольной коробки вымощено плитками 1(4 и 2(2.
Плитки высыпали из коробки и одна плитка 2(2 потерялась. Ее заменили на
плитку 1(4. Докажите, что теперь дно коробки вымостить не удастся.


Решение. Пусть S - фигура, соответствующая дну коробки. Пусть S =
А([4] + В({4} + C([pic]. Тогда Sх = Ах([4], Sу = Ву([4] и[pic][pic]Ах +
Ву. При этом #Ах + #Ву ( #А + #В ( N4(mod 2), где N4 - число плиток 1(4.
Итак, если S вымощено плитками 1(4 и 2(2, то #[pic] ( N4 (mod 2). При
замене плитки 2(2 на плитку 1(4[pic]количество последних увеличилось на 1,
хотя #[pic] не поменялось. Поэтому замостить S снова не удастся, так как
N4 (mod2) поменялось.



Задача 8. В таблице 10(10 все клетки левой половины доски окрашены в
черный цвет, остальные - в белый. Разрешается за ход менять цвет всех
клеток в любой строке и в любом столбце. Можно ли при помощи нескольких
таких операций добиться шахматной раскраски?


Решение. Каждая операция - сложение с [10] или {10}.Нетрудно видеть,
что начальное состояние - [5]{2}{5}2, а конечное - [5]2{5}2. Если возможно
сделать то, что требуется в условии задачи, то сумма этих фигур должна
представляться в виде А([10] + В({10}, или А([2][5]2 + В({2}{5}2 .
Итак, пусть [5]{2}{5}2 + [5]2{5}2 = А([2][5]2 + В({2}{5}2 . Тогда
А делится на {5}2, А =А(({5}2 , а В = В(([5]. Подставляя эти значения,
а затем сокращая на [5]{5}2 получим : {2}+ [5] = А(([2][5] + В(({2}.
Спроецируем это равенство на ось Ох : [5] = А(х ([2][5]; или 1 = А(х
([2], что невозможно (у единицы нет делителей, кроме единичных фигур). Зна-
чит , добиться шахматной раскраски нельзя.


Задача 9. (Эта задача М 1264( из "Задачника Кванта" ? 1-1991).
На бесконечном белом листе клетчатой бумаги квадрат 2(2 клетки нужно
закрасить в черный цвет. Можно ли это сделать несколькими операциями,
каждая из которых - перекрашивание в противоположный цвет всех клеток в
квадрате 3(3 или 4(4 ?

Решение. Задача сводится к решению уравнения [pic] = а[pic] + b[pic]
в конечных фигурах. Заметим, что [pic] = [pic]3.Т.к. [pic], [pic] делятся
на [pic], то и а[pic] ( [pic]. Так как [pic] и [pic] - взаимно простые
фигуры, то а = а([pic]. Уравнение принимает вид 1 = а([pic] + b[pic]2 .
Проецируем это равенство на ось Ох : 1 = а(х [3]. Поскольку это равенство
невозможно ( у единицы нет делителей), то и ответ к задаче отрицательный.




Литература.

1. Курош А.Г. Курс высшей алгебры. - М.: Наука, 1975.
2. Общая алгебра. Т.1/ О.В. Мельников, В.Н. Ремесленников, В.А.
Романьков и др. // Под общ.ред. Л.А. Скорнякова - М.: Наука, 1990.
3. Оре О. Приглашение в теорию чисел. - М.: Наука, 1980.