OBM 2022 - Nível 2 - P1

Problema 1:

Um jogo para uma pessoa tem as seguintes regras: inicialmente há dez pilhas, com $1$,$2$,$3$,...,$10$ pedras, respectivamente. Uma jogada consiste em fazer uma das duas seguintes operações:

(i) escolher duas pilhas, cada uma com pelo menos duas pedras, juntá-las e depois adicionar mais duas pedras à nova pilha;

(ii) escolher uma pilha com pelo menos quatro pedras, tirar duas pilhas dela e separá-la em duas pilhas de quantidades de pedras positivas escolhidas pelo jogador.

O jogo continua até não ser mais possível fazer uma operação.

(a) Dê um exemplo de uma sequência de jogadas que conduzem ao término do jogo.

(b) Faça uma tabela informando qual é o número total de pedras e o número de pilhas no início e após cada uma das 5 primeiras operações no seu exemplo acima.

(c) Mostre que o número de pilhas com apenas uma pedra ao final do jogo é sempre o mesmo,
independentemente de como se realizam as jogadas.

Solução (por Luca Zanardi):

a) Comece com as pilhas de tamanho $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$. Junte as pilhas de tamanho $2$ e $3$ formando uma pilha de tamanho 7 (operação $(i)$). Prossiga juntando com as próximas pilhas, como a seguir: $7, 4 \rightarrow 13$, $13, 5 \rightarrow 20$, $20, 6 \rightarrow 28$, $28, 7 \rightarrow 37$, $37, 8 \rightarrow 47$, $47, 9 \rightarrow 58$, $58, 10 \rightarrow 70$. A partir daí, faça a operação $(ii)$, separando a pilha em 2 pilhas de tamanhos $1$ e $67$. Aplique tal operação da mesma maneira, indo para pilhas de tamanho $1$ e $64$, $\dots$, $1$ e $4$, e finalmente, $1$ e $1$. Assim, perceba que mais nenhum movimento é possível no jogo, e finalizamos com $25$ pilhas de uma pedra.

b) Para o nosso exemplo, uma operação que é válida é a seguinte:

c) Note que, na operação $(i)$, a quantidade de pilhas diminui em $1$ e a quantidade de pedras aumenta em $2$ (Por exemplo, nos movimentos vistos na tabela acima). Por outro lado, em $(ii)$, pode-se perceber que a quantidade de pedras aumenta em $2$ e a de pilhas aumenta em $1$. Assim, considere a "energia" do jogo como sendo: $E_i = 2\cdot p + r$ ($E_i$ é a energia após o i-ésimo movimento, $p$ a quantidade de pilhas e $r$ a quantidade de pedras (rochas)). Note que a energia no sistema nunca será mudada, pois, a cada operação, $E_{i+1} = 2\cdot (p - 1) + r + 2 = 2\cdot p + r = E_i$, ou $E_{i+1} = 2\cdot (p + 1) + r - 2 = 2\cdot p + r = E_i$. Logo, a energia inicial será a mesma da final.

Porém, note que $E_0$ (a energia inicial) $= 2\cdot 10 + 55 = 75$.

Considere agora $X_i$ a quantidade de pilhas com $i$ pedras no final do jogo.

Perceba que, quando não se é possível fazer uma operação, $(ii)$ não pode ser realizado, então $X_i = 0 \ \forall \ i \geq 4$.
$(i)$ também não pode ser realizado, e então há no máximo uma pilha com $2$ ou $3$ pedras.

Dessa forma, $X_2 + X_3 \leq 1 \implies (X_2, X_3) = (0, 0);$ $(1, 0);$ ou $(0, 1)$.

Daí, como a energia se conserva, a energia final $= E_f = E_0 = 75$. Então...

Caso $1$: $(X_2, X_3) = (0, 0)$:

Teremos que $E_f = 2\cdot (X_1) + X_1 = 75 \implies X_1 = 25$ (esse caso ocorreu em nosso exemplo da letra a) da questão).

Caso $2$: $(X_2, X_3) = (1, 0)$:

Teremos que $E_f = 2\cdot (X_1 + 1) + X_1 + 2 = 75 \implies X_1 = 71/3 \notin \mathbb{Z}$.

Caso $3$: $(X_2, X_3) = (0, 1)$:

Teremos que $E_f = 2\cdot (X_1 + 1) + X_1 + 3 = 75 \implies X_1 = 70/3 \notin \mathbb{Z}$.

Assim, o único caso possível é o caso $1$, donde temos que $X_1 = 25$, independentemente dos movimentos, como queríamos demonstrar.