OBM 2018 - Nível 2 - P1

Problema 1

Um cubo $n\times n\times n$ e formado por $n^3$ cubinhos unitarios e tem, inicialmente, um cubinho vermelho em somente um de seus vertices. Numeramos esse cubinho com o número 1. A cada dia a partir do dia 2, os cubinhos vizinhos (cubinhos com faces comuns) a cubinhos vermelhos tambem ficam vermelhos e são numerados com o número do dia.

Por exemplo, o cubo $2\times 2\times 2$ acima, no primeiro dia, tem um cubinho vermelho com o numero 1, no segundo dia tem quatro cubinhos vermelhos, um com o numero 1 e três com o número 2, no terceiro dia tem sete, um cubinho com o numero 1, três com o número 2 e três com o número 3, e somente no quarto dia terá todos os seus cubinhos na cor vermelha. Para representar a numeração final podemos usar $n$ tabuleiros representando cada uma $n$ das camadas do cubo vistas de frente. Por exemplo, para o cubo $2\times 2\times 2$ acima temos as seguintes camadas:

a) Na figura a seguir temos as quatro camadas do cubo $4\times 4\times 4$ e os cubos numerados com 1 e 2. Copie esses 4 tabuleiros no caderno de respostas e preencha os numeros de cada cubinho

b) Em um cubo $10\times 10\times 10$, quantos cubinhos são numerados com 7? E quantos são numerados com 13?

c) Em um cubo $2018\times 2018\times 2018$ , qual o número que aparece mais vezes na numeração dos cubinhos? (Se houver mais de um número que aparece o maior número de vezes liste todos.)

Solução de João Linhares:

a)

b) Vamos definir $P_{(n,k)}$ como a quantidade de cubinhos numerados com $k$ num cubo $n\times n\times n$

Definimos também $D_{(n,k,i)}$ como o conjunto de cubinhos numerados com $k$ na $i$-ésima camada de um cubo $n\times n\times n$.
Tome coordenadas para o cubo $n\times n\times n$ sendo o cubinho numerado com 1 o cubinho (0,0,0) e com as coordenadas crescendo conforme o lado do cubo
Assim temos que $P_{(n,k)}=\sum_{i=0}^{n-1}|D_{(n,k,i)}|$

Lema 1: Se um cubinho tem coordenadas $(x,y,z)$, com $x,y,z\leq n-1$, ele será numerado com $x+y+z+1$

Prova: Primeiramente note que se um cubinho tem coordenadas $(i,j,k)$ e é numerado com $n$ isso implica que os cubinhos $(i+1,j,k)$, $(i,j+1,k)$ e $(i,j,k+1)$ serão numerados com $n+1$. Assim, se a condição vale para esse cubo $n$ então, $i+j+k=n-1\iff (i+1)+j+k=n$, $i+(j+1)+k=n$ e $i+j+(k+1)=n$. Logo, como o lema vale para $n=1$, então por indução, o lema é verdadeiro.

Assim temos que $D_{(n,k,i+1)}=D_{(n,k-1,i)}$
E que $D_{(n,k,i)}$ forma uma diagonal ao longo da camada $i$

Porém $D_{(n,k-1,i)}$ é uma diagonal acima de $D_{(n,k,i)}$, logo $|D_{(n,k,i+1)}|=|D_{(n,k,i)}|+1$ caso $D_{(n,k,i)}$ for uma diagonal abaixo da maior possível (tamanho $n$), ou $|D_{(n,k,i+1)}|=|D_{(n,k,i)}|-1$ caso $D_{(n,k,i)}$ for a diagonal maior ou uma diagonal acima da maior e $|D_{(n,k,i)}|\geq 1$.

Assim $P_{(10,7)}= 7+6+5+4+3+2+1+0+0+0=28$

E $P_{(10,13)}= 7+8+9+10+9+8+7+6+5+4=73$

c)

 

