Разделы 
Дополнительно
Задача по математике - 3678
2019-06-15 
Куб с ребром длины $n$ разбит на $n^3$ единичных кубиков. Выберем несколько кубиков и проведем через центр каждого из них три прямые, параллельные ребрам. Какое наименьшее число кубиков можно выбрать так, чтобы проведенные через них прямые перечеркнули все кубики?
а) Укажите ответ для маленьких значений $n$: для $n = 2, 3, 4$.
б) Попробуйте найти ответ при $n = 10$.
в) Решите общую задачу. Если Вам не удастся найти точный ответ, докажите какие-либо неравенства, оценивающие сверху и снизу число отмеченных кубиков.
г) Заметьте, что эту задачу можно сформулировать так.
Рассмотрим всевозможные наборы ($x_1, x_2, x_3$) где каждая из букв $x_1, x_2, x_3$ принимает одно из $n$ значений $1, 2, \cdots, n$. Какое наименьшее число наборов нужно выбрать, чтобы для каждого из остальных наборов среди выбранных нашелся такой, который отличается от него только в одном месте (значением только одной из координат $x_1, x_2, x_3$). Попробуйте найти ответ для более общей задачи, когда рассматриваются наборы не из трех, а из четырех или большего числа букв.
Решение:
Доказательство того, что меньшим числом кубиков обойтись нельзя, можно провести так. Для расстановки кубиков, удовлетворяющих условию: в каждой клетке нижней грани куба запишем число, показывающее, сколько кубиков лежит над этой клеткой. Воспользуемся теперь такой леммой.
Лемма. В таблице $n \times n$ расставлены целые неотрицательные числа, причем для каждой пары строка - столбец, на пересечении которых стоит нуль, сумма $2n - 1$ чисел в их объединении («кресте») не меньше $n$ тогда сумма всех чисел в таблице не меньше $n^2/2$.
Если наименьшая из сумм по строкам и столбцам - пусть это будет сумма чисел в первой строке - равна $m < n$, то в этой строке не меньше $n - m$ нулей, и в каждом из начинающихся с них $n - m$ столбцов сумма чисел не меньше $n - m$, а в каждом из $m$ остальных столбцов сумма чисел не меньше $m$, а потому общая сумма не меньше
$(n - m)^2 + m^2 > \frac{n^2}{2}$.
Пример нужной расстановки 12 кубиков в кубе $5 \times 5 \times 5$ и 60 кубиков в кубе $10 \times 10 \times 10$ указан на рис., где число в клетке означает номер слоя, в который нужно поместить кубик над данной клеткой, Аналогично строятся примеры для других $n$.
Ответ: наименьшее число $A_n$ кубиков, удовлетворяющих условию, равно
$A_n = \begin{cases} n^2/2 & \: если n \: четно \\ (n^2+1)/2 & \: если n \: нечетно \end{cases}$.
В частности, $A_2 = 2, A_3 = 5, A_4 = 8, A_5 = 12, A_{10} = 50$.
Наиболее интересный результат для $k$-мерного случая - оценка снизу числа «кубиков» ($x_1, \cdots, x_k$), если дополнительно известно, что никакие два из них не отличаются лишь в одной координате: их число не превосходит $\frac{n^{k-1}}{k-1}$. Точный ответ для $k \leq 1$ по-видимому, в общем случае неизвестен.
Куб с ребром длины $n$ разбит на $n^3$ единичных кубиков. Выберем несколько кубиков и проведем через центр каждого из них три прямые, параллельные ребрам. Какое наименьшее число кубиков можно выбрать так, чтобы проведенные через них прямые перечеркнули все кубики?
а) Укажите ответ для маленьких значений $n$: для $n = 2, 3, 4$.
б) Попробуйте найти ответ при $n = 10$.
в) Решите общую задачу. Если Вам не удастся найти точный ответ, докажите какие-либо неравенства, оценивающие сверху и снизу число отмеченных кубиков.
г) Заметьте, что эту задачу можно сформулировать так.
Рассмотрим всевозможные наборы ($x_1, x_2, x_3$) где каждая из букв $x_1, x_2, x_3$ принимает одно из $n$ значений $1, 2, \cdots, n$. Какое наименьшее число наборов нужно выбрать, чтобы для каждого из остальных наборов среди выбранных нашелся такой, который отличается от него только в одном месте (значением только одной из координат $x_1, x_2, x_3$). Попробуйте найти ответ для более общей задачи, когда рассматриваются наборы не из трех, а из четырех или большего числа букв.
Решение:
Доказательство того, что меньшим числом кубиков обойтись нельзя, можно провести так. Для расстановки кубиков, удовлетворяющих условию: в каждой клетке нижней грани куба запишем число, показывающее, сколько кубиков лежит над этой клеткой. Воспользуемся теперь такой леммой.
Лемма. В таблице $n \times n$ расставлены целые неотрицательные числа, причем для каждой пары строка - столбец, на пересечении которых стоит нуль, сумма $2n - 1$ чисел в их объединении («кресте») не меньше $n$ тогда сумма всех чисел в таблице не меньше $n^2/2$.
Если наименьшая из сумм по строкам и столбцам - пусть это будет сумма чисел в первой строке - равна $m < n$, то в этой строке не меньше $n - m$ нулей, и в каждом из начинающихся с них $n - m$ столбцов сумма чисел не меньше $n - m$, а в каждом из $m$ остальных столбцов сумма чисел не меньше $m$, а потому общая сумма не меньше
$(n - m)^2 + m^2 > \frac{n^2}{2}$.
Пример нужной расстановки 12 кубиков в кубе $5 \times 5 \times 5$ и 60 кубиков в кубе $10 \times 10 \times 10$ указан на рис., где число в клетке означает номер слоя, в который нужно поместить кубик над данной клеткой, Аналогично строятся примеры для других $n$.
Ответ: наименьшее число $A_n$ кубиков, удовлетворяющих условию, равно
$A_n = \begin{cases} n^2/2 & \: если n \: четно \\ (n^2+1)/2 & \: если n \: нечетно \end{cases}$.
В частности, $A_2 = 2, A_3 = 5, A_4 = 8, A_5 = 12, A_{10} = 50$.
Наиболее интересный результат для $k$-мерного случая - оценка снизу числа «кубиков» ($x_1, \cdots, x_k$), если дополнительно известно, что никакие два из них не отличаются лишь в одной координате: их число не превосходит $\frac{n^{k-1}}{k-1}$. Точный ответ для $k \leq 1$ по-видимому, в общем случае неизвестен.
