ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73771
Темы:    [ Десятичная система счисления ]
[ Шахматные доски и шахматные фигуры ]
[ Принцип крайнего (прочее) ]
[ Принцип Дирихле (прочее) ]
[ Геометрические интерпретации в алгебре ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

а) Имеется 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  ладьи можно выбрать шесть таких, что никакие две не бьют друг друга.

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

журнал
Название "Квант"
год
Год 1973
выпуск
Номер 12
Задача
Номер М236

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .