|
|
 |
Условие
а) Имеется 51 двузначное число. Докажите, что из этих чисел можно выбрать по крайней мере 6 чисел так, чтобы никакие два из выбранных чисел ни в одном разряде не имели одинаковой цифры.
б) Даны натуральные числа k и n, причём 1 < k < n. Для какого наименьшего m верно следующее утверждение: при любой расстановке m ладей на доске размером n×n клеток можно выбрать k ладей из этих m так, чтобы никакие две из этих выбранных ладей не били друг друга?
Решение
б) n(k – 1) ладей можно расставить в первых k – 1 столбцах, и тогда больше чем k – 1 ладей выбрать невозможно.
Лемма. При n > 1, 1 < k < n из n(k – 1) + 1 ладей всегда можно выбрать такую, что в её кресте – проходящих через ладью столбце и строке – стоит не более чем n + k – 2 ладьи.
Доказательство. Пусть этого сделать нельзя. Выберем среди всех рядов (строк и столбцов) тот, в котором ладей больше всего; обозначим их число через l. По предположению в кресте каждой из этих ладей стоит по крайней мере n + k – 1 ладья; значит, всего ладей не меньше
l(n + k – 1 – l) + l = l(n + k – l). При этом n + k – l ≤ l ≤ n, откуда l ≥ k. Следовательно, l(n + k – l) – nk = (n – l)(l – k) ≥ 0, то есть
l(n + k – l) ≥ nk > n(k – 1) + 1, если n больше единицы. Противоречие.
Докажем индукцией по n, что m = n(k – 1) + 1 ладей достаточно. Докажем индукцией по n, что m = n(k – 1) + 1 ладей достаточно.
Шаг индукции. Отметим ладью, в кресте которой стоит не более чем n + k – 2 ладьи, и вырежем её крест из доски. Из оставшихся частей составим доску (n–1)×(n–1). На новой доске будет не меньше m – (n + k – 2) = (n – 1)(k – 2) + 1 ладей. По предположению индукции при
k > 2 можно выделить k – 1 ладью так, что никакие две не бьют друг друга. При k = 2 это очевидно. Добавляя к ним выбранную ранее ладью, получим нужные k ладей.
а) Возьмём n = 10, k = 6. Обозначим произвольное двузначное число через xy (x = 1, ..., 9; y = 0, 1, ..., 9). Будем считать, что ладья соответствует числу ab, если она стоит в a-й строке и b-м столбце доски(нумерацию строк и столбцов доски начинаем с нуля; ладьи все будут размещаться даже в прямоугольнике 9×10). Две ладьи бьют друг друга тогда и только тогда, когда у соответствующих им чисел совпадают цифры в одном из разрядов. В б) доказано, что из 10·5 + 1 = 51 ладьи можно выбрать шесть таких, что никакие две не бьют друг друга.
