Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.eng.math.msu.su/download/Russian_articles_for_rendering.pdf Дата изменения: Mon Oct 3 01:13:25 2011 Дата индексирования: Sat Apr 9 22:27:15 2016 Кодировка: Windows-1251

ї

НОЯБРЬ ДЕКАБРЬ

Ю

НАУЧНО-ПОПУЛЯРНЫЙ

ФИЗИКО-МАТЕМАТИЧЕСКИЙ

?6
ЖУРНАЛ

ИЗДАЕТСЯ С ЯНВАРЯ 1970 ГОДА

В номере: # !
Учредитель Российская академия наук Издатель ООО НПП ОО 'Бюро Квантум'
ГЛАВНЫЙ РЕДАКТОР

Над пожаром самолет. В.Вышинский, М.Кудров, А.Стасенко Разбиения на домино и функции высоты. Е.Карпов, К.Кохась О муарах, оживших иллюстрациях и пользе моделей. З.Пятакова, А.Пятаков ЗАДАЧНИК 'КВАНТА' Задачи М2199М2205, Ф2205Ф2212 Решения задач М2176М2183, Ф2190Ф2195 О покрытии целых чисел прогрессиями КМШ Задачи Конкурс имени А.П.Савина 'Математика 68' Летний турнир имени А.П.Савина. КАЛЕЙДОСКОП 'КВАНТА' Стереометрия для всех ШКОЛА В 'КВАНТЕ' Метод изогональных прямых. И.Кушнир МАТЕМАТИЧЕСКИЙ КРУЖОК Чудеса инверсии. Т.Емельянова ЛАБОРАТОРИЯ 'КВАНТА' Электричество из фруктов. Э.Марчук ПРАКТИКУМ АБИТУРИЕНТА Движение заряженных частиц в магнитном поле. А.Черноуцан ОЛИМПИАДЫ LI Международная математическая олимпиада XLI Международная олимпиада школьников по физике ИНФОРМАЦИЯ Очередной набор в ОЛ ВЗМШ Федеральная заочная физико-техническая школа при МФТИ Новый прием в школы-интернаты при университетах Конкурс 'Свободный полет' в 2011 году Ответы, указания, решения Напечатано в 2010 году Памяти А.Р.Зильбермана (25) НА ОБЛОЖКЕ

% ' # % & & ! !# !% !& " "" "# "' ## #& #' $ $!

В.В.Козлов
ПЕРВЫЙ ЗАМЕСТИТЕЛЬ ГЛАВНОГО РЕДАКТОРА

С.С.Кротов
РЕДАКЦИОННАЯ КОЛЛЕГИЯ

А.Я.Белов, Ю.М.Брук, А.А.Варламов, А.Н.Виленкин, В.И.Голубев, С.А.Гордюнин, Н.П.Долбилин (заместитель главного редактора), В.Н.Дубровский, А.А.Егоров, А.В.Жуков, А.Р.Зильберман , П.А.Кожевников, С.П.Коновалов, А.А.Леонович, Ю.П.Лысов, В.В.Произволов, Н.Х.Розов, А.Б.Сосинский, А.Л.Стасенко, В.Г.Сурдин, В.М.Тихомиров, В.А.Тихомирова, В.М.Уроев, А.И.Черноуцан (заместитель главного

редактора)

РЕДАКЦИОННЫЙ СОВЕТ

А.В.Анджанс, М.И.Башмаков, В.И.Берник, В.Г.Болтянский, А.А.Боровой, Н.Н.Константинов, Г.Л.Коткин, С.П.Новиков, Л.Д.Фаддеев
РЕДАКЦИОННАЯ КОЛЛЕГИЯ 1970 ГОДА ГЛАВНЫЙ РЕДАКТОР

И.К.Кикоин
ПЕРВЫЙ ЗАМЕСТИТЕЛЬ ГЛАВНОГО РЕДАКТОРА

А.Н.Колмогоров
Л.А.Арцимович, М.И.Башмаков, В.Г.Болтянский, И.Н.Бронштейн, Н.Б.Васильев, И.Ф.Гинзбург, В.Г.Зубов, П.Л.Капица, В.А.Кириллин, Г.И.Косоуров, В.А.Лешковцев, В.П.Лишевский, А.И. Маркушевич, М.Д.Миллионщиков, Н.А.Патрикеева, Н.Х.Розов, А.П.Савин, И.Ш.Слободецкий, М.Л.Смолянский, Я.А.Смородинский, В.А.Фабрикант, Я.Е.Шнайдер
Товарный знак 'Журнал 'Квант' является собственностью ООО НПП ОО 'Бюро Квантум' ї 2010, РАН, журнал 'Квант'

I II III IV

Иллюстрация к статье З.Пятаковой и А.Пятакова Коллекция головоломок Шахматная страничка Прогулки с физикой Этот номер журнала 'Квант' вышел при финансовой поддержке компании The McGraw-Hill Companies

01-16.p65

