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

Проект МЦНМО
при участии
школы 57
Задача 73685
Темы:    [ Задачи с ограничениями ]
[ Целочисленные решетки ]
[ Индукция (прочее) ]
[ Объединение, пересечение и разность множеств ]
Сложность: 5
Классы: 10,11
В корзину
Прислать комментарий

Условие

P и Q – подмножества множества выражений вида  (a1, a2, ..., an),  где ai – натуральные числа, не превосходящие данного натурального числа k (таких выражений всего kn). Для каждого элемента  (p1, ..., pn)  множества P и каждого элемента  (q1, ..., qn)  множества Q существует хотя бы один такой номер m, что  pm = qm.  Докажите, что хотя бы одно из множеств P и Q состоит не более чем из kn–1 элементов для
  а)  k = 2  и любого натурального n;
  б)  n = 2  и любого натурального  k > 1;
  в) произвольного натурального n и произвольного натурального  k > 1.


Решение

  a) Набор d назовём противоположным набору d, если d получен из d заменой всех единиц на двойки, а двоек – на единицы. Обозначим через M множество всех наборов, противоположных наборам из M. Наборы d и d ни на одном месте не совпадают. Поэтому, если d входит в P, то d не может входить в Q. Значит, P и Q не содержат одинаковых наборов. Поэтому либо в P, либо в Q не более половины всех наборов. Но в P и в P одинаковое количество наборов. Значит, либо в P, либо в Q не более чем 2n–1 наборов.

  б) Для  n = 2  задачу можно сформулировать так: k² точек расставлены на плоскости в узлах квадратной решетки  (k–1)×(k–1).  Некоторые из этих точек нужно закрасить красным, некоторые – синим цветом так, чтобы каждая пара из красной и синей точек лежала либо в одном столбце, либо в одной строке. Одну точку можно закрашивать в оба цвета. Нужно доказать, что точек какого-то одного цвета не более k. Разберём два случая.
  1) В подмножестве P есть два таких набора  (a1, a2)  и  (b1, b2),  что  a1b1  и  a2b2.  Тогда в Q могут входить только два набора  (a1, b2)  и
(b1, a2).  Но  2 ≤ k,  и утверждение верно.
  2) В подмножестве P каждые два набора совпадают в одном месте (для определенности – в первом). Тогда все наборы из P имеют вид  (a, b),  где a фиксировано. Но таких наборов не более k.

  в) Пусть P содержит p, а Q – q наборов. Достаточно доказать, что  p + q ≤ 2kn–1.  Проведём индукцию по n. База  (n = 1)  очевидна.
  Шаг индукции. Пусть для наборов длины n утверждение доказано. Рассмотрим удовлетворяющие условию множества наборов P и Q длины
n + 1.
  Обозначим через Pi множество всех наборов из P, оканчивающихся числом i  (1 ≤ i ≤ k).  Зачеркнув в наборах из Pi последнее число i, мы получим множество Pi' наборов длины n. Число наборов в Pi (их столько же, сколько в Pi') обозначим через pi. Аналогично рассмотрим множества Qi, Qi' и числа qi.
  Пусть  i ≠ j.  По условию каждые два набора из Pi и Qj совпадают хотя бы в одном месте, но в последнем месте они совпадать не могут. Поэтому каждые два набора из Pi' и Qj' совпадают хотя бы в одном месте. По предположению индукции  pi + qj ≤ 2kn–1.
  Сложим все эти неравенства (всего их  k(k–1)).  Поскольку каждое pi (и каждое qj) входит ровно в  k – 1  неравенство, а   p1 + ... + pk = p,
в результате получим  (k – 1)p + (k – 1)q ≤ 2(k – 1)kn.  Значит,  p + q ≤ 2kn,  что и требовалось.

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

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

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

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