WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
Библиотека <Математическое просвещение> Выпуск 26 К. П. Кохась ЛАДЕЙНЫЕ ЧИСЛА И МНОГОЧЛЕНЫ Издательство Московского центра непрерывного математического образования Москва • 2003 УДК 519.113/.118 ББК 22.19 К75 Аннотация В брошюре рассказано о популярном и очень наглядном комбинаторном объекте: ладейных числах и ладейных многочленах.

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

Текст брошюры представляет собой дополненную обработку записи лекции для школьников 9—11 классов, прочитанной автором на Малом мехмате МГУ 21 декабря 2002 года.

Брошюра рассчитана на широкий круг читателей, интересующихся математикой: школьников старших классов, студентов, учителей.

Работа автора над брошюрой поддержана РосР И сийским фондом фундаментальных исследова ний (грант № 02—01—00093).

Издание осуществлено при поддержке Московского департамента образования и Московской городской Думы.

ISBN 5-94057-114-X © К. П. Кохась, 2003.

© МЦНМО, 2003.

Константин Петрович Кохась.

Ладейные числа и многочлены.

(Серия: <Библиотека,,Математическое просвещение“>. Вып. 26).

М.: МЦНМО, 2003. — 20 с.: ил.

Редактор Ю. Л. Притыкин. Техн. редактор М. Ю. Панов.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано в печать 8/VIII 2003 года.

1 Формат бумаги 6088 /. Бумага офсетная№1. Печать офсетная. Физ. печ. л. 1,25.

16 Усл. печ. л. 1,22. Уч.-изд. л. 1,24. Тираж 3000 экз. Заказ 3040.

Издательство Московского центра непрерывного математического образования.

119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

Отпечатано с готовых диапозитивов в ФГУП <Производственно-издательский комбинат ВИНИТИ>.

140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.

§ 1. ЛАДЕЙНЫЕ ЧИСЛА.

ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ Рассмотрим обычную шахматную доску и обычную шахматную фигуру — ладью. Сколькими способами можно поставить на шахматную доску две ладьи так, чтобы они не били друг друга Какое наибольшее число ладей можно поставить на доску так, чтобы каждая ладья била не более двух других Можно задать много подобных вопросов, наверняка читатель встречал такого рода задачи на олимпиадах или в книжках по развлекательной математике (см., например, книгу [1]).

Вопросы, о которых пойдёт речь в этой брошюре, являются естественными обобщениями задач о расстановке ладей. Мы рассмотрим произвольные доски и обсудим многочисленные свойства ладейных чисел. Для начала несколько определений.

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

Ладья — это фигура, которая держит под боем все клетки плоскости, находящиеся с ней на одной горизонтали или на одной вертикали.

Таким образом, для досок сложной формы ладья может держать под боем клетки, отделённые Рис. от неё клетками, не принадлежащими доске. Так, на рис. 1 изображена несвязная доска из пяти клеток, ладья и клетки, находящиеся под боем этой ладьи (отмечены крестиками).

Зафиксируем произвольную доску B и для каждого натурального n вычислим количество различных способов поставить на эту доску n не бьющих друг друга ладей. Обозначим это количество rn или rn(B), если нужно указать, о какой именно доске идёт речь.

Положим по определению r0=1. Числа r0, r1, r2,... называются ладейными числами доски B.

Очевидно, что r1(B)=S, где S — площадь (количество клеток) доски B.

Если же мы хотим разместить на доске слишком много ладей — больше S — у нас ничего не получится: все ладьи не поместятся на нашу доску. Таким образом, для любой доски ладейные числа с большими номерами равны нулю.

В таблице на рис. 2 приведены примеры досок, состоящих из пяти клеток, и все их ненулевые ладейные числа. Заметим, что доски разной формы могут иметь одинаковые наборы ладейных чисел.

1. Проверьте данные таблицы на рис. 2 *).

Для вычисления ладейных чисел часто хватает несложных комбинаторных соображений. Найдём, например, чему равно *) Двумя чертами слева выделены упражнения для самостоятельного решения.

