Главная
	Новости
	Задачи
	Устный тур
	Информация для участников
	Как провести Турнир?
	География
	Летние конференции
	Результаты
	Форум
	Ссылки
	Контакты

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

Решения

К. П. Кохась

---

0.1. | 0.2. | 0.4. | 0.5.
1.1. | 1.2. | 1.3. | 1.4. | 1.5.
2.1. | 2.2. | 2.3. | 2.4. | 2.5. | 2.6.
3.1. | 3.2. | 3.4. | 3.5. | 3.6. | 3.7.
4.1. | 4.2. | 4.3.
5.1. | 5.2. | 5.3. | 5.4. | 5.5.
6.1. | 6.2. | 6.3. | 6.4.
7.1. | 7.2. | 7.3.
8.1. | 8.2. | 8.3. | 8.4. | 8.5. | 8.6.
Список использованной литературы.

---

0.1. Черных и белых слонов расставляют независимо одним и тем же числом способов - обозначим его k. Для каждого из k способов расстановки черных слонов есть k способов расстановки белых слонов, поэтому общее число способов равно k².

0.2. Количество способов поставить одну ладью - это и есть площадь доски.

0.4. Трех ладей на доске 3*3 можно расставить 3! способами. Чтобы расставить трех ладей на доске 8*8, достаточно сначала выбрать три вертикали и три горизонтали - это можно сделать (C³₈)² способами, а потом на образовавшейся доске 3*3 взять одну из шести расстановок. Ответ: 6...7²...8².

0.5. Упражнение на принцип включения-исключения. Четырех ладей на всей доске можно расставить 4!(C⁴₈)² способами. Если одна ладья стоит на диагонали, а остальные - произвольно (лишь бы не били друг друга), то таких расстановок 8*3!*(C³₇)² (первый сомножитель - число способов выбрать одно место на диагонали, остальные - количество расстановок небьющих ладей на доске 7*7). Две ладьи на диагональ, а остальные - произвольно можно поставить C²₈*2!*(C²₆)² способами; три ладьи на диагонали, четвертая, где хочет, могут стоять C³₈*1!*(C¹₅)² способами; наконец, четыре ладьи на диагональ можно поставить C⁴₈ способами. Искомое число способов равно знакочередующейся сумме подсчитанных выражений

24*(C⁴₈)²- 8*3!*(C³₇)²+ C²₈*2!*(C²₆)²- C³₈*5²+ C⁴₈=70070 .

Действительно, в этой сумме интересующие нас расстановки учтены в первом выражении, а все лишние расстановки учтены в нескольких выражениях с суммарным коэффициентом 0. Например, расстановки ровно с тремя ладьями на диагонали один раз учтены в первом слагаемом, три раза - во втором, три раза в третьем и один раз в четвертом, учитывая знаки, получаем, что все эти расстановки "сокращаются". Ответ: 70070.

1.1. Если нам нужно расставить n ладей, и мы решили поставить k из них в часть C₁, а остальные - в часть C₂, то всего найдется r_k(C₁)r_n-k(C₂) таких расстановок. Значит,

	n
rn(C)=	S	rk(C1)rn-k(C2) .
	k=0

Осталось заметить, что коэффициент при xⁿ многочлена R(x,C₁)R(x,C₂) равен той же самой сумме.

1.2. Это очевидно. Рассмотрим расстановку n ладей. Если на клетке c не поставлена ладья, то ладьи рсположены на доске C₁, и их можно расставить r_n(C₁) способами. Если же на клетку c поставлена ладья, то остальные (n-1) ладей располагаются на доске C₂, и таких расстановок существует r_n-1(C₂). Значит, r_n(C)=r_n(C₁)+r_n-1(C₂). То же самое означает соотношение с многочленами.

1.3. Например, такая доска (в верхней строке 2002 клетки):

 _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_
|_|_|_
|_| |_|_
|_|   |_|
|_|

Другой пример: диаграмма Юнга со строками 1, 3, 5, 12, 41.

1.4. Автор задачи - C. Волченков, задача использовалась на II кубке им. Колмогорова. Вопрос задачи эквивалентен следующему вопросу:

На доске n*n расставлено n небьющих друг друга ладей. Разрешается спрашивать про любую клетку, стоит на ней ладья или нет. За какое наименьшее число вопросов можно заведомо узнать всю расстановку.

Ответ: n(n-1)/2. Например, можно сначала узнать, где расположена ладья, находящаяся в первом столбце. На это понадобится не более (n-1) вопросов. Потом узнаем, где именно расположена ладья из второго столбца. На это потребуется не более (n-2) вопросов, и т. д.

Докажем, что меньшего числа вопросов не хватит. Допустим, что некто пытается отгадать расстановку, задавая наименьшее число вопросов. Сжульничаем: не будем изначально расставлять ладей на доске, а на все вопросы угадывающего будем отвечать "нет", пока это возможно, вырезая из доски упомянутые в вопросах клетки и следя за тем, чтобы на оставшихся клетках было возможно расставить n не бьющих друг друга ладей. Заметим, что нам придется ответить "да" на вопрос угадывающего об очередной клетке C только в том случае, если при всех возможных расстановках небьющих ладей на "урезанной" доске на клетке C должна находится ладья. Но в этой ситуации и без вопросов ясно, что на клеке C стоит ладья, поэтому при действиях угадывающего, требующих наименьшего количества вопросов, нам не придется ни разу отвечать "да".

