XIII математическая олимпиада «Шелковый путь», 2014 год

Какое наибольшее число монет можно расставить в клетках таблицы $n \times n$ (в каждой клетке таблицы может находиться не более одной монеты) так, чтобы любая монета не была одновременно ниже и правее чем любая другая? ( Ильясов С. )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. $2n-1$. Пример можно получить, если расставить монеты во все клетки самого левого столбца и самой верхней строки.
Решение. Занумеруем все столбцы (слева направо) и строки (снизу вверх) числами $1, 2, \ldots, n$. Каждая клетка при этом будет иметь свои координаты $(x,y)$ (номер столбца, номер строки).
Далее занумеруем монеты в таблице следующим образом: рассмотрим клетку (где есть монета) с наименьшей координатой $y$, если таких несколько, то также выбираем с наименьшей координатой $x$. Выбранная монета будет первой. Оставшиеся монеты нумеруем аналогичным образом. Пусть в таблице $k$ монет с координатами $(a_1, b_1), \ldots, (a_k, b_k)$. Заметим, что для всех $1 \le i \le k-1$ выполнено $b_{i} \le b_{i+1}.$
Если для некоторого $i$, $b_{i} = b_{i+1},$ то монеты с номерами $i, i+1$ лежат в одной строке. Значит, $a_i < a_{i+1}$ и $a_{i} + b_{i} < a_{i+1} + b_{i+1}$.
Если же $b_{i} < b_{i+1},$ то неравенство $a_{i} > a_{i+1}$ невозможно так как иначе монета $i$ будет одновременно правее и ниже чем монета $i+1$. То есть $a_i \le a_{i+1}$ и $a_{i} + b_{i} < a_{i+1} + b_{i+1}$.
Нетрудно видеть, что $2 \le a_{i} + b_{i} \le 2n$. Так как $a_{i} + b_{i}$ строго возрастает, то в ней не более чем $2n-1$ членов.