Всесиб 2024, отборочный этап, 11 класс, задача 1
( баллов) Четыре клетки на клетчатой бумаге называются квартетом, если их центры образуют прямоугольник, стороны которого параллельны линиям сетки. Какое максимальное количество квартетов можно разместить в квадрате на ? Никакие два разных квартета не могут содержать общих клеток.
Ответ
Ответ. квартетов.
Решение. Каждая строка квадрата на пересекается с любым квартетом либо по паре клеток, либо по нулю клеток, то есть по чётному числу клеток. Следовательно, каждая строка содержит чётное число клеток, лежащих в квартетах. Всего в строке клеток, поэтому хотя бы одна клетка каждой строки квадрата остаётся свободной. В квадрате строк, значит, квадрат содержит не менее свободных клеток, и не более клеток, занятых квартетами. Следовательно, в квадрате на нельзя разместить более непересекающихся квартетов.
Пример размещения квартетов выглядит так: обозначим вертикали квадрата на как в шахматах, буквами , а горизонтали — цифрами от до . Первый квартет содержит угловых клетки квадрата , второй — , третий — , четвёртый — , пятый — . Свободными остаются клетки , лежащие в разных строках и разных столбцах доски.
Замечание. Есть много различных примеров размещения квартетов на доске на . Можно доказать, что для любой выборки пяти клеток, находящихся в разных строках и разных столбцах, существует размещение пяти непересекающихся квартетов, занимающих все остальные клетки доски.