1

23.12.10, 15:26

2010


Над пожаром самолет
В.ВЫШИНСКИЙ, М.КУДРОВ, А.СТАСЕНКО

'Т

хотою небывалой, //И солнце даже в полдень было ало' (Н.Гумилев). В таких условиях высока вероятность страшных лесных пожаров. Вот художественное описание одного из них: 'Огонь шел торопливой, рокочущей лавиной, бешено неся всему смерть. Деревья, будто собираясь бежать, пытались сорваться с места, раскачиваясь и тревожа корни. Но тщетно гудели они вершинами, тщетно роняли смолистые слезы. Еще мгновение и враз вспыхивает, подобно оглушительному взрыву, целая стена ужаснувшихся деревьев, с треском одеваются хвои в золото, и все тонет в огне. Дальше и дальше, настойчиво и властно плывет пылающая лава, и нет сил остановить ее' (из повести 'Тайга' В.Я.Шишкова). Оказывается, сила, способная остановить пожар, есть. Это авиация. И действительно, кто кроме противопожарного самолета сможет за несколько секунд набрать десяток тонн воды из реки, озера или моря и сбросить их на пылающую полосу леса с безопасной высоты? Конечно, чем больше высота, тем безопасней. Но если забраться слишком высоко то что долетит до земли? Рассеянное облако капель? Благодаря многолетнему опыту уже выработана минимальная норма: для тушения крупного лесного пожара перед его фронтом нужно создать полосу орошения порядка десяти метров шириной, причем на каждый квадратный метр площади орошения должен выпасть примерно один литр воды. Понятно, что существует оптимальная высота работы самолета такая, что, с одной стороны, ширина падающей массы воды успеет вырасти до десяти метров за счет деформации и дробления ее первоначального объема, а с другой еще не вся масса превратится в капли, легко уносимые ветром. Можно оценить и длину полосы орошения. Если самолет сбросит, например, три тонны воды (или 3 10 3 л), то при норме поверхностной плотности 1 л м2 и требуемой ширине полосы 10 м получим длину порядка 300 м. Но это если бы вся вода долетала до этой полосы и оседала равномерно. А если долетает только половина, то эта длина сокращается вдвое, а если треть, то И тут уже нужно строить физикоматематическую модель процессов, происходящих со сброшенной водой. Для начала обратимся к эксперименту. В летных условиях трудно что-либо измерить внутри падающей массы воды (разве что посадить туда аквалангиста с парашютом и приборами). Однако, кое-что дают и внешние впечатляющие киносъемки (рис.1). Прежде

О ЛЕТО БЫЛО ГРОЗАМИ ПОЛНО,/ ЖАРОЙ И ДУ-

Рис. 1. Противопожарный самолет, сбрасывающий воду

всего, видно, что жидкость через некоторое время после 'выпадения' из люка распадается на части (рис.2). Этот распад происходит из-за воздействия набегающего (со скоростью u0 ) потока воздуха, который сплющивает жидкость в поперечном направлении.

Рис. 2. Дробление жидкости при падении на землю

Жидкость дробится на части на расстоянии порядка 10 м по вертикали от самолета. В этот момент скорость падения жидкости составляет приблизительно 10 м/с, а горизонтальная скорость относительно земли почти равна скорости самолета.

01-16.p65

2

23.12.10, 15:26


НАД

ПОЖАРОМ



САМОЛЕТ

!

Конечно, в этом процессе 'почти вертикального' падения происходит интенсивный сдув поверхностного слоя воды. Экспериментаторы установили, что до момента дробления основного объема жидкости в виде капель уже потеряны 2030% от начальной массы. В результате образуется широкий спектр размеров 'кусков' воды от крупных фрагментов, продолжающих разрушаться под напором воздуха, до мелкой водяной пыли, далеко простирающейся за самолетом, которая будет унесена ветром или восходящим горячим потоком от пожара. Разумеется, нас прежде всего интересует судьба тех фрагментов первоначальной массы воды, которые должны попасть в нужное место на поверхности земли. Это похоже на проблему бомбометания, которая была решена изобретением приборов, учитывающих скорость и высоту полета, ветер, а также расстояние до цели. Только в рассматриваемом случае 'бомба' имеет переменную массу и непредсказуемую форму. А как заманчиво было бы сделать этакое бортовое устройство, которое вычисляло бы, с учетом всех определяющих факторов, тот момент, когда нужно нажать кнопку сброса воды. Или еще лучше чтобы оно само нажало такую кнопку. В принципе, современный уровень развития аэрогидродинамики позволяет численно решить такую задачу, да вот беда долго ждать, пока даже самые современные компьютеры проведут вычисления. Но попробуем исследовать отдельные черты явления, пользуясь теми подсказками, которые уже представил нам летный эксперимент. Прежде всего, выделим в струе воды, вытекающей из самолета, горизонтально-плоский фрагмент воды, который первоначально имел форму прямоугольного люка. Рассматриваемая нами жидкость обдувается встречным потоком воздуха. Используя современный пакет программ численного исследования, получим

