Европейская математическая олимпиада среди девочек (EGMO) 2012. Великобритания

$n$ — натурал сан. $n$-ге тәуелді келесі қасиетке ие болатын ең үлкен бүтін $m$ санын табыңыз: өлшемі $m$ қатар және $n$ баған болатын кестені нақты сандармен толтыруға болады, әрі кез келген екі түрлі $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$ және $\left[b_{1}, b_{2}, \ldots, b_{n}\right]$ қатарлары үшін мына шарт орындалады: $$ \max \left(\left|a_{1}-b_{1}\right|,\left|a_{2}-b_{2}\right|, \ldots,\left|a_{n}-b_{n}\right|\right)=1.$$

Комментарий/решение

Ответ: $m=2^n$.

Оценка: Рассмотрим произвольный столбец $i$. Пусть в нем наименьшее число равно $x$. Заметим, что все остальные числа находятся в диапазоне от $x$ до $x+1$. Понятно что меньше не может быть, а если найдется число больше(пусть это $y$), то рассмотрев соответствующие ряды в которых находятся эти числа, то $max(|a_i-b_i|) \geq |y-x| > 1$. Противоречие. Тогда заменим любое число $y$ которое больше $x$ на $x+1$ и условие не поменяется. Тогда в любом столбце значения равны либо $x$ либо $x+1$. Значит для любого ряда, на каждой клетке есть 2 варианта, то есть всего $2^n$ различных строк. Тогда если $m > 2^n$, найдутся две равные строки, то есть $max(|a_i-b_i|)=0$. Отсюда исходит оценка.

Пример: В строки запишем всевозможные перестановки из $0$ и $1$. Тогда очевидно что все строки различны, и для любых двух строк найдется столбец для которого разница чисел в нем равна $|0-1|=1$.