Угадывающий должен прекратить задавать вопросы в тот момент, когда на урезанной доске будет существовать лишь единственная расстановка n не бьющих друг друга ладей. Не умаляя общности можно считать, что эта единственная расстановка n ладей - по диагонали. Тогда для каждой пары клеток, симметричных относительно этой диагонали, о хотя бы одной из клеток этой пары угадывающий должен был задать вопрос. Действительно, поставив в противном случае ладей на эти клетки (и убрав двух подходящих ладей с диагонали), мы получим новую расстановку ладей, которая не противоречит ни одному из сделанных ответов. Но тогда мы вырезали из доски не менее n(n-1)/2 клеток.

1.5. В одну сторону это утверждение очевидно: если доска содержится в объединении k линий, то, поскольку на каждой линии может находиться не более одной ладьи, всего ладей не может быть больше k (так сказать, принцип Дирихле с быть-может-пересекающимися клетками).

В другую сторону это не просто. Мы перескажем доказательство из [8].

Минимальное число линий, в объединении которых помещается доска D, обозначим m(D). Пусть для исходной доски C m(C)=n. Будем удалять из доски C клетки, пока это возможно, так чтобы m не менялось. Полученную в результате доску обозначим C₁. Докажем, что ладьи, расставленные на всех клетках доски C₁, не будут бить друг друга. Этим будет установлено, что на исходной доске можно расставить n небьющих ладей.

Допустим, что это не так, и клетки x и y доски C₁ находятся на одной линии l. Из минимимальности доски C₁ следует, что доска C₁\x содержится в объединении семейства линий S_x, состоящего из (n-1) линии, а доска C₁\y содержится в объединении семейства линий S_y, также состоящего из (n-1) линии, причем lПS_x, lПS_y.

Пусть S - множество линий, входящих только в одно из семейств S_x, S_y (то есть симметрическая разность множеств S_x и S_y). Если пересечение множеств S_x и S_y состоит из m линий, то S состоит из 2(n-1-m) линий. Построим доску C₂, состоящую из всех клеток доски C₁, лежащих на пересечениях линий из SUl. Очевидно, x,yCC₂, и каждая клетка доски C₁, не лежащая в объединении линий из S_xЗS_y, принадлежит C₂. Множество SUl состоит из 2(n-1-m)+1 линий, поэтому доску C₂ можно покрыть семейством T, состоящем из (n-1-m) линий (для этого отнесем к T только горизонтальные или только вертикальные линии из SUl). А тогда вся доска C₁ покрывается семейством линий TU(S_xЗS_y). Но это семейство состоит из не более чем (n-1-m+m) линий, что противоречит определению доски C₁. Полученное противоречие показывает, что никакие две клетки доски C₁ не могут лежать на одной линии.

Отметим в качестве следствия следующую переформулировку этой задачи:

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

2.1. Например, R(x,C₁) = R(x,C₂) = 1+10x+14x²,
где

     _ _ _ _ _ _ _ _
C1= |_|_|_|_|_|_|_|_|
    |_|_|

     _ _ _ _ _ _ _ _
    |_|_|_|_|_|_|_|_|
C2= |_|
    |_|

2.2. У эквивалентных досок совпадают площади, но среди всех диаграмм с площадью n(n-1)/2   Т_n - единственная, на которой существует расстановка n-1 небьющих ладей.

2.3. Утверждение задачи легко выводится из теоремы Капланского или задачи 6.2., но мы дадим прямое, почти биективное доказательство, следуя [7]. Обозначим квадрат n*n через K_n.

Докажем утверждение задачи по индукции. Разобьем квадрат K_n на две части: квадрат K _n-1 и "рамку", состоящую из 2n-1 клеток. Треугольную доску Y_n тоже разобьем на две части: доску Y_n-1 и самую длинную горизонталь (тоже из 2n-1 клеток). Допустим, что совпадение ладейных чисел квадрата K_n-1 и треугольника Y_n-1 уже установлено. Тогда можно считать, что построено соответствие между расстановками ладей в квадрате n*n, в которых все ладьи находятся в выделенной части (n-1)*(n-1), и расстановками ладей в Y_n, в которых все ладьи находятся в выделенной части Y_n-1. Осталось построить соответствие между расстановками ладей в Y_n, которые содержат ладью на длинной горизонтали и расстановками ладей в K_n, которые содержат ладьи в "рамке". Рассмотрим все расстановки k ладей в Y_n, содержащих ладью в длинной строке, у котроых расстановка (k-1) ладей в Y_n-1 фиксирована, назовем ее s, а соответствующую ей расстановку в K_n-1 - t. Всего имеется 2n-k=n+(n-k) таких расстановок, поскольку в длинной строке ровно столько подходящих для последней ладьи клеток. Пронумеруем как-нибудь эти клетки (рис. 1).

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

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

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