Доски r0 r1 r2 r3 Доски r0 r1 r2 r1 1 5 1 5 1 5 5 1 5 1 5 6 Рис. число r3 для обычной шахматной доски 88. Трёх ладей на доске 33 можно расставить 3! способами. Чтобы расставить трёх ладей на доске 88, достаточно сначала выбрать три вертикали и три горизонтали — это можно сделать (C3)2 способами, а потом на образовавшейся доске 33 взять одну из шести расстановок.

Итак, для шахматной доски r3=6·72·82.

Приведём ещё один пример.

Лемма I. Пусть имеется доска B и cB — произвольная клетка. Пусть Крест(c) — это множество клеток доски B, лежащих на той же горизонтали или в той же вертикали, что и клетка c.

Тогда rk(B)=rk(B\c)+rk-1(B\Крест(с)). (1) (Здесь мы используем обычные обозначения: B\c — это доска, полученная из B удалением клетки c.) Д о к а з а т е л ь с т в о очевидно: поставить k ладей на доску B можно либо разместив их так, чтобы клетка c осталась свободной (это можно сделать rk(B\c) способами), либо поставив одну ладью в клетку c, тогда остальные придётся ставить вне креста клетки c (это можно сделать как раз rk-1(B\Крест(с)) способами).



Заметим, что утверждение леммы I показывает, как можно вычислить ладейные числа какой-нибудь доски, если известны ладейные числа меньших досок. Таким образом, на самом деле равенство (1) — это рекуррентная формула, с помощью которой мы можем вычислять ладейные числа любой доски B (лучше на компьютере), не пользуясь никакими комбинаторными идеями.

Правда, придётся накопить довольно много информации о ладейных числах досок, которые содержатся в B. Примеры других рекуррентных формул мы встретим в § 3.

Теперь, когда мы убедились, что вычисление ладейных чисел — задача в принципе решаемая, введём ещё одно понятие.

Две доски назовём эквивалентными, если наборы ладейных чисел у этих досок совпадают. Примеры эквивалентных досок можно видеть в таблице на рис. 2.

Изучая ладейные числа различных досок, хотелось бы научиться для каждой доски подбирать эквивалентную доску <достаточно простой> формы. Естественный и простой способ преобразовать доску так, чтобы её ладейные числа не изменились, состоит в перестановке вертикальных или горизонтальных рядов клеток, составляющих эту доску. Так, для доски на рис. 1, переставляя вертикальный ряд клеток, содержащий изолированную клетку, <поближе> к <основной части> доски, мы можем получить связную доску, что, по-видимому, можно рассматривать как <упрощение> формы.

Другими естественными операциями над досками, сохраняющими ладейные числа, являются поворот на ±90 или 180 и отражения доски относительно вертикали, горизонтали или диагонали.

Хотя эти операции и позволяют изменять форму доски, добиться <совсем простой> формы, пользуясь этими или ещё какими-нибудь операциями, видимо, не удастся, что видно уже на примере всё тех же пятиклеточных досок. Но всё же мы будем рассматривать достаточно богатый класс досок относительно простой формы. Это так называемые диаграммы Юнга.

