Выбрана 1 задача 
Убрать все задачи
Саша спускался по лестнице из своей квартиры к другу Коле, который живет на первом этаже. Когда он спустился на несколько этажей, оказалось, что он прошёл треть пути. Когда он спустился ещё на один этаж, ему осталось пройти половину пути. На каком этаже живёт Саша?
Решение
|
|
 |
Условие
а) Имеется 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 ладьи можно выбрать шесть таких, что никакие две не бьют друг друга.
