OBM 2022 - Nível 3 - 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.

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 Matheus Alencar):

Seja $x_i$ o número de pedras em todas as pilhas juntas após $i$ jogadas e $y_i$ o número de pilhas após $i$ jogadas. Afirmo que $2y_k+x_k$ é invariante de acordo com as jogadas feitas.

Prova: Veja que $y_k$ na jogada (i) diminui em $1$ e $x_k$ aumenta em $2$, já na jogada (ii), $y_k$ aumenta em $1$ e $x_k$ diminui em $2$. Assim,

$2y_{k+1}+x_{k+1}=2(y_k+1)+(x_k-2)$ ou $2(y_k-1)+(x_k+2)$. Em ambos os casos temos

$2y_k+x_k=2y_{k+1}+x_{k+1}$

Além disso, veja que numa possível posição final temos no máximo uma pilha com mais de uma pedra (se não seria possível fazer a jogada (i)) e nenhuma pilha com $\ge 4$ pedras (se não seria possível fazer a jogada (ii)). Logo, se após $n$ jogadas chegamos numa posição final:

$\implies 2y_n+x_n =2y_0+x_0$

veja que $x_n=y_n+r$, onde $r\in\{0,1,2\}$ é o o número de pedras a mais da única pilha com mais de uma pedra.

$\implies 3y_n+r=2y_0+x_0$

Pelo Algoritmo da divisão, só existe um jeito de dividir $2y_0+x_0$ dessa forma. Assim, independente de que jogadas fazemos, a posição final é fixa. logo, $y_n=$ número de pilhas é fixo

Nota: Se quisessemos achar o número de pilhas no final também seria possível por esse argumento, basta calcular $2y_0+x_0$!

 

Solução alternativa (por Luca Zanardi):

Note que, na operação $(i)$, a quantidade de pilhas diminui em $1$ e a quantidade de pedras aumenta em $2$. Por outro lado, em $(ii)$, 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$.

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.