Разделы 
Дополнительно
Задача по математике - 3729
2019-06-16 
а) В квадрате $7 \times 7$ клеток нужно отметить центры к клеток так, чтобы никакие четыре отмеченные точки не являлись вершинами прямоугольника со сторонами, параллельными сторонам квадрата. При каком наибольшем к это возможно?
б) Решите аналогичную задачу для квадрата $13 \times 13$ клеток.
Решение:
Оценим количество точек, которые можно нужным образом разместить в квадрате $m \times m$.
Пусть $x_i$ - количество точек в строке с номером $i$ и $\sum_{i = 1}^m x_i = k$.
Если в некоторой строке отмечены центры каких-то двух клеток, то ни в какой другой строке такая же пара клеток не может быть отмечена. Всего в $i$-й строке отмечено $x_i(x_i -1)/2$ пар клеток. Так как все отмеченные пары различны, то их суммарное число не больше общего числа возможных пар, т. е.
$\sum_{i = 1}^m \frac {x_i (x_i - 1)}{2} \leq \frac {m(m-1)}{2}$.
Отсюда следует, что
$\sum_{i=1}^m x_i^2 \leq m(m-1) + \sum_{i=1}^m = m(m-1) + k$;
поскольку $\sum_{i=1}^m x_i^2 \geq \frac{(x_1 + x_2 + \cdots + x_m)^2}{m} = \frac{k^2}{m}$ получаем неравенство $\frac{k^2}{m} \leq m(m-1) + k$. Из этого неравенства следует, что
$k \leq \frac {m+m \sqrt {4m - 3}}{2}$. (*)
При $m = 7$ и $m = 13$ получаем, что $k \leq 21$ и $k \leq 52$ соответственно.
Самое загадочное в решении этой задачи примеры, реализующие точную оценку, (Участниками олимпиады они были найдены подбором, с помощью каких-то соображений симметрии.) Укажем способ их построения. В примере а) в качества «номеров» строк (а также столбцов) используем тройки из чисел 0 и 1, отличные от $(0; 0; 0)$. Их как раз 7: $(1; 1; 1), (1; l;0), (1; 0; 1), (0; 1; 1), (1;0;0), (0; 1; 0), (0;0;1)$. Клетку на пересечении строки $(a_1, a_2,a_3)$ и столбца $(x_1, x_2, x_3)$ отмечаем, если $a_1x_1 + a_2x_2 + a_3x_3$ четно. В примере б) в качестве «номеров» строк и столбцов используем тройки из чисел 0, 1 и -1, отличные от $(0; 0; 0)$, причем из двух троек, получающихся одна из другой умножением на -1, используется лишь одна. Их как раз 13: $(1; 1; 1)$, три перестановки $(1; 1; 0)$, три перестановки $(1; 1; -1)$, три перестановки $(1;-1; 0)$ и три перестановки $(1;0;0)$. Клетку на пересечении строки $(a_1, a_2, a_3)$ и столбца $(x_1, x_2, x_3)$ отмечаем, если $a_1x_1 + a_2x_2 + a_3x_3$ делится на 3.
Это - конструкции конечных проективных плоскостей над полем из $p = 2$ и $p = 3$ элементов: столбцам соответствуют точки, строкам - прямые проективной плоскости, а требуемое в условии свойство таблицы сводится к тому, что через каждые две точки проходит одна прямая и каждые две прямые пересекаются в одной точке (прямая $(a_1, a_2, a_3)$ содержит точку $(x_1, x_2, x_3)$, если $a_1x_1 + a_2x_2 + a_3x_3$ равно 0 по модулю $p$).
Можно убедиться, что неравенство (*) превращается в равенство лишь при $m = p^2 + p + 1$, где $p$ - натуральное число; при этом $k=(p+1)(p^2 + p + 1)$. Вопрос о том, существует ли для таких тик соответствующая таблица, очень сложен: он сводится к (нерешенной в общем виде) проблеме существования конечных проективных плоскостей порядка $p$; во всяком случае, при $p$ простом (или равном степени простого числа) ответ на этот вопрос положителен.
Ответ: а) $k = 21$; б) $k = 52$ (рис.),
а) В квадрате $7 \times 7$ клеток нужно отметить центры к клеток так, чтобы никакие четыре отмеченные точки не являлись вершинами прямоугольника со сторонами, параллельными сторонам квадрата. При каком наибольшем к это возможно?
б) Решите аналогичную задачу для квадрата $13 \times 13$ клеток.
Решение:
Оценим количество точек, которые можно нужным образом разместить в квадрате $m \times m$.
Пусть $x_i$ - количество точек в строке с номером $i$ и $\sum_{i = 1}^m x_i = k$.
Если в некоторой строке отмечены центры каких-то двух клеток, то ни в какой другой строке такая же пара клеток не может быть отмечена. Всего в $i$-й строке отмечено $x_i(x_i -1)/2$ пар клеток. Так как все отмеченные пары различны, то их суммарное число не больше общего числа возможных пар, т. е.
$\sum_{i = 1}^m \frac {x_i (x_i - 1)}{2} \leq \frac {m(m-1)}{2}$.
Отсюда следует, что
$\sum_{i=1}^m x_i^2 \leq m(m-1) + \sum_{i=1}^m = m(m-1) + k$;
поскольку $\sum_{i=1}^m x_i^2 \geq \frac{(x_1 + x_2 + \cdots + x_m)^2}{m} = \frac{k^2}{m}$ получаем неравенство $\frac{k^2}{m} \leq m(m-1) + k$. Из этого неравенства следует, что
$k \leq \frac {m+m \sqrt {4m - 3}}{2}$. (*)
При $m = 7$ и $m = 13$ получаем, что $k \leq 21$ и $k \leq 52$ соответственно.
Самое загадочное в решении этой задачи примеры, реализующие точную оценку, (Участниками олимпиады они были найдены подбором, с помощью каких-то соображений симметрии.) Укажем способ их построения. В примере а) в качества «номеров» строк (а также столбцов) используем тройки из чисел 0 и 1, отличные от $(0; 0; 0)$. Их как раз 7: $(1; 1; 1), (1; l;0), (1; 0; 1), (0; 1; 1), (1;0;0), (0; 1; 0), (0;0;1)$. Клетку на пересечении строки $(a_1, a_2,a_3)$ и столбца $(x_1, x_2, x_3)$ отмечаем, если $a_1x_1 + a_2x_2 + a_3x_3$ четно. В примере б) в качестве «номеров» строк и столбцов используем тройки из чисел 0, 1 и -1, отличные от $(0; 0; 0)$, причем из двух троек, получающихся одна из другой умножением на -1, используется лишь одна. Их как раз 13: $(1; 1; 1)$, три перестановки $(1; 1; 0)$, три перестановки $(1; 1; -1)$, три перестановки $(1;-1; 0)$ и три перестановки $(1;0;0)$. Клетку на пересечении строки $(a_1, a_2, a_3)$ и столбца $(x_1, x_2, x_3)$ отмечаем, если $a_1x_1 + a_2x_2 + a_3x_3$ делится на 3.
Это - конструкции конечных проективных плоскостей над полем из $p = 2$ и $p = 3$ элементов: столбцам соответствуют точки, строкам - прямые проективной плоскости, а требуемое в условии свойство таблицы сводится к тому, что через каждые две точки проходит одна прямая и каждые две прямые пересекаются в одной точке (прямая $(a_1, a_2, a_3)$ содержит точку $(x_1, x_2, x_3)$, если $a_1x_1 + a_2x_2 + a_3x_3$ равно 0 по модулю $p$).
Можно убедиться, что неравенство (*) превращается в равенство лишь при $m = p^2 + p + 1$, где $p$ - натуральное число; при этом $k=(p+1)(p^2 + p + 1)$. Вопрос о том, существует ли для таких тик соответствующая таблица, очень сложен: он сводится к (нерешенной в общем виде) проблеме существования конечных проективных плоскостей порядка $p$; во всяком случае, при $p$ простом (или равном степени простого числа) ответ на этот вопрос положителен.
Ответ: а) $k = 21$; б) $k = 52$ (рис.),
