Из чисел 1, 2, $\ldots$, $k$ составляются всевозможные наборы $(a_1,a_2,\ldots,a_n)$ длины $n$ (легко видеть, что их $k^n$). Выбраны два подмножества $P$ и $Q$ таких наборов (один и тот же набор может входить и в $P$, и в $Q$). Известно, что если взять произвольный набор $(p_1,p_2,\ldots,p_n)$ из $P$ и произвольный набор $(q_1,q_2,\ldots,q_n)$ из $Q$, то они будут совпадать хотя бы в одном месте (т. е. $p_i=q_i$ для некоторого $i$). Тогда либо в $P$, либо в $Q$ не более чем $k^{n-1}$ наборов.
Докажите это утверждение
для $k=2$ и любого $n$;
для $n=1$, 2, З и любого $k\ge2$;
для произвольных $k\ge2$ и $n\ge1$.
Попробуйте найти другие ограничения на количество элементов в подмножествах $P$ и $Q$, связанных таким условием.
а) $k=2$. Набор $\overline d$ назовём противоположным набору $d$, если
$\overline d$ получен из $d$ заменой всех 1 на 2, а 2 на 1. Обозначим через
$\overline M$ множество всех наборов, противоположных наборам из $M$. Наборы
$\overline d$ и $d$ ни на одном месте не совпадают. Поэтому, если
$\overline d$ входит в $P$, то $d$ не может входить в $Q$. Значит,
$\overline P$ и $Q$ не содержат одинаковых наборов. Поэтому либо в $\overline P$, либо в $Q$ не более половины всех наборов. Но в $P$ и в $\overline P$ одинаковое количество наборов. Значит, либо в $P$, либо в $Q$
не более половины всех наборов, т. е. не более чем $2^{n-1}$ наборов.
б) Для $n=1$ утверждение очевидно.
Рис. 10
Для $n=2$ задачу можно сформулировать так: $k^2$ точек расставлены нa плоскости в узлах квадратной решётки $(k-1)\times(k-1)$ (рис. 10).
Некоторые из этих точек нужно закрасить красным, некоторые — синим цветом
так, чтобы любая из красных и любая из синих точек лежали либо в одном
столбце, либо в одной строке (т. е. ситуация в) невозможна). Одну точку
можно закрашивать в оба цвета (случай г)). Нужно доказать, что всегда точек
какого-то одного цвета не более $k$. Рисунки а) и б) соответствуют следующим
двум случаям.
В подмножестве $P$ есть два таких набора $(a_1,a_2)$ и $(b_1,b_2)$,
что $a_1\ne b_1$ и $a_2\ne b_2$.
Тогда в $Q$ могут входить только 2 набора $(a_1,b_2)$ и $(b_1,a_2)$. Ho $2\le k$, и утверждение верно.
В подмножестве $P$ любые два набора совпадают в одном
месте (для определённости — в первом).
Тогда любой набор из $P$ имеет вид $(a,b)$, где $a$ — фиксировано. Но таких наборов не более $k$.
Подобным, но значительно более длинным рассмотрением случаев можно
доказать утверждение и при $n=3$. Рассмотрим сразу общий случай.
в) Пусть $P$ содержит $p$ наборов, $Q$ содержит $q$ наборов. Докажем
индукцией по $n$ при фиксированном $k$ более сильное утверждение: если
$p\ge k^{n-1}$, то при выполнении условий задачи$p+(k-1)q\le k^n$.
Отсюда будет следовать, что если $p\ge k^{n-1}$, то $q\le k^{n-1}$.
Если $n=1$, то по условию $p\ge1$. Если $p=1$, то $q\le1$. Если
$2\le p\le k$, то $q=0$. В любом случае $p+(k-1)q\le k$.
Пусть для $n=s$ утверждение доказано. Рассмотрим $n=s+1$. Пусть
$p\ge k^s$. Надо доказать, что $p+(k-1)q\le k^{s+1}$. Обозначим через $P_1$
множество всех наборов из $P$, оканчивающихся цифрой 1. Зачеркнув в наборах
из $P_1$, последнюю цифру 1, мы получим можество $P_1'$, наборов длины $s$.
Число наборов в $P_1$ (столько же наборов и в $P_1'$) обозначим через $p_1$.
Точно так же pacсмотрим множества $P_2$, $\ldots$, $_k$ (наборов,
оканчивающихся на 2, $\ldots$, $k$); $P_2'$, $\ldots$, $P_k'$;
$Q_1$, $\ldots$, $Q_k$; $Q_1'$, $\ldots$, $Q_k'$ и числа $p_2$, $\ldots$,
$p_k$; $q_1$, $\ldots$, $q_k$. По условию любые 2 набора из $P_r$ и $Q_t$
совпадают хотя бы в одном месте, но если $r\ne t$, то в последнем разряде
они совпадать не могут, поэтому любые 2 набора из $P_r'$ и $Q_t'$ при $r\ne t$ совпадают хотя бы в одном месте. Так как $p\ge k^s$, то $p_i\ge k^{s-1}$ хотя бы для одного $p_i$ (так как набор $P$ разбит на $k$
наборов). Можно считать, что $$
p_1\ge k^{s-1},~\ldots,~p_m\ge k^{s-1},\quad
p_{m+1}\lt k^{s-1},~\ldots,~p_k\lt k^{s-1}.\tag4
$$
Рассмотрим 2 случая:
1) $m=1$, т. е.
$$
p_1\ge k^{s-1},\quad p_2\lt k^{s-1},~\ldots,~p_k\lt k^{s-1}.\tag5
$$
Из сказанного выше о $P_r'$ и $Q_t'$ и предположения индукции вытекают
следующие неравенства:
$$
\left\{\begin{array}{l}
p_1+(k-1)q_2\le k^s,\\
{\dots}\,{\dots}\,{\dots}\,{\dots}\\
p_1+(k-1)q_k\le k^s.
\end{array}\right.\tag6
$$
Из этих неравенств следует, что $$
q_2\le k^{s-1},~\ldots,~q_k\le k^{s-1},\tag7
$$
так как $p_1\ge k^{s-1}$. Сложив неравенства (6) и разделив полученное
неравенство на $k-1$, получим
$$
p_1+q_2+\ldots+q_k\le k^s.\tag8
$$
Если $q_1\ge k^{s-1}$, то точно так же получим
$$
q_1+p_2+\ldots+p_k\le k^s.\tag9
$$
Складывая (8) и (9), получим $p+q\le 2\cdot k^s$, а так как $p\ge k^s$, то $$
q\le k^s.\tag{10}
$$
Если же $q_1\lt k^s$, то неравенства (9) и (10) тем более выполняются
ввиду неравенств (5) и (7). В обоих случаях, складывая (8) и (9) и прибавляя
(10), умноженное на $k-2$, получим $p+q+(k-2)q\le2\cdot k^s+(k-2)k^s$, или $$
p+(k-1)q\le k^{s+1}.
$$
2) $m\gt1$. Тогда, так же как и в случае 1), получим
$$
\left\{\begin{array}{l}
p_1+q_2+\ldots+q_k\le k^s,\\
p_2+q_1+q_3+\ldots+q_k\le k^s,\\
{\dots}\,{\dots}\,{\dots}\,{\dots}\,{\dots}\,{\dots}\\
p_m+q_1+\ldots+q_{m-1}+q_{m+1}+\ldots+q_k\le k^s
\end{array}\right.\tag{11}
$$
и $$
q_1\le k^{s-1},~q_2\le k^{s-1},~\ldots,~q_k\le k^{s-1}.\tag{12}
$$
Прибавляя к (13) неравенства из (4) для $p_{m+1}$, $\ldots$, $p_k$ и неравенства (12), первые $m$ из которых умножены на $k-m$, а остальные на $k-m-1$, получим
$$
\begin{gather*}
p_1+\ldots+p_k+(k-1)(q_1+\ldots+q_m)\le\\
\le mk^s+(k-m)k^{s-1}+m(k-m)k^{s-1}+(k-m)(k-m-1)k^{s-1}=\\
=mk^s+(k-m)k^s=k^{s+1},
\end{gather*}
$$
т. е.
$$
p+(k-1)q\le k^{s+1},
$$
что и требовалось доказать.
