М1752. Восемь шахматных ладей

Задача из журнала «Квант» (2000 год, 6 выпуск)

Условие

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

Решение

Если не выдвигать ограничений на цвет полей, то $8$ ладей допустимым образом можно расставить $8!$ различными способами; вообще для доски размером $n\times{n}$ число способов расстановки n ладей равно числу перестановок из n элементов, т.е. $n!$.

Но нам нужно учесть ограничение на цвет полей: ладьи расставляются только на черных полях доски. Перекрасим черные поля доски в красный и синий цвета. При этом всякое черное поле, расположенное на нечетной вертикали (но на четной горизонтали), сделаем красным, а всякое черное поле, расположенное на четной вертикали (но на нечетной горизонтали), сделаем синим (см. рисунок). Из $8$ ладей, стоящих допустимым образом на черных полях, $4$ ладьи окажутся на красных полях, а остальные $4$ ладьи – на синих.

Красные поля образуют как бы отдельную шахматную доску размером $4\times4$, поэтому число способов расстановки $4$ ладей на красных полях равно $4! = 24$. То же можно сказать о синих полях.

В результате число способов для допустимых расстановок $8$ ладей равно $24^2.$

Ответ: $24^2$.

В. Произволов

М1761. Ящики фокусника

Задача из журнала «Квант» (2001 год, 1 выпуск)

Условие

У фокусника [latex]100[/latex] карточек, занумерованных числами от [latex]1[/latex] до [latex]100.[/latex] Он раскладывает все карточки в три ящика – красный, белый и синий – так, чтобы в каждом ящике лежала хотя бы одна карточка. Один из зрителей выбирает два из трех ящиков, вынимает из них по одной карточке и объявляет сумму номеров вынутых карточек. Зная эту сумму, фокусник определяет тот ящик, из которого карточки не вынимались. Сколькими различными способами можно разложить карточки по ящикам так, чтобы этот фокус всегда удавался?
(Способы, при которых хотя бы одна карточка попадает в разные ящики, считаются различными.)

Ответ: [latex]12.[/latex]

Решение

Пусть карточка [latex]1[/latex] (или число [latex]1[/latex]) лежит в красном ящике
(сокращенно КЯ), а карточка с наименьшим числом [latex]k,[/latex] не лежащая в КЯ, лежит в белом ящике (БЯ). Тогда [latex]k-1[/latex] находится в КЯ.
По условию, в синем ящике (СЯ) есть хотя бы одна карточка; пусть [latex]n[/latex] – наименьшее число (т.е. карточка с наименьшим числом) в СЯ [latex]\to [/latex] [latex]n > k.[/latex] Если [latex]n-1[/latex] лежит в КЯ, то зритель может вытащить либо [latex]n-1[/latex] и [latex]k[/latex] из КЯ и
БЯ, либо [latex]n[/latex] и [latex]k-1[/latex] из СЯ и КЯ. Суммы чисел на карточках одинаковы, значит, в этом случае фокус не удастся.
Следовательно, [latex]n-1[/latex] находится в БЯ. Предположим, что карточка [latex]2[/latex] лежит в КЯ. Тогда взяв либо [latex]2[/latex] и [latex]n-1[/latex] из КЯ и БЯ, либо [latex]1[/latex] и [latex]n[/latex] из КЯ и СЯ, получим одинаковые суммы, значит, [latex]k=2[/latex] и [latex]2[/latex] находится в БЯ.
Рассмотрим два случая.

  1. В КЯ нет других карточек, кроме [latex]1.[/latex] Покажем, что тогда [latex]n=100.[/latex] Пусть [latex]n<100.[/latex] Тогда [latex]n+1[/latex] лежит либо в БЯ, либо в СЯ. Пары карточек [latex](1, n+1)[/latex] и [latex](2, n)[/latex] с одинаковой суммой находятся в (КЯ, БЯ (СЯ)) и в (БЯ, СЯ) – фокус не удался. Значит,[latex]n=100 ,[/latex] т.е. в СЯ только одна карточка [latex]100,[/latex] в КЯ – одна карточка [latex]1,[/latex] в БЯ – карточки [latex]2, 3, \ldots , 99 .[/latex] Покажем, что в этом случае фокус всегда удается: если мы берем карточки из БЯ и КЯ, то получаем суммы [latex]3, 4, \cdots ,100 ,[/latex] если из КЯ и СЯ – сумму [latex]101,[/latex] если из БЯ и СЯ – суммы [latex]102, 103, \cdots , 199,[/latex] т.е. суммы различны.
  2. В КЯ есть другие числа, и [latex]m[/latex] – наименьшее из них. Тогда [latex]m > 2 ,[/latex] значит, [latex]m-1[/latex]не лежит в КЯ. Если [latex]m-1[/latex] находятся в БЯ, то для пар [latex](m-1, n) ,[/latex] из БЯ и СЯ и [latex](n-1, m) ,[/latex] из БЯ и СЯ фокус не удастся. Значит, [latex]m-1[/latex] лежит в СЯ.