характерную картину (рис.3), соответствующую определенному моменту времени. В нашем случае выбраны скорость полета u0 = 70 м с и момент времени t = = 0,27 с. Конечно, на рисунке приведена только половина 'вида сверху' этого слоя (в целях экономии места) поскольку имеется вертикальная плоскость симметрии. Под рисунком приведена принятая декартова система координат: ось х направлена вдоль скорости 'обдува' слоя воды (она равна скорости полета с противоположным знаком), ось z перпендикулярна ей и лежит в горизонтальной плоскости, ось y вертикальна. Здесь же дана цветная оцифровка значений скорости и геометрический масштаб. Стрелками показано направление скоростей воздуха. Видны истонченные концевые области сильно деформированного 'прямоугольника', с которых должны особенно интенсивно срываться более мелкие фрагменты и капли. За бывшим прямоугольником видно образование вихрей, которые способствуют удержанию капель вблизи падающей массы воды. Но эта модель плоского слоя предполагает, что ктото насильно удерживает воду между двумя фиксированными плоскостями. В реальности уже через короткий промежуток времени оставшаяся масса воды будет сплющена набегающим потоком воздуха и станет скорее похожа на вертикальный блин, который далее развалится на части; эти части, в свою очередь, сплющатся и развалятся и так далее вплоть до падения на землю или полного распыления на мелкие капли (в случае очень большой высоты полета). И тут возникает другая модель постадийного дробления (см. рис.2). Пусть на некотором этапе процесса его номер j водяной фрагмент имеет форму шара радиусом rj . Сплющиваясь под напором воздуха, он превращается в блин (по-научному, эллипсоид вращения) с отношением осей x y = 110 , после чего

Рис. 3. Распределение скорости и образование вихря в падающем фрагменте воды

01-16.p65

3

23.12.10, 15:26


"
распадается на две части, каждая из которых снова принимает форму шара, теперь уже rj радиусом rj +1 = 3 , и так да2 лее. Тот факт, что в знаменателе стоит
3

КВАНT 2010/?6

2 , соответствует

предположению о достаточно малом времени распада j-фрагмента на два (j + 1)-фрагмента, в течение которого срыв капель пренебрежимо мал: m j = 2 m j +1 , или rj3 = 2 rj3+1 . Но между двумя последоваРис. 4. Поверхностное распределение выпавшей жидкости тельными дроблениями изменяются и масса m, и горизонвакууме (когда воз = 0 ): u = u 0 (постоянная скотальная скорость u, и вертикальная скорость v падарость полета), v = - g t . Отсюда для траектории полующего фрагмента, и, конечно, его форма фрагмент чаем уравнение параболы (в параметрическом виде) стремится принять форму блина для последующего g t2 распада на два (j + 2)-фрагмента. x = x 0 + u 0 t, y = y0 - (здесь x0 начальная 2 Строго описать все это можно, но сложно. Поэтому абсцисса сброса массы, y0 высота 'полета'). используем приближенные соотношения, получаемые из соображений размерности. Далее, из второго уравнения (для v) видно, что если Уравнения второго закона Ньютона в проекциях на тело постоянной массы уронить с нулевой начальной оси х, у примут вид (здесь индекс j опущен) скоростью (u 0, V v) , то при t достигается du = -CS uV mg . m , воз конечная скорость падения v =- Отсюда dt CSвоз
m dv dt -mg - CS
воз

vV ,

где V = u2 + v2 модуль скорости падения фрагмента, воз плотность воздуха, S поперечное сечение тела, C безразмерный коэффициент, так называемый коэффициент сопротивления. А что же происходит с массой воды? Примем, что скорость ее изменения во времени зависит от модуля скорости обдува, площади поперечного сечения и плотностей воздуха воз и самой воды воды :
dm -VS воз воды , dt где , как и C, безразмерный коэффициент. Знак 'минус' в правой части первых двух уравнений указывает на то, что сила, действующая со стороны воздуха, противоположна по направлению соответствующей компоненте скорости тела относительно воздуха (за это сила и называется силой сопротивления). А в третьем уравнении знак 'минус' указывает на то, что масса убывает со временем. Конечно, приведенная система уравнений не является результатом строго вывода. Но что поделать даже великие физики говорят, что ' если мы хотим, чтобы от науки была какая-то польза, мы должны строить догадки, а если вы думали, что наука достоверна, вы ошибались' (Р.Фейнман). А польза безусловно есть. Прежде всего, проанализируем эту систему уравнений. В частности, из первых двух уравнений (для u и v) получается точное решение для случая падения тела в

