|
|
 |
Условие
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), что a1 ≠ b1 и a2 ≠ b2. Тогда в 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, что и требовалось.
