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.