понятно, почему парашюты должны иметь большую площадь (S в знаменателе!). Разумеется, эту систему обыкновенных дифференциальных уравнений нужно решать численно, что вполне доступно бортовому компьютеру в летных условиях. Надо только подобрать подходящие значения безразмерных коэффициентов С и из сравнения заранее проведенных экспериментов с результатами расчета. Проделав такую работу, можно быстро предсказать распределение выпавшей на почву жидкости. Один из таких расчетов приведен на рисунке 4 для следующих условий: u 0 = 70 м с , y0 = 40 м . Здесь же дано сравнение с экспериментально измеренным распределением (полоска внизу). Конечно, в этой статье отображена только часть великолепной картины, богатой физическими явлениями. В ней не затронуты многие интересные вопросы. Например: почему ширина зоны орошения заметно больше ширины люка и даже фюзеляжа самолета? Тут играет роль турбулентная диффузия: элементы воздуха и жидкости участвуют в хаотическом движении, которое накладывается на их 'среднее' движение, рассмотренное выше, и приводит к 'размазыванию' траекторий падающих частиц. Кроме того, не учтены и такие факторы: струйно-вихревой след самого самолета, опускающийся вниз; горячий поток смеси воздуха, паров воды, углекислого газа и сажи, поднимающийся вверх; возможность бокового ветра; наконец, модель самого пожара. Но об этом лучше поговорить, когда вы поступите в Московский физико-технический институт. Чего вам и желаем.

01-16.p65

4

23.12.10, 15:26


Разбиения на домино и функции высоты
Е.КАРПОВ, К.КОХАСЬ

В

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

ЭТОЙ СТАТЬЕ МЫ РАССКАЗЫВАЕМ О ТОМ, КАК

Для каждого разбиения шестиугольника F на домино мы зададим функцию на узлах решетки, которую будем называть функцией высоты этого разбиения. Ее можно задать, например, так. Правило построения функции высоты. Треугольная решетка состоит из прямых линий трех направлений. Ориентируем каждое из этих направлений. Будем считать, что движение по горизонтали вправо, движение влево вниз и движение влево вверх увеличивают высоту, а движение по горизонтали влево, движение вправо вверх и движение вправо вниз уменьшают высоту см. рисунок 4, где стрелочками отмечены направления движения, увеличивающие высоту. Выберем Рис.4. Направлетеперь любой узел решетки и зада- ния, в которых дим в нем значение функции высоты высота растет произвольным образом. Например, пусть h(K) = 4 (см. рис.3). Будем двигаться по ребрам нашего разбиения и последовательно задавать высоту в узлах, полагая, что сдвиг по ребру увеличивает или уменьшает высоту на 1 по описанным правилам. Например, высоту в точке L положим равной 3, так как движение от K к L идет в направлении, понижающем высоту. Переходя от узла к узлу, мы определим функцию высоты для всех узлов фигуры F (рис.5,а).

Рис.5. а) Функция высоты; б) график функции высоты

Последнее обстоятельство, впрочем, нуждается в пояснении. В правиле не указано, в каком порядке мы обходим узлы шестиугольника. В математике для всякой конструкции, имеющей произвол в определении, принято доказывать корректность этой конструкции, т.е. что ее выполнение однозначно и непротиворечиво задает конструируемый объект. Гипотетически возможна ситуация, когда, задав значение высоты в

01-16.p65

5

23.12.10, 15:27


$

КВАНT 2010/?6

очередном узле, мы обнаружим, что это значение нарушает правило по отношению к соседнему узлу, или, что то же самое, если обойдя какой-либо циклический маршрут на нашем разбиении (и задавая вдоль пути функцию высоты), мы вдруг обнаружим, что значение высоты в конце пути не совпадает с начальным значением. В нашем случае указанные опасения не реализуются. Действительно, заметим, что при обходе вершин каждого ромба высота задается корректно, поскольку увеличение высоты на одной стороне ромба компенсируется уменьшением высоты на противоположной стороне. А поскольку любой цикл состоит из обходов ромбов, то не может возникнуть противоречия и при обходе любого из циклов. Любое замощение шестиугольника ромбами легко расшифровывается нашим глазом как плоское изображение трехмерной картины 'коробка, частично заполненная кубиками' (см. рис.3). При этом флип это просто добавление или вынимание кубика из коробки. Покажем, как можно воссоздать эту картинку, используя функцию высоты. Будем пользоваться обычной декартовой системой координат в трехмерном пространстве. Расположим шестиугольник F в горизонтальной плоскости (OXY) и из каждого узла решетки проведем вертикально вверх (в направлении оси OZ) отрезок, длина которого равна значению функции высоты. Соединим верхние концы отрезков, стоящих в соседних узлах нашего разбиения. Получится каркас многогранной поверхности (на рисунке 5,б эта конструкция выполнена для части замощения). Это та поверхность, которую мы видим на рисунке 3, фактически она представляет собой график функции высоты. Нетрудно видеть, что значения функций высоты двух замощений, отличающихся флипом, совпадают всюду, кроме центра шестиугольничка, в котором произошел флип. Это значит, что графики этих функций высоты различаются лишь внутри того шестиугольничка, где происходил флип. Удалим совпадающие части графиков, тогда оставшиеся грани определяют некоторый многогранник, расположенный над этим шестиугольничком. Это и есть тот самый кубик, который добавляется или убирается из коробки. Рассмотрим отдельно такой кубик (рис.6, возле каждой вершины указана ее высота). Ясно, что функция Рис.6 высоты h(v) это фактически сумма координат вершины v, или, что то же самое, расстояние от узла v до плоскости x + y + z = 0, умноженное на 3 . Это наблюдение оправдывает название 'функция высоты'. Сделаем еще одно замечание. Мы только что описали, как по функции высоты построить 'коробку, частично заполненную кубиками'. А о какой коробке, собственно, идет речь? Что такое 'коробка без кубиков'? Поскольку флип, соответствующий выниманию кубика, уменьшает значение функции высоты в какомто узле, то после вынимания всех кубиков получается минимально возможная функция высоты. Таким образом, 'коробка без кубиков' это график минимально

