Конструктивы в комбигео

Подсказка 1:

В подобных задачах всегда стоит поизучать примеры раскрасок, то есть не сразу делать оценку, а попробовать понять, как может выглядеть пример, заметить закономерности и так далее. Также частенько бывает очень полезно рассмотреть маленькие случаи, времени это много не займёт, а понимания может привнести достаточно. Итак, с чего начнём?

Подсказка 2:

Раз куб со стороной 2N + 1, то логичнее всего начать рассматривать случай куба 3×3×3. Исследуйте возможные примеры, удовлетворяющие условию.

Подсказка 3:

Уверены, пример на 18 вы построили, подумайте ещё и осознайте, что пример на 20 тоже строится несильно сложно. Теперь стоит подумать насчёт оценки...

Подсказка 4:

Она здесь тривиальная, рассмотрим два диагонально противоположных куба 3×3×3 и вот уже оценка на ≤ 20 готова (осознайте это). Итого, мы поняли, что для этого куба ответ 20. В такие моменты бывает очень полезно изучить число 20, а тем более то, как оно зависит от N (в нашем случае N = 1).

Подсказка 5:

20 = 2 * 2 * 5 = (N + 1)²(4N + 1) = 4N²(4N + 1) = 20N = 4N²(N+4) = ... (в случае N = 1). Также понятно, что ответ около трети от (2N+1)³. Очевидно, что в общем виде это многочлен с коэффициентом 4 при N³. Также естественное желание свести константы к минимуму (ну или оставить ± единички). На что это намекает?

Подсказка 6:

На то, что ответ, скорее всего, равен (N+1)²(4N + 1). Попробуем доказать эту гипотезу. С чего мы начнём?

Подсказка 7:

Разумеется, с примера, ведь подогнать пример под ответ проще, чем оценку (банально в силу наглядности). Итак, вперёд пробовать!

Подсказка 8:

Если вы достаточно попробовали, то, скорее всего, поняли, что совсем наглядно пример не строится (никакие красивые узоры не подходят), значит, нужно прибегать к аналитическому подходу...

Подсказка 9:

А от подобных мыслей недалеко до декартовой системы координат. Введём же её так, что все вершины единичных кубиков будут иметь целые координаты от 0 до 2N + 1. Рассмотрим произвольный куб 2×2×2. Хотим как-то в зависимости от координат вершин его кубиков определять его цвет.

Подсказка 10:

Но наборов координат всего 27, а кубиков 8, не хотелось бы рассматривать все эти наборы координат, в идеале для каждого кубика оставить свою координату, а ещё круче, если они будут выбраны "одинаково".

Подсказка 11:

Попробуем выбрать "наконечник" куба 2×2×2, то есть в каждом маленьком кубике рассмотрим вершину, которая ближе всего к началу координат. Этот наконечник образует куб из 8 вершин. Как координаты этих вершин записываются в общем виде?

Подсказка 12:

(a, b, c); (a + 1, b, c); (a, b + 1, c); (a, b, c + 1); (a + 1, b + 1, c); (a + 1, b, c + 1); (a, b + 1, c + 1); (a + 1, b + 1, c + 1). С какой точки зрения мы можем посмотреть на эти числа, учитывая, что a, b, c — произвольные?

Подсказка 13:

С точки зрения чётности! И нам нужно покрасить ровно 4 кубика в чёрный цвет. Как же это сделать?

Подсказка 14:

Давайте сделаем так, чтобы кубики, у которых в выбранном наборе координат хотя бы 2 чётные, будут чёрными, а остальные — белыми. Осознайте, что это искомый пример. Путём несложных вычислений докажите, что всего чёрных кубиков при такой раскраске ровно (N+1)²(4N+1). Осталось подогнать оценку под пример, однако наш пример уже достаточно сложный и идейный, может попробовать как-то использовать его в оценке?

Подсказка 15:

Давайте вместо отдельной оценки попробуем доказать оптимальность нашего примера (осознайте, что эти идеи разные). Пусть в общем виде кубик тёмный, если в нашем примере он чёрный, и светлый — если в примере он белый (то есть кубик вполне может быть тёмным и светлым одновременно). Раз пример аналитический, то оценка, скорее всего, такая же. В примере мы используем идеи чётности и расстояний, и они отлично работают, может стоит вновь прибегнуть к ним? Давайте для каждой целочисленной точки в нашей ДСК (a, b, c) введём определение t-ранга. t-ранг — минимальное расстояние до грани куба, перпендикулярной соответствующей оси (разумеется, t ∈ {x, y, z}). Значения рангов — r_x, r_y, r_z. А просто рангом точки (a, b, c) — r будем называть min(r_x, r_y, r_z). Вспомним про наши идеи, что можно сделать дальше?

Подсказка 16:

Отметим все целочисленные точки с нечётным рангом. Для каждой такой точки посчитаем разницу количества чёрных кубиков и количества белых кубиков, смежных с этой точкой. Что можно сказать про эту разницу?

Подсказка 17:

Вспомним условие и поймём, что она неположительна. Значит, сумма ∑ этих разностей по всем отмеченным точками также неположительна. Понятно, что какой-то конкретный маленький кубик мы учли несколько раз в ∑. Что тогда полезно было бы сделать?

Подсказка 18:

Ввести обозначение для количества отмеченных вершин конкретного кубика. Назовём эту величину кратностью. Воспользуемся техникой двойного подсчёта. Как же теперь с помощью новых обозначений можно посчитать ∑?

Подсказка 19:

Разумеется, ∑ = сумма всех кратностей чёрных кубиков — сумма кратностей белых кубиков. Итого, опираясь на некоторую "интуицию", мы ввели много обозначений и что-то поняли про ∑. Кажется, пришло время вновь немного поисследовать, посмотреть случаи. Рассмотрим произвольный кубик 2×2×2, пусть ранги его центра — r_x, r_y, r_z. Для однозначности будем считать, что r_x ≤ r_y ≤ r_z. Разберём несколько случаев.

Подсказка 20:

1) r_x < ry;
2) r_x = r_y = 1/2 + d, где d — чётно;
3) r_x = r_y = 1/2 + d, где d — нечётно.
Аккуратно разберите каждый случай и осознайте, что кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4 (именно тёмных и светлых, а не чёрных и белых). Отличное продвижение. Давайте теперь для удобства введём обозначения кратностей: s₁ ≤ s₂ ≤ ... ≤ s_{(2N+1)³} С учётом продвижения и построенного примера, что можно сказать про эти кратности?

Подсказка 21:

Что s₁ + ... + s_{(N+1)²(4N+1)} = s_{(N+1)²(4N+1)+1} + ... + s_{(2N+1)³}, так как в примере ∑ = 0. Фух, осталось совсем немного. Осталось красиво завершить оценку противоречием. Пусть в раскраске чёрных кубиков > (N+1)²(4N+1). Что тогда?

Подсказка 22:

0 ≥ ∑ > s₁ + ... + s_{(N+1)²(4N+1)} − s_{(N+1)²(4N+1)+1} − ... − s_{(2N+1)³} = 0. В этой цепочке неравенств есть одно упущение (осознайте какое и допишите его, не забудьте обосновать). В итоге мы получили, что 0 > 0, если кубиков > (N+1)²(4N+1). Кажется, это победа)