Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?thesises=106 Дата изменения: Fri May 5 15:24:30 2006 Дата индексирования: Tue Oct 2 03:48:10 2012 Кодировка: koi8-r Поисковые слова: arp 220

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

Суммой фигур а и b назовем фигуру с, состоящую из элементов,
состояние которых определяется как сумма по модулю 2 состояний
соответствующих элементов фигур а и b. При этом а + а = 0.
Элементарным вектором фигуры а назовем вектор с началом в центре
квадрата с координатами (0,0) и концом в центре какого-либо закрашенного
квадрата фигуры а. Тогда фигура полностью определяется множеством всех ее
элементарных векторов.
Для двух фигур а и b рассмотрим мультимножество (т.е. множество, где
каждый элемент встречается произвольное число раз), каждый элемент которого
- вектор, равный сумме какого-то элементарного вектора фигуры а и
элементарного вектора фигуры b. Из полученного множества исключаем пары
одинаковых векторов до тех пор, пока это возможно. Получается множество
векторов с началом в 0 и концами в центрах целочисленной решетки. Это
множество элементарных векторов для фигуры с, которую и назовем
произведением фигур а и b. Эквивалентный способ, используемый на практике:
а(b равно сумме всех фигур, получающихся из а сдвигом на элементарные
векторы фигуры b.
Нетрудно убедиться, что введенные операции коммутативны и ассоциативны,
умножение дистрибутивно относительно сложения. Кроме того, a + 0 = a, a • 1
= a, a + a = 0 для любого a. При этом вычитание эквивалентно сложению.
Таким образом, множество конечных фигур является кольцом. Обозначим его
Zf.
Проекцией ах фигуры а на ось Ox будем называть фигуру, у которой
элемент с координатами (m,0) закрашен тогда и только тогда, когда в
фигуре а нечетное количество закрашенных элементов имеют х-координату
m. Все остальные элементы незакрашены. Аналогично, проекцией ay фигуры a
на ось Оy назовем фигуру, у которой элемент (0,n) закрашен лишь тогда,
когда в фигуре a есть нечетное количество закрашенных элементов с y-
координатой n, а все другие элементы не закрашены. Имеют место равенства
(а(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].

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


Теорема 1. Каждая неединичная фигура разлагается в произведение простых
фигур, причем единственным образом.


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

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

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

Данный метод позволяет решать многие задачи этого класса.

Имеются результаты в исследовании аналога рациональных чисел -
отношения целых фигур. Открылись красивые связи с другими вопросами
математики, в частности - с фракталами.
Теория имеет обобщение на случай n-мерных пространств и клеточных
пространств с числом состояний больше двух.

Более подробно познакомиться с результатами исследований и их
приложениями Вы можете в полном тексте работы.