возможной функции высоты. Когда мы разглядываем картинку с разбиением на ромбы, наш мозг однозначно восстанавливает пустую коробку (в том числе и на тех картинках, где коробка частично заполнена), и это дает 'биологическое' доказательство существования минимальной функции высоты. Докажите существование минимальной функции высоты математически (почему она единственна?). Теперь понятно, что с помощью флипов из любого разбиения можно получить любое другое. Например, можно сначала вынуть все кубики из коробки, заданной первым разбиением, а потом добавить все кубики, которые должны быть во второй коробке. Это ответ на первый вопрос. Количество кубиков в заполненной коробке равно n3 . Поэтому для переделывания одного разбиения в другое потребуется не более n3 флипов. Действительно, пусть даны две кучи кубиков A и B. Рассмотрим два возможных алгоритма: 1) убираем все кубики из кучи A, после чего кладем кубики, чтобы получилась куча B; 2) добавляем кубики к куче A, пока коробка не заполнится, после чего вынимаем из полной коробки кубики так, чтобы осталась куча B. Вместе эти алгоритмы требуют 2n3 флипов. Значит, для выполнения одного из них понадобится не более n3 флипов. С другой стороны, нельзя получить полную коробку из пустой меньше чем за n3 флипов. Мы ответили и на второй вопрос. 2. Доминошки на клетчатой плоскости Рассмотрим обычную клетчатую плоскость. Клетки это единичные квадраты, а доминошкой будем называть любой прямоугольник 1 Ч 2 , состоящий из двух клеток, имеющих общую сторону. Зафиксируем прямоугольник P на клетчатой плоскости и будем рассматривать всевозможные замощения этого прямоугольника доминошками. В этом разделе флипом будем называть преобразование, состоящее в том, что мы выбираем квадрат 2 Ч 2 , разбитый на две доминошки, и поворачиваем его на

Рис.7. Два покрытия доминошками, отличающиеся одним флипом

90 (рис.7). Нас будут интересовать те же два вопроса о флипах: можно ли с их помощью перестроить любое разбиение на домино в любое другое и сколько для этого потребуется операций. На этот раз никакой объемной картинки не видно, наше пространственное воображение молчит. Поэтому мы поступим аналогично рассуждениям из предыдущего параграфа: придумаем функцию на узлах решетки, которая будет измерять высоту какого-то пространственного объекта, и посмотрим, что, собственно, она измеряет. Функция высоты для прямоугольников впервые рассматривалась У.Терстоном [1].

01-16.p65

6

23.12.10, 15:27


РАЗБИЕНИЯ

НА

ДОМИНО

И

ФУНКЦИИ

ВЫСОТЫ

%

Правило построения функции высоты. Раскрасим клетки плоскости в шахматном порядке. Пользуясь этой раскраской, построим ориентированный граф G следующим образом (рис.8,а): вершины графа это

котором тоже не удается определить функцию высоты. Цикл ограничивает многоугольник, разбитый на доминошки. Обходя каждую доминошку по часовой стрелке, мы встречаем стрелки по движению и против одинаковое число раз. Получаем, что общее количество стрелок по движению совпадает с общим количеством стрелок против, но при этом все стрелки внутри многоугольника подсчитаны дважды один раз по направлению цикла, один против. Значит, на границе многоугольника, т.е. в исходном цикле, одинаковое количество стрелок по движению по часовой стрелке и против. Противоречие. Функцию высоты, заданную на узлах, и ее график можно продолжить до многогранной поверхности (на рисунке 10 эта поверхность показана упрощенно: шестиугольные 'грани' на самом деле неплоские). Тогда

Рис.8. а) Шахматная раскраска и направленные ребра графа; б) разбиение прямоугольника на домино и его функция высоты

Рис.10. График функции высоты и его преобразование при флипе

