Pergunta 4 do RMO 1991

Question

Existem duas urnas, cada uma contendo um número arbitrário de bolas. Ambos não estão vazios para começar. Temos dois tipos de operação permitidos:
$(a)$ remova um número igual de bolas simultaneamente das urnas, e
$(b)$dobre o número de bolas em qualquer um deles.
Mostre que, depois de realizar essas operações finitamente muitas vezes, ambas as urnas podem ser esvaziadas.

Esta pergunta foi feita pelo menos $3$times [1] [2] [3] , mas nenhum deles parece usar a abordagem que estou usando. Agora não tenho certeza se minha abordagem é correta ou não, mas quero verificar isso.

Minha abordagem:

Deixei $A$ seja o número de bolas na urna $1$ e $B$ seja o número de bolas na urna $2$ a qualquer momento.

Deixe as urnas conter $x_1$ e $y_1$bolas respectivamente inicialmente. ($x_1<y_1$ sem perda de generalidade, é claro)

Subtrair $x_1-1$ bolas de ambas as urnas, dando assim $(1,y_1-x_1+1)$ como a nova configuração.

Continue dobrando o número menor até $|A-B|$ alcance o menor valor possível.

Suponha que o menor valor de $|A-B|$ é alcançado na configuração $(x_2,y_2)$. Subtraindo um a menos do que o menor número de$x_2,y_2$ (suponha $x_2$) dá $(1,y_2-x_2+1)$ como a nova configuração.

Pode ser visto claramente que $|y_2-x_2|\leq|y_1-x_1|$. Assim, continuar este processo resultará em redução contínua no valor de$|A-B|$ até atingir seu valor mais baixo, ou seja $0$.

Nessa fase, teríamos $A=B$. Tomando assim$A$ bolas de ambas as urnas esvaziariam ambas as urnas.

$\therefore $ Ambas as urnas podem ser esvaziadas em um número finito de operações.

Sei que abordagens mais simples são possíveis para essa questão, mas quero verificar se minha abordagem também está correta ou não. Por favor, verifique minha abordagem e forneça sugestões. Também lamento por não ter conseguido pensar em um título melhor.

OBRIGADO

Answer 1

Suponha que temos $x_1,y_1$ bolas em urnas $A,B$respectivamente. Podemos atender os seguintes casos:

Caso 1 :$x_1=y_1 \implies$ nós removemos $x_1$bolas de ambas as urnas esvaziando os dois. Acabamos!

Caso 2 : Sem perda de generalidade, deixe$1<x_1<y_1$. Nós removemos$x_1-1$ bolas de ambas as urnas, dando-nos $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ deixei $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, de modo que agora temos $1,y_2$ bolas respectivamente em urnas $A,B$respectivamente.
E se$y_2=1$, vá para o Caso 1 , caso
contrário , dobre o número de bolas na urna$A$ repetidamente, até que haja $x_2=2^k$ bolas na urna $A$, de modo a $$x_2=2^k\le y_2<2^{k+1}$$ então agora nós temos $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Observe que $x_2\le y_2$), então se $x_2=y_2$vá para o Caso 1 $\qquad \qquad \qquad (*)$
caso contrário, volte ao início do Caso 2 e repita as etapas com$x_2,y_2$ no lugar de $x_1,y_1$. (Então, a seguir teremos$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ Onde $y_3=y_2-x_2+1<y_2$ Desde a $x_2>1$,
(porque$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ que já deveria ter aparecido em $(*)$))

Nosso processo vai acabar definitivamente porque $y_1>y_2>\cdots$é uma sequência estritamente decrescente de inteiros positivos e não podemos ter uma sequência infinita estritamente decrescente de inteiros positivos. Então, em alguma etapa, vamos acabar em$x_n=y_n$quando esvaziaremos ambas as urnas (este é precisamente o caso mencionado na última linha do Caso 2 acima).