Лемма 1

Если в двух различных ящиках лежат карточки
[latex]x[/latex] и [latex]x+1[/latex], а в третьем [latex]y[/latex] и [latex]y+1,[/latex] то фокус не удастся.

Одинаковые суммы имеют пары [latex](x, y + 1)[/latex] и [latex](x+1, y)[/latex], из разных пар ящиков.

Лемма 2

Если в одном ящике лежат карточки [latex]x[/latex] и [latex]y,[/latex] а в
двух других [latex]x+1[/latex] и [latex]y+1[/latex] соответственно, то фокус не удастся.

Доказательство дословно повторяет доказательство леммы [latex]1.[/latex]

Выше мы показали, что для каждой пары ящиков есть карточки с двумя последовательными числами, а именно
КЯ, БЯ : [latex]1,2,[/latex]
БЯ, СЯ : [latex]n-1, n,[/latex]
СЯ, БЯ : [latex]m — 1, m.[/latex]
Значит, по лемме [latex]1[/latex] ни в одном из ящиков нет карточек с двумя последовательными числами.
Далее, полагая, что [latex]y = 1,[/latex] если [latex]x[/latex] лежит в КЯ и [latex]x + 1[/latex] – в
СЯ, и [latex]y = n — 1,[/latex] если [latex]x[/latex] находится в БЯ и [latex]x + 1[/latex] – в КЯ,
по лемме [latex]2[/latex] получаем, что в этих случаях фокус не удастся.
Аналогично фокус не удастся, если [latex]x[/latex] лежит в СЯ, а [latex]x + 1[/latex] в БЯ. Итак, если а находится в КЯ, то [latex]a + 1[/latex] – в БЯ, [latex]a + 2[/latex] – в СЯ, [latex]a + 3[/latex] – в БЯ и т.д. Значит, в КЯ находятся числа, сравнимые с [latex]1[/latex] по модулю [latex]3[/latex], в БЯ – сравнимые с [latex]2,[/latex] в СЯ – делящиеся на [latex]3.[/latex] Покажем, что такое расположение карточек подходит: сумма чисел на карточках из КЯ и БЯ делится на [latex]3,[/latex] из КЯ и СЯ сравнима с [latex]1[/latex] по модулю 3, из СЯ и БЯ – с [latex]2,[/latex] т.е. всегда можно определить, из каких ящиков взяты карточки.
Мы получили, что если карточка [latex]1[/latex] лежит в КЯ, а карточка с наименьшим числом не из КЯ находится в БЯ, то есть два варианта раскладывания карточек. Аналогично рассуждаем в случае других пяти пар ящиков. Значит, всего имеется [latex]2 \times 3 \times 2 = 12[/latex] различных способов.

Н. Агаханов, А. Гайфуллин