узлы решетки, принадлежащие прямоугольнику P, а ребра стороны клеток; причем стороны черных клеток направлены по часовой стрелке, а белых против часовой стрелки. Высоту задаем так: произвольно зададим высоту какого-нибудь узла, а после этого будем двигаться по сторонам доминошек нашего разбиения, полагая, что при движении по стрелке происходит увеличение высоты на 1, а при движении против стрелки уменьшение на 1 (рис.8,б). Обойдя все узлы, мы полностью определим функцию высоты. Корректность этого определения не вполне очевидна. Проведем эксперимент: возьмем тримино (рис.9). Пусть высота левого нижнего угла A равна 1. Обойдем границу тримино против часовой стрелки. Дойдя до вершины B, мы вдруг обнаруживаем, что на ребре BA высота задана с нарушением правила! Таким образом, данное правило построения функции высоты для некоторых фигур действительно может быть некорректным. На самом деле, эти сообраРис.9. Тримино жения ничего не опровергают, так как мы применяем наше правило к фигурам, разбитым на домино. Докажем, что если фигура уже разбита на домино, то правила корректно задают функцию высоты. Пусть, двигаясь по циклу и определяя функцию высоты в узлах, мы пришли к противоречию в исходном узле, т.е. при движении по циклу количество 'попутных' стрелок не совпало с количеством 'встречных' стрелок. Можно считать, что цикл несамопересекающийся, иначе возьмем тот из маленьких подциклов, на которые распадается цикл, на

для каждого флипа разность подграфиков этих поверхностей до и после флипа определяет некоторый многогранник 'кирпич', аналог кубика из п. 1. Чтобы понять, как выглядит этот кирпич, рассмотрим квадрат 2 Ч 2 , разбитый на домино двумя способами (рис.11). Расположим н аш квадрат 2 Ч 2 в горизонтальной плоскости OXY. Для каждого узла на рисунке 11 рассмотрим точку в трехмерном пространстве, у которой апп- Рис.11. Флип в квадратике 2 Ч 2 и ликата (т.е. z-коорди- функция высоты ната) равна значению функции высоты в этом узле. Мы построили 10 точек. Они определяют многогранник, изображенный на рисунке 12 (закрашенные грани проектируются в контур квадрата). Это и есть наш 'кирпич'. Сторонам исходного квадрата 2 Ч 2 соответствуют некоторые грани 'кирпича' (потому что высота в серединах сторон квадрата отличается от высоты в вершинах), на рисунке эти грани закрашены. Американские математики Элкис, Ларсен, Куперберг и Пропп, написавшие фундаменРис. 12 тальную статью о разбиениях на домино [2], заметили, что с точностью до некоторой деформации графика функции высоты можно считать, что 'кирпич' это параллелепипед 2 Ч 2 Ч 1 . Точнее,

01-16.p65

7

23.12.10, 15:27


&

КВАНT 2010/?6

это параллелепипед, у которого сделаны выступы на средних линиях граней и скосы на ребрах (рис.13). Благодаря этим выступам мы не можем, к примеру, положить один кирпич на другой выступы меРис.13. Граненый кирпич шают плотной укладке. Кирпичи приходится укладывать друг на друга со сдвигом, как это делают в обычной кирпичной кладке, выступающие части кирпичей накладываются на скошенные ребра и в результате кирпичи плотно прилегают друг к другу. При взгляде на кирпич сверху мы воспринимаем выступ как линию, разбивающую квадратную грань кирпича на две доминошки. Поэтому любая куча плотно уложенных кирпичей сверху выглядит как разбиение некоторой фигуры на домино. Функция высоты, которую мы определили выше, обладает таким свойством: если f и g две функции высоты, то min ( f , g ) тоже функция высоты (докажите!). Отсюда следует, что существует минимальная функция высоты. Благодаря этому обстоятельству выполнение флипов можно интерпретировать как заполнение кирпичами некоторой 'коробки'. Пустая коробка график минимальной функции высоты имеет довольно хитрую форму: что-то вроде октаэдра. На рисунке 14 показана часть 'пустой коробки',

кирпича (рис.16,в), в четвертый 2 Ч 3 = 6 кирпичей (рис.16,г), наконец, в пятый ряд можно положить 3 Ч 3 = 9 кирпичей (рис.16,д). Но это еще не все. Хотя коробка заполнена, мы можем продолжать класть кирпичи сверху так, чтобы они образовывали 'горку', симметричную уже уложенным кирпичам. Поэтому в шестой ряд можно положить 3 Ч 2 = 6 кирпичей (рис.16,е), в седьмой 2 Ч 2 = 4 кирпича (рис.16,ж), в восьмой 2 Ч 1 = 2 кирпича (рис.16,з) и в девятый ряд на вершину всей этой пирамиды 1 Ч 1 = 1 последний кирпич (рис.16,и). Заполненная коробка 'с горкой' изображена на рисунке 16,к. Благодаря интерпретации с заполнением коробки ясно, что с помощью флипов любое замощение можно перестроить в любое другое. Сколько же для этого потребуется флипов? Проведем вычисление для квадрата 2n Ч 2n . Лемма 1. Наибольшее количество кирпичей в конфигурации, построенной по разбиению квадрата 2n Ч 2n на домино, равно n(2n 1)(2n + 1)/3. Доказательство. Выше мы подробно описали процесс заполнения пустой коробки для квадрата 6 Ч 6 . В случае квадрата произвольного размера по аналогичным соображениям суммарное количество кирпичей равно
11 + 1 2 + 2 2 + 2 3 + ...