Сверху вниз: Рис. 1, Рис. 2, Рис. 3.

2.4. Обозначим исходные эквивалентные доски A и B, пусть A' и B' - их дополнения в прямоугольнике m*n, R_p,q(x) - ладейный многочлен прямоугольника p*q. Пользуясь принципом включения-исключения, аналогично задаче 0.2., нетрудно вывести соотношение

R(x,A')=	S	rk(A)(-x)kRm-k,n-k(x)
	k

Для доски B есть аналогичное соотношение, и мы сразу получаем нужное равенство многочленов.

2.5. Будем считать, что m - это размер по вертикали. Подсчитаем сначала число способов расставить l ладей на доске AUC, если в части A стоит при этом k ладей. Эти k ладей всегда занимают k горионталей и могут быть поставлены r_k(A) способами. Остальные (l-k) ладей из части C могут занимать любые из n вертикалей доски C и любые из (m-k) горизонталей. Значит, мы можем расставить на доске C эти (l-k) ладей (l-k)!C^l-k_nC^l-k_m-k способами (как в задаче 0.4). А всего способов расставить l ладей на доске AUC указанным способом - r_k(A)(l-k)!C^l-k_nC^l-k_m-k. Следовательно, число способов расставить на доске AUC   l небьющих ладей (без других ограничений) равно

	l
rl(AUC)=	S	rk(A)(l-k)!Cl-knCl-km-k .
	k=0

Аналогичное вычисление верно для доски BUC, а так как ладейные числа досок A и B равны, мы получаем, что равны и ладейные числа досок AUC и BUC.

2.6. Мы приведем доказательство, не требующее никакого счета. Доказанную выше теорему Капланского (задача 2.5) нетрудно обобщить на случай двух пар эквивалентных досок, добавляемых к общей прямоугольной части справа и снизу. А именно, верна теорема:

Рассмотрим прямоугольник (m+q)*(n+p), который для удобства будем считать составленным из четырех частей: C - прямоугольника m*n, U - прямоугольника m*p, V - прямоугольника q*n и оставшегося прямоугольника q*p. Пусть A₁ и A₂ - эквивалентные доски, расположенные внутри части U, B₁ и B₂ - эквивалентные доски, расположенные внутри части V . Тогда доски A₁UB₁UC и A₂UB₂UC тоже эквивалентны.

Для доказательства таким же рассуждением, как и в теореме Капланского, следует проверить, что количество способов расставить l небьющих ладей на доске A₁UB₁UC равно

rl(A1UB1UC)=	S	ri(A1)rk(B1)(l-i-k)!Cl-i-km-iCl-i-kn-k
	i,k>0
	i+k<l

Поскольку первая доска представляет собой объединение прямоугольника 3*5 и двух частей вида

 _ _ _ _
|_|_|_|_|
|_|_|     ,

а вторая доска есть объединение прямоугольника 3*5 и частей вида

 _ _ _ _
|_|_|_|_|
|_|
|_|

и

 _ _ _
|_|_|_|
|_|_|_| ,

причем расположение этих частей удовлетворяет только что доказанной теореме, то для доказательства эквивалентности этих досок достаточно проверить что эквивалентны между собой малые доски

 _ _ _ _
|_|_|_|_|
|_|_|     ,
 _ _ _ _
|_|_|_|_|
|_|
|_|

и

 _ _ _
|_|_|_|
|_|_|_|  .

Эквивалентность первой и второй из этих досок, а также второй и третьей очевидна по теореме Капланского.

3.1. Очень грубое неравенство. Разбивая произвольным образом km небьющих ладей на m групп по k ладей, мы получаем набор из m расстановок k небьющих ладей. Число наборов, которые мы можем получить таким способом, конечно же, не превосходит (r_k)^m.

3.2. Из каждой расстановки (k+n) небьющих ладей можно C^k_k+n способами получить две расстановки небьющих ладей: первую - из k небьющих ладей, вторую - из n оставшихся небьющих ладей. Разным исходным расстановкам и разным способам выборки соответствуют разные пары, итого - C^k_k+nr_k+n пар. Общее же число пар "расстановка k ладей - расстановка n ладей" равно r_kr_n и заведомо не меньше указанного выше количества.

3.3. Рассмотрим произвольные четыре небьющих ладьи. Разбивая эту четверку ладей на две пары, что можно сделать тремя способами, мы получаем из нее пару различных расстановок двух небьющих ладей. Из произвольной расстановки трех небьющих ладей мы также можем получить пару различных расстановок двух ладей. Для этого назовем одну из ладей a (это тоже можно сделать тремя способами) и рассмотрим пары (a,b), (a,c), где b и c - две остальные ладьи. Таким образом из всех возможных расстановок трех или четырех небьющих ладей мы сможем получить 3r₃+3r₄ пар различных расстановок двух ладей, что не превосходит C²_r2 - общего числа пар расстановок двух ладей.

3.4. Из любой расстановки 12 небьющих ладей можно получить (упорядоченную) пару расстановок 9 ладей следующим способом: пометим любые 6 ладей, а остальные 6 ладей разобьем на два множества по 3 ладьи, причем, будем различать эти множества (одно из них будет первым, другое - вторым). Добавляя к каждому из этих множеств 6 помеченных ладей, мы получаем два набора из 9 небьющих ладей. Поскольку пометить ладей можно C⁶₁₂ способами, а разбить 6 оставшихся ладей на две группы по 3 ладьи можно C³₆ способами, мы заключаем, что получить пару расстановок 9 ладей из исходной расстановки 12 ладей можно C⁶₁₂C³₆=18480 способами. При этом из разных расстановок 12 ладей получаются разные пары, но, конечно, таким способом не удастся получить все (r₉)² пар. Значит, 18480r₁₂<(r₉)².

3.5. Из любой расстановки k небьющих ладей мы можем получить k-1 пар небьющих ладей, причем многими способами. Чтобы подсчитать это число способов, заметим, что любые k небьющих ладей можно считать естественным образом упорядоченными, например, по расположению их горизонталей сверху вниз. Тогда каждому способу выбора (k-1) пар небьющих ладей можно сопоставить граф, в котором имеется k помеченных вершин, соответствующих ладьям, и (k-1) ребер, соответствующих выбираемым парам. Чтобы наборы пар ладей, получаемые из различных исходных расстановок k ладей не пересекались, ограничимся рассмотрением только таких графов, в которых нет изолированных вершин. Тогда по (k-1) парам ладей исходная расстановка из k ладей легко восстанавливается, просто как объедининие всех ладей, входящих в эти (k-1) пар. Пусть N_k - число графов, состоящих из k помеченных неизолированных вершин и (k-1) ребер. Тогда N_k и есть искомое число способов, и мы, аналогично предыдущим задачам получаем неравенство

N_kr_k<C^k-1_r2 .

Для завершения доказательства заметим, что N_k>k^k-2, так как последняя величина выражает количество деревьев с k помеченными вершинами.

3.6. Так как r_n(B)>1, то r_n(B)>r₀(B). Рассмотрим любую из расстановок n небьющих ладей на доске B. Переставив при необходимости строки и столбцы, мы можем считать, что эти ладьи расположены на одной диагонали D. Очевидно, эта диагональ содержит ровно n клеток, принадлежащих доске B.

Зафиксируем k, 1< k < n/2. Возьмем произвольное k1, 1 < k1 < k и фиксируем любое расположение k1 небьющих ладей вне диагонали D. Пусть эти ладьи бьют m клеток диагонали D, k1+1<m<2k1. Тогда количество расстановок k ладей, в которых вне диагонали D стоит k1 ладей, причем в точности на выбранных местах, равно Cn-mk-k1. А количество расстановок (n-k) ладей, в которых вне диагонали D стоит k1 ладей, причем в точности на выбранных местах, равно Cn-k-k1n-m=Ck+k1-mn-m > Ck-k1n-m.

Таким образом, количество всех расстановок (n-k) ладей не меньше количества всех расстановок k ладей.

3.7. В случае возвратного многочлена вместо неравенств предыдущей задачи должны быть равенства. Заметим, что равенства будут иметь место, если в рассуждениях решения предыдущей задачи окажется m=2k₁. То есть, если любые k₁ небьющих ладей (k₁<n/2), расположенных вне диагонали D, бьют ровно 2k₁ клеток этой диагонали. Примеры досок для четного и нечетного n изображены на рисунке.

 _ _ _ _ _ _
|_|_|_|_|_|_|
  |_|_
    |_|_
      |_|_
        |_|_
          |_|

 _   _ _ _ _
|_|_|_|_|_|_|
  |_|_  |_|_|
    |_|_
      |_|_
        |_|_
          |_|

4.1. Применяя последовательно соотношение задачи 1.2 для клеток, расположенных вдоль одной стороны длины n, получаем требуемое.

4.2. Приравнивая коэффициенты при x^d_n+1-k в левой и правой части, получаем, что требуется доказать тождество:

r_k(D_n) = r_k(D_n-1) + (d_n-k+1)r_k-1(D_n-1) .

Это тождество выражает тот факт, что, расставляя k ладей на доске D_n, мы можем либо разместить их все в D_n-1, либо разместить (k-1) ладью в D_n-1, а последнюю ладью поставить в самой длинной строчке на одно из (d_n-k+1) допустимых мест.

4.3. Заметим, что расстановки черных слонов распадаются на два множества: те, в которых есть слон на клетке a1, и остальные. Если на клетке a1 стоит слон, то остальные чернопольные слоны могут стоять где угодно за исключением большой побочной диагонали доски. Отметим, что множество всех черных клеток доски (2n+1)*(2n+1), не лежащих на побочной диагонали, изоморфно, в смысле связности ходом слона, множеству всех черных клеток доски 2n*2n (или, что то же, множеству ее белых клеток). Поэтому

число расстановок k чернопольных слонов на доске (2n+1)*(2n+1) со слоном на a1 равно числу расстановок (k-1) белопольных слонов на доске 2n*2n.

Теперь докажем, что

число расстановок k чернопольных слонов на доске (2n+1)*(2n+1) без клетки a1 равно числу расстановок k белопольных слонов на доске (2n+1)*(2n+1).

То есть мы хотим доказать эквивалентность "чернопольной без a1" и белопольной "поддосок" доски (2n+1)*(2n+1) (вид этих досок для n=3 показан на рисунке).

       _
     _|_|_
   _|_|_|_|_
 _|_|_|_|_|_|_
|_|_|_|_|_|_|_|
  |_|_|_|_|_|
    |_|_|_|

     _ _
   _|_|_|_
 _|_|_|_|_|_
|_|_|_|_|_|_|
|_|_|_|_|_|_|
  |_|_|_|_|
    |_|_|

Эквивалентность этих досок сразу следует из результата задачи 6.2. Но мы докажем эту эквивалентность, пользуясь теоремой Капланского (задача 2.5). Действительно, расположим доски так, как это сделано в примере выше, и вычеркнем из обеих досок самую длинную вертикаль длины (n-1). По теореме Капланского, эквивалентность полученных досок равносильна эквивалентности исходных.

     _ _
   _|_|_|_
 _|_|_|_|_|_
|_|_|_|_|_|_|
  |_|_|_|_|
    |_|_|

     _
   _|_|_
 _|_|_|_|_
|_|_|_|_|_|
|_|_|_|_|_|
  |_|_|_|
    |_|

Теперь сделаем еще один шаг: из первой (бывшей чернопольной) доски вычеркнем самую длинную горизонталь, а из второй доски - опять самую длинную вертикаль. Вычеркиваемые ряды клеток, нетрудно видеть, будут иметь одинаковую длину. Опять по теореме Капланского эта операция не меняет отношения эквивалентности досок. Но в результате последнего вычеркивания получаются одинаковые доски!

Итак, мы проверили два утверждения, выделенных выше зауживанием. Эти два утверждения и дают требуемое равенство многочленов.

5.1. Рассмотрим какую-нибудь расстановку k небьющих ладей. Если на клетке (i,j) стоит ладья, поместим числа i и j в одно подмножество. Перебрав всех ладей, мы получим разбиение множества {1,2,...,n} на (n-k) подмножеств. Очевидно, что это соответствие взаимно-однозначно.

5.2. Ответ: это граф G, вершины которого пронумерованы числами от 1 до n, а ребра соединяют вершины, номера которых отличаются на 1.

Клетки доски T^~_n можно считать помеченными парами чисел (i,j) (почти как на шахматной доске). Конструкция решения 5.1 по расстановке k ладей дает разбиение множества {1, 2,..., n} вершин графа G на (n-k) подмножеств. Раскрасив каждое подмножество в свой цвет, мы получим правильную раскраску вершин графа. Действительно, если вершины i₁>i₂>i₃>i₄>... попали в одно подмножество, то это значит, что в расстановке имеются ладьи (i₁, i₂), (i₂, i₃), (i₃, i₄), ...(это следует из того, что ладьи не бьют друг друга). Но тогда, по определению доски T^~_n,   i₁-i₂>1, i₂-i₃>1, .... Это значит, что никакие две из вершин i₁, i₂, i₃, ... не соединены друг с другом в нашем графе.

Таким образом, имеется взаимно-однозначное соответствие между расстановками k ладей в T^~_n и раскрасками в (n-k) цветов вершин графа G .

5.3. Можно считать, что при подходящем n   BcT_n. Клетки доски B будем считать помеченными парами чисел (i,j).В качестве множества вершин графа G_B возьмем множество чисел от 1 до n. Вершины i и j (i>j) соединим ребром только в том случае, если (i,j) не принадлежит B. Если доска B обладает следующим дополнительным свойством: вместе с двумя клетками (i,j) и (j,k) она обязательно содержит клетку (i,k), то рассуждения предыдущей задачи дают взаимно-однозначное соотвествие между расстановками ладей и раскрасками графа. Действительно, наличие на доске ладей (i₁, i₂), (i₂, i₃), (i₃, i₄), ..., благодаря упомянутому свойству, означает, что доска содержит все клетки вида (i_s,i_t), s>t, а это по определению G_B значит, что никакие две из вершин i₁, i₂, i₃, ... не соединены друг с другом в графе G_B.

Осталось заметить, что при больших n мы можем обеспечить требуемое дополнительное свойство, сдвинув доску подальше вправо так, чтобы x-координата любой клетки доски была бы больше y-координаты любой клетки.

5.4. Нет, неверно.

5.5. Достаточно применить конструкцию решения 3.3 к двум эквивалентным доскам (см. пример на рисунке). Единственное за чем нужно проследить - что получающиеся графы не отличаются лишь перестановкий меток у вершин.

6.1. Обе части доказываемого равенства равны количеству расстановок m небьющих ладей на диаграмме Юнга со строками b₁+p, b₂+p, ..., b_m+p. Для правой части это так, поскольку мы можем выбрать место для ладьи в первой строке b₁+p способами, после этого место для ладьи во второй строке - b₂+p-1 спосособами и т.д. Левая часть выражает другой способ подсчета. Считая что доска представляет собой объединение прямоугольника p*m и исходной диаграммы B, поставим на часть B   k небьющих ладей. Это можно сделать r_k(B) способами. Чтобы разместить остальных ладей в прямоугольной части, мы выбираем место для первой ладьи в первой свободной строке (p способов), затем выбираем место для второй ладьи во второй свободной строке (p-1 способов) и т.д., всего (p!)/((p-m+k)!) способов.

Замечание. Так как левая и правая части доказанного равенства являются многочленами от p и совпадают для бесконечного множества значений p, то они на самом деле совпадают при всех pCR.

6.2. Рассмотрим равенство задачи 6.1. как равенство двух многочленов переменной p. Заметим, что эти многочлены одозначно определяются числами r_k(B). Действительно, r₀(B) - это коэффициент при старшей степени m, коэффициент при (m-1)-й степени линейно выражается через r₀(B) и r₁(B), коэффициент при (m-2)-й степени линейно выражается через r₀(B), r₁(B) и r₂(B), и т. д. Но тогда диаграммы, имеющие одинаковые наборы S(B_i), имеют одинаковые правые части в равенствах задачи 6.1. Поэтому все их ладейные числа совпадают.

6.3. Ответ: 3^n-1.

6.4. Если строки диаграммы B различны и не равны нулю, то числа набора S(B) образуют неубывающую последовательность натуральных чисел. Добавление нескольких нулевых строчек не скажется на ладейных числах и приведет к тому, что набор S(B) будет содержать в начале строго убывающий фрагмент 0, -1, -2, ...(каждый раз уменьшение на единицу), а после него - нестрого возрастающий. Обратно, каждый набор указанного вида соответствует некоторой "строго монотонной" диаграмме Юнга. Нам остается только заметить, что если набор произвольной диаграммы содержит отрицательные числа, то они встречаются там "без пропусков", то есть, вместе с каждым отрицательным s этот набор содержит все целые числа из промежутка [s, 0]. Это ясно сразу из определения.

Проиллюстрируем описанное соответствие примером. Диаграмме со строками 1, 1, 1, 2, 4 соответствует набор 1, 0, -1, -1, 0. Упорядочим его так: 0, -1, -1, 0, 1. Такому набору соответствует диаграмма 0, 0, 1, 3, 5. Значит, искомая диаграмма - это 1, 3, 5.

7.1. Требуется придумать такие доски С, для которых в указанном множестве досок значение выражения R(1,C) максимально. Пусть C_n - искомая доска из n клеток, L_n(x)= R(x,C_n) - ее ладейный многочлен. Выберем какую-нибудь клетку c доски C_n. Пусть C^~_n - доска, получающаяся из C_n удалением вертикали и горизонтали, содержащих клетку c. В силу связности доски C_n, доска C^~_n состоит не более чем из (n-2) клеток (мы действительно что-то выкинем помимо клетки c), пусть она содержит (n-k) клеток (k>2).

Мы утверждаем, что доска C^~_n состоит из не более чем (k-1) компонент связности относительно хода ладьи. Это легко проверить по индукции, например, база индукции, k=2 - достаточно очевидна. Ясно, что к любой доске, состоящей из двух компонент связности относительно хода ладьи, можно так добавить одну клетку, что полученная доска окажется связной (достаточно добавить клетку, расположенную на пересечении вертикали, проходящей через какую-нибудь клетку первой компоненты, и вертикали, проходящей через какую-нибудь клетку второй компоненты). Следовательно, к доске C^~_n можно добавить (k-2) клетки так, что полученная доска - обозначим ее D_n - будет связна относительно хода ладьи. Заметим, что

R(1,C^~_n)<R(1,D_n)<L_n-2(1) ,

поскольку простое добавление клеток к доске C_^~n не уменьшает количество ладейных расстановок, а последующая оптимизация по всем (n-2)-клеточным доскам также не уменьшит это количество. По формуле из задачи 1.2

L_n(1)=R(1,C_n\{c})+R(1,C^~_n) < L_n-1(1)+L_n-2(1) .

Итак,

L_n(1) < L_n-1(1)+L_n-2(1) .      (4)

Заметим теперь, что последовательность "лестничных" досок

      _ _
      |_|_|_
        |_|_|_
 Cn =     |_|_|     (всего n клеток)
            |_|
              ...

обладает тем свойством, что при малых n эти доски действительно дают максимум числа расстановок (проверяется перебором для n=1, 2), а ладейные многочлены этих досок (мы их, конечно же, обозначим L_n) удовлетворяют соотношению (возьмем в качестве c самую верхнюю клетку)

L_n(x) = L_n-1(x) + xL_n-2(x) .      (5)

Из рассуждений перед формулой (4), несложной индукции и формулы (5) следует, что указанные доски C_n служат ответом в этой задаче, в формуле (4) на самом деле имеет место равенство, а искомое число способов для доски из n клеток равно числу Фибоначчи u_n (с начальными условиями u₁=1, u₂=2).

7.2. Докажем утверждение индукцией по n. База n=0, 1 очевидна. Переход следует из тождества

sin((n+1)j) + sin((n-1)j) = 2 sin(nj) cos j .

Заодно получаем рекуррентную формулу

U_n+1(x) =2xU_n(x) -U_n-1(x)

7.3. Из полученного в предыдущей задаче рекуррентного соотношения легко вывести рекуррентную формулу для многочленов U_n с четными номерами:

U_2n(y) = (4y²-2)U_2n-2(y)-U_2n-4(y)     (6)

А из формулы (5) нетрудно вывести рекуррентную формулу для многочленов L_n с нечетными номерами:

L_2n-1(x) = (1+2x)L_2n-3(x)-x²L_2n-5(x)     (7)

Положим y=(-1/(4x))^1/2, тогда из формулы (6)

U_2n(y) = (-(1/x)-2)U_2n-2(y)-U_2n-4(y)

Домножим на (-x)ⁿ

(-x)ⁿU_2n(y) = (2x+1)(-x)^n-1U_2n-2(y)-x²(-x)^n-2U_2n-4(y) .     (8)

Выражение (-x)^kU_2k(-1/(4x))^1/2 на самом деле является многочленом (степени 2k). Это следует из того, что все слагаемые-одночлены в U_2k(y) имеют четную степень по y (видно из соотношения (6) ). Сравнивая (7) и (8), мы видим, что для завершения доказательства осталось проверить совпадение начальных условий. Но так как L₁(x)=1+x, L₃(x)=1+3x+x², U₂(y)=4y²-1, U₄(y)=16x⁴-12x²+1, то при n=1, 2 равенство L_2k-1=(-1)^kx^kU_2k(-1/(4x))^1/2 имет место.

Аналогично можно установить, что L_2k=(-x)^k(-x)^1/2U_2k+1(-1/(4x))^1/2 .

В задаче 7.1 мы выяснили, что L_2k-1(1) - число Фибоначчи. Как результат задачи 7.3 соотносится с формулой Бине?

8.1. Благодаря формуле из задачи 4.2, эта задача - стандартное упражнение на примененение теоремы Ролля.

По теореме Фоата-Шютценберже произвольная диаграмма Юнга эквивалентна строго монотонной диаграмме Юнга. Ладейный многочлен строго монотонной диаграммы Юнга с n строками имеет степень n. Поэтому для доказательства утверждения задачи достаточно проверить, что функция q_n(x) из задачи 4.2. имеет n вещественных отрицательных корней. Это легко проверяется по индукции. Будем пользоваться обозначениями задачи 4.2. При n=1   R(x,B₁)=1+h₁x, q₁(x)=e^x(x^h₂+h₁x^h₂-1). Как видим, функция q₁ имеет отрицательный корень, кроме того q(0)=q(-oo)=0. Это значит, что функция q'₁(x) имеет не менее двух отрицательных корней (это и есть теорема Ролля). По формуле задачи 4.2, отсюда следует, что функция q₂(x) имеет не менее двух отрицательных корней (а больше двух, как следует из свойств R(x,D₂), она иметь не может, значит, их ровно два). Кроме того, опять q₂(0)=q₂(-oo)=0. Значит, q₃ имеет не менее трех вещественных корней, и т. д.

8.2. Обозначим F(x)=f(x)+xS^k_i=1g_i(x). Из свойств 2 и 3 разделения корней следует, что старшие коэффициенты многочленов f и g_i положительны и при x>0   f(x)>0 и g_i(x)>0. Значит, степень F равна или на единицу больше степени f, и у F нет положительных корней. Далее, если 0>x₁>x₂>... - корни многочлена f, то из свойства разделения корней следует, что F(x₁)<0, F(x₂)>0, F(x₃)<0 и т.д. Следовательно, у многочлена F имеется корень на каждом из промежутков (x₁, 0), (x₂, x₁), (x₃, x₂) ..., а если deg F = (deg f)+1, то еще и на промежутке (-oo, x_deg f), причем на каждом из упомянутых промежутков есть ровно один корень. Значит, f разделяет корни F.

8.3. Пусть l - произвольная горизонталь доски B; c₁, c₂, ..., c_k - все клетки доски B, лежащие на этой горизонтали l; B_l - доска, получающаяся из B вычеркиванием горизонтали l; B_i - доска, получающаяся из B вычеркиванием горизонтали l и вертикали, содержащей клетку c_i. Тогда, аналогично задаче 4.1, имеет место соотношение

	k
R(x,B)=R(x,Bl)+x	S	B(x,Bi) .       (9)
	i=1

Аналогичное соотношение имеется для вертикалей доски B.

Докажем индукцией по площади доски B, что ладейный многочлен доски B', полученной из B вычеркиванием строки или столбца, разделяет корни ладейного многочлена доски B. Для доски, состоящей из одной или двух клеток, это утверждение очевидно. Если для досок, не превосходящих по площади (n-1) утверждение задачи уже установлено, то, благодаря соотношению (9) и результату задачи 8.1, мы сразу получаем что многочлен R(x,B_l) разделяет корни многочлена R(x,B) (для столбцов аналогично).

Утверждение задачи является частью доказанного утверждения.

8.4. Докажем, что если

r_nxⁿ+ r_n-1x^n-1+ ...+r₀ =r_n(x+a₁) (x+a₂)...(x+a_n),      (10)

где все a_i положительны, то при всех k   r_k-1r_k+1 <(r_k)².

Это неравенство - свойство симметрических функций от a_i, оно имеет отношение к ладейным многочленам лишь постольку, поскольку выполнено утверждение задачи 8.2.

Поскольку доказываемое неравенство однородно, можно считать, что r_n=1. Тогда по теореме Виета (или если просто раскрыть скобки)

rk=	S	ai1ai2...aik
	1<i1<i2<...<ik<n

Тогда выражение r_k-1r_k+1 -(r_k)² состоит из слагаемых вида (a_j1)²(a_j2)²...(a_js)²a_js+1...a_jk+s, причем каждое такое слагаемое входит с коэффициентом C^s-1_2s-C^s_2s<0.

8.5. Нет, неверно. Например, для доски

 _ _
|_|_|_
  |_|_|_
    |_|_|
      |_|

r₀=1, r₁=7, r₂=15, и неравенство не выполнено.

8.6. Для монотонной диаграммы с n строками мы сразу имеем в равенстве (10) r_n=1. Само утверждение задачи тогда - это обычное неравенство о симметрических средних.

Как и в предудущей задаче, будем воспринимать r_k как симметрические функции от переменных a_i. Докажем неравенство

(r_k/C^k_n)^1/(n-k) > (r_m/C^m_n)^1/(n-m)     при k>m .

Пусть a₁ - наименьшее, a₂ - наибольшее из чисел a_i. Обозначим для краткости a=(r_k/C^k_n)^1/k. Тогда, как нетрудно сообразить, a₁<a<a₂. Идея состоит в том, чтобы заменить число a₁ на a, а a₂ - на такое число b, чтобы величина выражения r_k не изменилась, а r_m - увеличилась. Выполняя такие замены несколько раз подряд, мы придем к набору одинаковых чисел a_i; доказываемое неравенство при этом, очевидно, обратится в равенство.

Поскольку r_k(a₁,...,a_n)=a₁a₂r'_k-2 + (a₁+a₂)r'_k-1 + r'_k, где r'_k=r_k(a₃,...,a_n-2) и т. п., то, ставя целью, чтобы r_k не менялось, мы приходим к уравнению

a₁a₂r'_k-2 + (a₁+a₂)r'_k-1 + r'_k = abr'_k-2 + (a+b)r'_k-1 + r'_k .

Из этого уравнения мы найдем b. Отметим одно полезное соотношение, которое сразу следует из этого уравнения:

(ab-a₁a₂)r'_k-2 = -(a+b-a₁-a₂)r'_k-1 .     (11)

Далее, r_m(a,b,a₃,...,a_n)-r_m(a₁,a₂,a₃,...,a_n) = (ab-a₁a₂)r'm-2+(a+b-a₁-a₂)r'_m-1+r'_m . Пользуясь (11), находим, что знак последнего выражения такой же как у выражения

(a+b-a₁-a₂)((r'_m-1/r'_m-2)-(r'_k-1/r'_k-2)) .

Нарвенство r_m-1r_k-2<r_m-2r_k-1 следует из предыдущей задачи и показывает, что второй сомножитель отрицателен. Из (11) мы получаем, что

sign(a+b-a₁-a₂) = sign(a₁a₂-ab) = sign(a(a+b-a₁-a₂)+a₁a₂-ab) = sign((a-a₁)(a-a₂)) = -1

Таким образом, замена a₁, a₂ на a, b действительно приводит к увеличению r_m.

Литература:

Задачи 1.1, 1.2, 2.2-2.5, 4.1, 4.3, 7 обсуждаются в [1]. Задачи 5.1, 6 - в замечательной книге [2]. Связь с хроматическими числами (задачи 5.2-5.5) разъяснена в [3]. Сюжет с корнями ладейных полиномов взят из [4] (задачи 4.2, 8.1) и [5] (задачи 8.2, 8.3). Доказательства неравенств 8.4, 8.6 приведены по книге [6].
1. Риордан Дж. Введение в комбинаторный анализ. М., ИЛ, 1963.
2. Стенли Р. Перечислительная комбинаторика. М., "Мир", 1990.
3. Goldman J. L., Joichi J. T., White D. E. Journal of Comb. Theory, Ser. B, V. 25 (1978), 135-142.
4. Goldman J. L., Joichi J. T., White D. E. Journal of Comb. Theory, Ser. A, V. 21 (1976), 230-239.
5. Nijenhuis A. Journal of Comb. Theory, Ser. A, V. 21 (1976), 240-244.
6. Харди Г. Г., Литтльвуд Д. Е., Полиа Г. Неравенства. М., ИЛ, 1948.
7. Левит А. Частное сообщение.
8. Ловас Л., Пламмер М., Прикладные задачи теории графов. М., Мир, 1998.