Европейская математическая олимпиада среди девочек (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$.