... + (n - 1) n + n2 + n (n - 1) + ... + 2 1 + 1 1 . Теперь требуемую формулу читатель легко докажет с помощью метода математической индукции. Как и в предыдущем параграфе, из утверждения леммы следует, что для перестройки одного разбиения квадрата 2n Ч 2n на домино в другое потребуется не более n (2n - 1) (2n + 1) 3 флипов. 3. Крепости Янга Теперь рассмотрим более экзотическую решетку. Возьмем обычную клетчатую плоскость и в каждой клетке проведем диагонали (рис.17). Плоскость оказалась разбитой на равнобедренные прямоугольные треугольники. Зафиксируем терминологию: эти треугольники мы теперь будем называть клетками. Исходную квадратную решетку будем называть базовой квадратной решеткой. Фигуру, состоящую из двух соседних клеток, т.е. треугольник или ромб будем называть доминошкой. Таким образом, в этом параграфе слово 'доминошка' имеет совсем не то значение, к которому мы привыкли: это не прямоугольничек 1 Ч 2 , а совершенно другая фигура ромб или треугольник, состоящий из двух маленьких треугольничков. Чтобы лишний раз подчеркнуть нетипичный смысл этого слова, мы всюду ниже будем выделять его курсивом. Итак, мы будем рассматривать разбиения некоторых фигур на доминошки. Фигуры, разбитые на доминошки, мы будем преобразовывать с помощью флипов. Флип это преобразование одного из двух типов: i Поворот на 90 квадрата, состоящего из двух треугольных доминошек.

Рис.14. Коробка для замощений домино прямоугольника 8Ч6

соответствующей прямоугольнику 8 Ч 6 . Чтобы не усложнять картинку, выступы и скосы не показаны, за исключением тех, что разделяют горизонтальные поверхности коробки на доминошки. Вид сверху на ту же коробку показан на рисунке 15 (закрашены те части коробки, которые не показаны на рисунке 14, указана высота, на которой находятся горизонтальные части коробки). На примере коробки для квадрата 6 Ч 6 опишем процесс заполнения пустой коробки по слоям (рис.16, всюду отмечены высоты видимых Рис.15. Коробка. Вид граней). В самый нижний ряд пустой коробки можно полосверху жить лишь 1 кирпич (рис. 16,а); здесь и на следующих рисунках место, куда мы кладем кирпичи, подкрашено. Во второй ряд помещается 1 Ч 2 = 2 кирпича (рис.16,б), в третий 2 Ч 2 = 4

01-16.p65

8

23.12.10, 15:27


РАЗБИЕНИЯ

НА

ДОМИНО

И

ФУНКЦИИ

ВЫСОТЫ

'

Рис.16. Последовательное заполнение коробки

i Замена двух средних линий ромба, состоящего из четырех ромбических доминошек, на две диагонали этого ромба (в результате получается ромб, разбитый на четыре треугольные доминошки) или наоборот. Такое преобразование возможно, только если центр ромба находится в узле базовой квадратной решетки.

Будем рассматривать следующие фигуры. Возьмем на базовой квадратной решетке квадрат N Ч N и, проходя вдоль каждой его стороны, добавим на каждом втором единичном отрезке границы выступающую наружу четвертинку квадратика. Получится фигура, напоминающая чертеж крепости (выступающие треугольники это 'бастионы'). Ее мы так и будем называть крепость Янга (в честь первого, кто систематически исследовал разбиения этих фигур на домино [3]). При нечетном n имеется два вида крепостей (рис.17), при четном один вид (с точностью до поворотов).

Рис.17. Два варианта крепости порядка 5

Крепости интересны тем, что для них подсчитано, сколькими способами их можно разбить на домино. Ответ фантастический. Крепость размера 2N Ч 2N 2 можно разбить на домино 5N способами! Для нечетных размеров ответ немного похуже. Например, крепость размера 2011 Ч 2011 без угловых бастионов (как на рисунке 17 слева) разбивается н а домино 2 510061005 способами. К сожалению, доказать это непросто, хотя доказательство элементарно. Для более