Диаграмма Юнга со строками b1, b2,..., bm (0

В заключение этого параграфа приведём нетривиальный пример двух эквивалентных досок.

2. Докажите, что доски, изображённые на рис. 3, а, б, эквивалентны! * * * Теорема I. Квадратная доска nn эквивалентна доске Yn в форме диаграммы Юнга с длинами строк 1, 3, 5,..., 2n-1.

Д о к а з а т е л ь с т в о. Обозначим квадрат nn через Kn. Мы построим по индукции взаимно однозначное соответствие между расстановками ладей в Kn и в Yn, следуя А. Левиту.

База индукции n=1 очевидна. Докажем индукционный переход. Разобьём квадрат Kn на две части: квадрат Kn-1 и <рамку>, состоящую из 2n-1 клеток. Треугольную доску Yn тоже разобьём на две части: доску Yn-1 и самую длинную горизонталь (тоже из 2n-1 клеток). Допустим, что совпадение ладейных чисел квадрата Kn-1 и треугольника Yn-1 уже установлено. Тогда можно считать, что построено соответствие между расстановками ладей в квадрате nn, в которых все ладьи находятся в выделенной части (n-1)(n-1), и расстановками ладей в Yn, в которых все ладьи находятся в выделенной части Yn-1. Осталось построить соответствие между расстановками ладей в Yn, которые содержат ладью на длинной горизонтали, и расстановками ладей в Kn, которые содержат ладьи в <рамке>. Рассмотрим все расстановки k ладей в Yn, содержащие ладью в длинной строке, у которых расстановка k-1 ладей в Yn-1 фиксирована, назовём её s, а соответствующую ей расстановку в Kn-1 назовём t. Всего имеется 2n-k=n+(n-k) таких расстановок, поскольку в длинной строке ровно столько подходящих для последней ладьи клеток. Пронумеруем как-нибудь эти клетки (рис. 4).

Если ладья стоит на клетке с номером l, 1ln, то поставим ладью на l-ю клетку вертикальной стороны рамки в Kn, вычеркнем мысленно вертикаль и горизонталь, содержащие поставленную ладью, и на оставшейся части доски (которая представляет собой <раздвинутый> квадрат Kn-1, очевидно, у него ладейные числа такие же, как у Kn-1) реализуем расстановку t (рис. 5).

1 2 3 4 5 4 Рис. 1 2 4 Рис. Если же ладья стоит на клетке с номером l>n (таких номеров имеется n-k), то реализуем расстановку t в стандартном квадрате Kn-1. Заметим, что среди n-1 клеток <рамки>, расположенных над Kn-1, есть ровно n-k мест, куда можно было бы поставить ладью. Ну так и поставим ладью на (l-n)-е из этих мест (рис. 6).

Построенное соответствие является взаимно однозначным.

Действительно, нетрудно предъявить обратное отображение. Если в <рамке> квадрата Kn не стоит ни одной ладьи, следует воспользоваться взаимно однозначным отображением, которое существует по индукционному предположению. Если имеется ладья, стоящая в первом столбце, следует вычеркнуть её вместе с вертикалью и горизонталью, которые она занимает, и для оставшейся фигуры (<раздвинутый> квадрат Kn-1) опять воспользоваться индукционным предположением. Если же в первом столбце ладьи нет, но есть ладья в первой строке, следует мысленно удалить рамку, воспользовавшись индукционным отображением, расположить ладей в диаграмме Yn-1Yn и добавить ладью в самую длинную строчку диаграммы Yn на подходящее место.

Замечание. Как мы отмечали, число r1(B) равно площади доски B. Поэтому, доказав утверждение теоремы I, мы получили также (не самое простое, зато о ч е н ь комбинаторное) доказательство равенства 1+3+5+...+(2n-1)=n2.





3. Разглядывая рис. 4—6, докажите, что rk(Kn)=rk(Kn-1)+(2n-k) rk-1(Kn-1).

1 2 3 Рис. § 2. КОМБИНАТОРНЫЕ НЕРАВЕНСТВА С ЛАДЕЙНЫМИ ЧИСЛАМИ Докажем несколько неравенств с ладейными числами. Будем считать, что фиксирована произвольная доска B. Говоря о расстановке небьющих друг друга ладей, мы часто для краткости будем опускать слова <друг друга>.

Неравенство 1. Ck rk+mrmrk.

k+m Доказ ат е льс т во. Число rmrk имеет ясный комбинаторный смысл: это количество способов разместить на доске k белых и m чёрных ладей так, чтобы белые ладьи не били белых, а чёрные — чёрных; при этом на любую клетку разрешается ставить две ладьи, если они разного цвета. Заметим, что из каждой расстановки k+m небьющих ладей можно получить расстановку из k белых небьющих ладей и m чёрных небьющих ладей — нужно просто выбрать, какие ладьи будут белыми (это можно сделать как раз Ck способами), а остальные ладьи пусть будут чёрными.

k+m Разным исходным расстановкам и разным способам выборки соответствуют разные пары наборов белых и чёрных ладей, итого — Ck rk+m пар. Но, конечно же, таким способом мы можем полуk+m чить далеко не все наборы белых и чёрных ладей, поскольку мы заведомо не получим таких наборов, где имеются чёрная и белая ладьи, стоящие на одной клетке.

4. Докажите неравенство 18 480r12r9 (не будем скрывать от читателя, что 18 480=C6 ·C3).

12 * * * Неравенство 2. kk-2rkCk-1 при 1kn.

rД о к а з а т е л ь с т в о. Для любого множества A из k небьющих ладей построим всевозможные такие наборы из k-1 пар небьющих ладей, что все ладьи в этих парах принадлежат A и каждая ладья из A входит хотя бы в одну пару. Это можно сделать многими способами. Чтобы подсчитать это число способов, заметим, что любые k небьющих ладей можно считать упорядоченными, например, по расположению их горизонталей сверху вниз. Тогда каждому способу выбора k-1 пар небьющих ладей можно сопоставить граф, в котором имеется k помеченных вершин, соответствующих ладьям, и k-1 рёбер, соответствующих выбираемым парам. Этот граф будет, вообще говоря, несвязным; нетрудно видеть, что в нём не может быть изолированных вершин. Пусть Nk — число графов, состоящих из k неизолированных помеченных вершин и k-1рёбер.

Далеко не всякий набор из k-1 пар ладей может быть получен таким образом, хотя бы потому, что в н а ш и х наборах общее число ладей равно k, а в произвольном наборе их количество может быть и другим. Следовательно, мы получаем неравенство NkrkCk-1.

rПо-видимому, для чисел Nk нет хорошей формулы, подробности (в том числе, описание производящей функции) можно прочитать в статье [4]. Для завершения доказательства заметим, что Nkkk-2, так как последняя величина выражает количество деревьев с k помеченными вершинами (это утверждение знаменитой теоремы Кэли).

* * * Неравенства, которые мы сейчас рассмотрели, — грубые, поскольку не используют <геометрию> доски. Действительно, при доказательстве этих неравенств мы пользовались теоретико-множественными соображениями и никак не учитывали взаиморасположение ладей. Поэтому доказанные неравенства верны в следующей более общей ситуации. Пусть дано произвольное конечное множество A. Пусть S — некоторое свойство подмножеств множества A, удовлетворяющее условию монотонности: если множество BA удовлетворяет свойству S, то и любое подмножество B B также удовлетворяет свойству S.

Например, пусть A — произвольное множество натуральных чисел, а S — свойство <произведение данных чисел нечётно> (или, скажем, свободно от квадратов). В применении к ладейным числам, A — это множество клеток доски, S — свойство <все клетки данного подмножества ладейно независимы> (т. е. каждая вертикаль и горизонталь содержат не более одной клетки из множества S).

Пусть rk —количество k-элементных подмножеств множества A, удовлетворяющих свойству S. Тогда величины rk удовлетворяют неравенствам 1 и 2.

Следующее неравенство значительно тоньше.

Неравенство 3. rk-1rk+1rk.

Д о к а з а т е л ь с т в о. Опять воспользуемся комбинаторным смыслом обеих частей неравенства: rk-1rk+1 — это количество способов поставить на доску k-1 чёрных небьющих ладей и k+белых небьющих ладей так, что ладьи разных цветов могут стоять на одной клетке; rk — это количество аналогичных расстановок k чёрных и k белых ладей.

Фиксируем произвольный набор C из 2k-m клеток доски, 0mk. Пусть pC — количество расстановок k-1 чёрных и k+1 белых ладей, в которых все клетки из C заняты ладьями, назовём эти расстановки расстановками первого типа, будем считать, что pС=0 при m=k; qС — количество расстановок k чёрных C1: (u клеток) A C2: s компонент, из них t - нечётные <лестницы>, s-t - все прочие B Рис. и k белых небьющих ладей на C, в которых все клетки из C заняты ладьями — расстановки второго типа. Докажем, что pCqC для каждого множества C из 2k-m клеток, 0mk. Из этого утверждения сразу следует требуемое неравенство.

Пусть C=C1C2, где C1 — объединение всех одноклеточных компонент связности (по отношению к ходу ладьи) множества C, C2=C\C1. Пусть часть C1 содержит u клеток.

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.