Vimos que os números iguais que aparececem em uma tabela formam sempre uma diagonal. Perceba que possuímos um total de $3\times 2017 +1=3\times2018 -2$ números pois esse é o tempo levado para cobrir o quadradinho oposto ao inicial (lembre que este quadradinho é (2017,2017,2017)). Temos um total de $2\times 2018-1$ diagonais. Seja n um inteiro qualquer de $1$ a $3\times2018 -2$. Perceba $n$ vai aparecer (considerando todas as tabelas) em no máximo 2018 diagonais consecutivas do tabuleiro das $2\times 2018 -1$ diagonais possíveis. Assim, os $n$ que aparecerão mais vez são os que estão no conjunto de $2018$ diagonais consecutivas com maior número de quadradinhos nelas. Isto é obtido tomando-se a diagonal principal, $1009$ para um lado e $1008$ para o outro. Assim, temos 2 possíveis máximos alternando qual lado tem $1009$ diagonais.

Calculemos o primeio valor em que existem $1008$ diagonais antes da principal na tabela com o número n (consideramos as diagonais da esquerda para direita);

Nesse caso, a 1009° tabela tem sua diagonal principal preenchida com esse número. Como o número da principal da primeira tabela é 2018 e ele aumenta de um em um, temos que este valor será $2018 + 1008 = 3026$

O outro $n$ é este +1 pois ele será ta que a 1010° tabela tem sua diagonal principal preenchida com esse número. Respostas: $3026, 3027$.

Abaixo, está uma explicação mais formal para o porquê do máximo ocorrer nestes casos:

 

Como $P_{(2018,k)}=\sum_{i=0}^{2017}|D_{(2018,k,i)}|$, para maximizar isso, temos que $|D_{(2018,k,i)}| \neq 0$ e como a sequência de $D_{(2018,k,i)}$ é definida por $D_{(2018,k,1)}$, basta encontrar $D_{(2018,k,1)}$ para maximizar $P_{(2018,k)}$

Note que a maior coordenada possível para um cubinho na primeira camada é $(n-1,n-1,0)$ logo para $k>2n-1$ temos que $|D_{(2018,k,1)}|=0$

Note que para $k<n$, $|D_{(2018,k,2017)}|=0$ pois o máximo valor de $|D_{(2018,k,1)}|$ é $n-1$ e $D_{(2018,k,1)}$ está acima da maior diagonal $D_{(2018,k,i)}$ sempre diminui.

Assim, o $k$ que procuramos pertence ao intervalo $n\leq k\leq 2n-1$
Vamos chamar $|D_{(2018,k,1)}|$ de $S$, assim temos que $P_{(2018,k)}=S+(S+1)+...+(n-1)+n+(n-1)+...+(S'+1)+S'$
Vamos calcular $S'$, como existem exatamente $n$ termos na soma de $P_{(2018,k)}$ e de $S$ a $n$ existem $n-S+1$ termos, sabemos que faltam $S-1$ termos, logo $(n-1)-S'+1=S-1\iff S'=n-S+1$

Porém,

$P_{(2018,k)}=S+(S+1)+...+(n-1)+n+(n-1)+...+(n-S+2)+(n-S+1)$

$P_{(2018,k+1)}=(S-1)+S+(S+1)+...+(n-1)+n+(n-1)+...+(n-S+2)$

Portanto,

$P_{(2018,k)}+S-1-(n-S+1)=P_{(2018,k+1)}\iff P_{(2018,k)}+2(S-1)-n=P_{(2018,k+1)}$

Porém, fazendo $2(S-1)-n=0\iff S=\frac{n+2}{2}$ temos que $P_{(2018,k+1)}=P_{(2018,k)}$ e são os máximos, porque depois disso $2(S-1)-n$ fica negativo pois $S$ vai diminuindo.

Mas note que a diferença de $k$ e $n$, é a diferença de $n$ e $S$, pois para cada valor que $k$ excede $n$, $S$ diminui 1 sendo o inicial $S=n$, logo $k-n=n-S\iff S=2n-k$

Portanto para $n=2018$:

$2n-k=\frac{n+2}{2}\iff k=\frac{3n-2}{2}=\frac{3\cdot2018-2}{2}=3026$

Logo para $k=3026$ ou $3027$, $P_{(2018,k)}$ é máximo.