простых фигур на этой решетке, например для квадратов или ромбов, хороших формул для числа разбиений, по-видимому, нет. Чтобы не увязнуть в деталях конструкций, зависящих от четности, ограничимся рассмотрением крепостей нечетного размера без угловых бастионов (см. рис.17, слева). Для других крепостей утверждения, приводимые ниже, аналогичны. Нас интересуют все те же два вопроса о флипах. Зафиксируем какое-либо разбиение крепости на домино. Функция высоты для этого разбиения задается следующим образом. Правило построения функции высоты. Раскрасим узлы базовой квадратной решетки в синий и оранжевый цвета в шахматном порядке (рис.18). Произвольно зададим высоту какого-нибудь узла, а после этого будем двигаться по сторонам доминошек нашего раз- Рис.18. Раскраска узлов крепости биения, полагая, что при движении по диагонали высота не меняется, при движении по вертикали или горизонтали от синей вершины к оранжевой высота возрастает на 1, а при движении от оранжевой к синей убывает на 1. Теорема 1. Правила корректно задают функцию высоты для любого разбиения креРис.19. Функция высоты пости.

01-16.p65

9

23.12.10, 15:27




КВАНT 2010/?6

Рис.20. Три вида кирпичей для крепости Янга

Докажите это самостоятельно. Заметим, кстати, что конструкции, с помощью которых мы задавали функции высоты, не являются единственно возможными. Например, если мы уже придумали трехмерную модель, ничто не мешает повернуть ее в пространстве. В результате высуты всех точек изменятся довольно хитро и комбинаторное правило, задающее функцию высоты, может стать совершенно неудобоваримым. Теперь, когда функция высоты задана, мы можем сконструировать 'кирпичи', соответствующие флипам. Как и в предыдущем параграфе, рассмотрим фигуру (квадрат из двух доминошек или ромб из четырех доминошек), в которой выполняется флип, и для каждого узла этой фигуры построим точку в трехмерном пространстве, у которой z-координата равна значению функции высоты в этом узле. Построенные точки определяют некоторый многогранник. Флипу первого вида соответствует тетраэдр, а флипам второго вида четырехугольная пирамида (рис.20). Итак, выполнение флипа это добавление или вынимание кирпича из некоторой коробки, где под коробкой мы, как и раньше, понимаем график минимальной функции высоты. Разбиение на домино, соответствующее пустой коробке, показано на рисунке 21 слева; полной коробке (т.е. максимальной функции высоты) соответствует разбиение на рисунке 21 справа. Как видим, у нашей коробки две противополож-

Рис.21. Пустая и заполненная коробки

ные вершины крепости расположены низко (на высоте 0), а две другие высоко (на высоте 3). Таким образом, коробка для кирпичей по форме близка к тетраэдру (сравните с рисунком 20,а). Несколько примеров заполнения коробки показаны на рисунках 2327.

Опишем процесс заполнения пустой коробки по слоям на примере коробки 5 Ч 5 . Самое низкое место в пустой коробке это диагональ, идущая слева снизу вправо вверх (рис.21, слева). Положим вдоль этой диагонали 5 тетраэдров, верхние ребра тетраэдров находятся на высоте 1 (рис.22,а; на рисунке 25 показано, как выглядит коробка, когда добавлен один тетраэдр). На диагонали осталось 6 точек, находящихся на высоте 0. С крайними мы ничего сделать не сможем, а остальные 4 точки накроем перевернутыми пирамидами (кирпичи третьего вида, см. рис.20,в), получится большая плоская площадка на высоте 1 (рис.22,б). На этой площадке мы можем поставить 6 пирамид (кирпичи второго вида, см. рис.20,б), вершины пирамид должны находиться над отмеченными узлами. Другое размещение пирамид тут невозможно, потому что, как мы отмечали, центр ромба, где происходит соответствующий флип, должен лежать на базовой квадратной сетке; если же, к примеру, сделать флип в ромбе с центром на рассматривавшейся диагонали, то это приведет к удалению одной из только что уложенных перевернутых пирамид (рис.26). Итак, добавив 6 пирамид, мы получили картинку, изображенную на рисунке 22,в. Добавленные пирамиды соприкасаются друг с другом и с коробкой ребрами на высоте 1, положим на эти ребра тетраэдры: 9 тетраэдров на ребра, идущие в одном диагональном направлении, и 4 на ребра второго диагонального направления; результат показан на рисунке 22,г. Оставшиеся внутри площадки вершины на высоте 1 накроем 6 перевернутыми пирамидами, получится большая плоская площадка на высоте 2 (рис.22,д). На эту площадку мы ставим 4 пирамиды с вершинами, расположенными над отмеченными узлами, результат показан на рисунке 22,е. Если теперь закрыть ребра, лежащие на высоте 2, пятью тетраэдрами, получится заполненная коробка (см. рис. 21, справа). Вся эта конструкция напоминает укладывание яиц в коробку: сначала кладут подложку с лунками для яиц, потом кладут сами яйца, а сверху их закрывают перевернутой подложкой и т.д. Для подсчета количества флипов нам понадобится следующая лемма. Лемма 2. 1 (n - 1) + 2 (n - 2 ) + 3 (n - 3 ) + ...

... + (n - 2 ) 2 + (n - 1) 1 = (n - 1) n (n + 1) 6 .

01-16.p65

10

23.12.10, 15:27