Большой Куб и маленькие кубики

[Xenia1996]

Простая задача, придуманная в бессонные часы.

Большой Куб со стороной 2011 разбит на $2011^3$ единичных кубиков, n из которых - зелёненькие, а остальные - розовенькие. При каком наименьшем n гарантированно найдётся ряд из 2011 зелёненьких кубиков, параллельный одной из сторон Большого Куба?
Обобщение данной задачи на Большой Куб с произвольной натуральночисленной стороной, а также на камерный Куб (k - натуральное число) приветствуется.

[MrDindows]

$2011^3-2011^2+1$
Ну или для произвольного куба:
$n^3-n^2+1$

Будем рассматривать эту задачу с обратной стороны: при каком наименьшем количестве розовых кубиков будет существовать куб без единого зелёного ряда.
Так как каждый розовый кубик принадлежит трём рядам, тоесть гарантирует что эти три ряда не будут искомыми, а всего у нас рядов $2011\cdot2011\cdot3$, то минимальное необходимое количество розовых кубов - $2011^2$ Ну и остаётся привести пример для этого числа.
Будем заполнять куб по слоям:
В первом слое положим в главной диагонали 2011 розовых кубов.
Во втором заполним розовыми диагональ возле главной и противоположный от неё угол ( всего $2011$ кубов)
В третем следующуй диагональ от центра и следующую диагональ с противоположного угла.
И тд.
Таким образом получим куб в котором всего $2011^2$ розовых кубиков и в каждом ряду есть ровно по 1 такому кубику.

В общем случае аналогично.

[Руст]

Вначале смотрите на квадрат $n*n$. Легко получается, что если главная диагональ не зеленая, то в любой последовательности $n$ параллельной одной стороне появится не зеленый. Поэтому количество зеленых должно быть не меньше $n^2-n+1$.

Аналогично в $k-мерном случае. Параллельная последовательность из вашего определения это
множество $\{(a_1,...,a_k)\}$, где все $a_i$ постоянны, а одно из них пробегает все $n$ значений.
Поэтому, если клетки с координатами $(x,x,y),(x,y,x)$ розовые, то не существует зеленой стороны.
Т.е. количество зеленых должно быть не меньше $n^3-2n^2+n+1$.
В $k$ мерном кубе $n^k-C_{k-1}^1n^{k-1}+C_{k-2}^2n^{k-2}-...+(-1)^{k-1}n+1=n(n-1)^{k-1}+1$.

[svv]

Cогласен с решением MrDindows.

Руст писал(а):

Поэтому, если клетки с координатами $(x,x,y),(x,y,x)$ розовые, то не существует зеленой стороны.
Т.е. количество зеленых должно быть не меньше $n^3-2n^2+n+1$.

Ваш способ, конечно, не оставляет шанса зелёным кубикам занять ряд, но возможно обойтись и меньшим количеством розовых кубиков, а именно $n^2$.

Ставим розовые кубики на те и только те клетки, у которых $x+y+z$ делится на $n$. Тогда, очевидно, для любых фиксированных значений двух координат существует единственное значение третьей координаты в диапазоне $[1, n]$, удовлетворяющее условию. Т.е. все ряды перекрываются $n^2$ розовыми кубиками.

[Руст]

Да все верно. Вместо $n(n-1)^{k-1}$ надо поставить $n^{k-1}(n-1)$.