Задание №177050: Турнир городов

6. Куб, состоящий из (2n)3 единичных кубиков, проткнут несколькими спицами,
параллельными рёбрам куба. Каждая спица протыкает ровно 2n кубиков, каждый кубик проткнут
хотя бы одной спицей.
а) [6] Докажите, что можно выбрать такие 2n2 спиц, идущих в совокупности всего в одном или
двух направлениях, что никакие две из этих спиц не протыкают один и тот же кубик.
б) [6] Какое наибольшее количество спиц можно гарантированно выбрать из имеющихся так,
чтобы никакие две выбранные спицы не протыкали один и тот же кубик?
(Никита Гладков, Александр Зимин)
Решение. (А. Шаповалов) Пусть ребра куба параллельны осям координат.
а) Разобьём куб на слои толщиной 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 спиц одного направления, всего не
менее k2 спиц. Добавим к ним синие спицы. По известному неравенству
k2 + (2n – k)2  ½ (k + (2n – k))2 = 2n2.
б) Ответ. 2n2 спиц. Выделим в нашем кубе два меньших куба со стороной n, примыкающие к
противоположным вершинам. Они состоят из 2n3 единичных кубиков. Проткнём каждый
выделенный кубик тремя перпендикулярными спицами. Тогда и все невыделенные единичные
кубики тоже проткнуты. Заметим, что каждая спица протыкает ровно n выделенных кубиков. Значит,
если спицы выбраны так, что никакой кубик не проткнут дважды, то спиц не более чем 2n3: n = 2n2.