|
|
 |
Условие
Куб, состоящий из $(2n)^3$ единичных кубиков, проткнут несколькими спицами, параллельными рёбрам куба. Каждая спица протыкает ровно 2n кубиков, каждый кубик проткнут хотя бы одной спицей.а) Докажите, что можно выбрать такие $2n^2$ спиц, идущих в совокупности всего в одном или двух направлениях, что никакие две из этих спиц не протыкают один и тот же кубик.
б) Какое наибольшее количество спиц можно гарантированно выбрать из имеющихся так, чтобы никакие две выбранные спицы не протыкали один и тот же кубик?
Решение
Пусть ребра куба параллельны осям координат.
а) Разобьём куб на слои толщиной 1, параллельные плоскости Oxy. Рассмотрим только спицы направлений Ox и Oy. В каждом слое найдём максимум числа таких спиц, идущих в одном направлении. Точно также найдём максимумы числа спиц для каждого слоя параллельного Oxz и параллельного Oyz. Пусть k – минимум из 6n этих максимумов.
Рассмотрим слой K, где максимум равен k.
В слое можно выбрать 2n-k строк и 2n-k столбцов, через которые не проходят спицы слоя.
На пересечении выбранных рядов есть $(2n-k)^2$ кубиков, их протыкают $(2n-k)^2$ спиц, перпендикулярных K.
Покрасим эти $(2n-k)^2$ спиц в синий цвет.
Выберем грань P куба, перпендикулярную слою K.
Рассмотрим слои, параллельные P и не содержащие синих спиц.
Их ровно k.
В каждом таком слое можно выбрать не менее k спиц одного направления, всего не менее $k^2$ спиц.
Добавим к ним синие спицы.
По известному неравенству
$$k^2+(2n-k)^2\geqslant\frac{1}{2} (k+(2n-k))^2=2n^2.$$
б)
$2n^2$ спиц.
Выделим в нашем кубе два меньших куба со стороной n, примыкающие к противоположным вершинам.
Они состоят из $2n^3$ единичных кубиков.
Проткнём каждый выделенный кубик тремя перпендикулярными спицами.
Тогда и все невыделенные единичные кубики тоже проткнуты.
Заметим, что каждая спица протыкает ровно n выделенных кубиков.
Значит, если спицы выбраны так, что никакой кубик не проткнут дважды, то спиц не более чем $2n^3:n=2n^2$.
