22-я Международная Жаутыковская олимпиада по математике, 2026 год

Натурал $m>k>1$ сандары берілген. $N\times N$ өлшемді тақтада әр қатарда және әр бағанда дәл бір фишкадан болатындай етіп $N$ фишка орналастырылған. Белгілі болғандай, тақтаны бір вертикаль және бір горизонталь түзу арқылы (ұяшықтардың қабырғалары бойымен) төрт тіктөртбұрышқа қалай бөлмесек те, төртуінің бірінде кемінде $m$ фишка, ал екіншісінде кемінде $k$ фишка болатындай ортақ қабырғасы болмайтын екі тіктөртбұрыш табылмайды. Мұндай жағдай қандай ең үлкен $N$ үшін мүмкін? ( И. Богданов, Г. Челноков )

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

Докажем что $N \geq 2m+2k-3$ не подходит.

Добавив несколько столбцов и строк достаточно рассмотреть случай $N=2m+2k-3$. Отделим левую $(2k-1) \times N$ подтаблицу. Понятно что в нем можно выбрать либо верхние либо нижние $m+k-1$ строк что в нем хотя бы $k$ фишек. Б.О.О. пусть верхние $m+k-1$ строки содержать хотя бы $k$ фишек. Тогда нижние $(m+k-2) \times (2k-1)$ содержать не более $k-1$ фишек. Значит правый нижний $(2m-2) \times (m+k-2)$ подтаблица содержит хотя бы $m-1$ фишек. Пусть тогда в нем ровно $m-1$ фишек. Тогда в "верхней подтаблице" от нашей отделенной полтаблицы ровно $k$ фишек. Допустим в "среднем" строке нашей отделенной подтаблицы нету фишки. Тогда в остальной части этой строки есть ровно одна фишка. Значит если взять правый нижний $(m+k-1) \times (2m-2)$ подтаблицу то в нем ровно $m$ фишек. Тогда мы нашли такой разрез. Значит в левой $2k-1$ клетках "средней" строки нашей таблицы есть ровно одна фишка. Аналогичным образом в правом $2k-1$ клетках этой же строки есть другая фишка. Но тогда в этой строке есть 2 фишки. Противоречие.

а почему что нижняя таблица (m+k-2)x(2k-1) не содержить не более k-1 фишек