RMO 1991 question 4

Question

Il y a deux urnes contenant chacune un nombre arbitraire de boules. Les deux ne sont pas vides pour commencer. Nous avons droit à deux types d'opérations:
$(a)$ retirer simultanément un nombre égal de balles des urnes, et
$(b)$doubler le nombre de balles dans n'importe lequel d'entre eux.
Montrez qu'après avoir effectué ces opérations un certain nombre de fois, les deux urnes peuvent être vides.

Cette question a été posée au moins $3$fois [1] [2] [3] , mais aucun d'entre eux ne semble utiliser l'approche que j'utilise. Maintenant, je ne sais pas si mon approche est correcte ou non, mais je veux la vérifier.

Mon approche:

Laisser $A$ être le nombre de boules dans l'urne $1$ et $B$ être le nombre de boules dans l'urne $2$ n'importe quand.

Que les urnes contiennent $x_1$ et $y_1$balles respectivement initialement. ($x_1<y_1$ sans perte de généraité bien sûr)

Soustraire $x_1-1$ boules des deux urnes donnant ainsi $(1,y_1-x_1+1)$ comme nouvelle configuration.

Continuez à doubler le nombre inférieur jusqu'à $|A-B|$ atteindre la valeur la plus basse possible.

Suppoe la valeur la plus basse de $|A-B|$ est atteint lors de la configuration $(x_2,y_2)$. Soustraire un de moins que le nombre inférieur de$x_2,y_2$ (supposer $x_2$) donne $(1,y_2-x_2+1)$ comme nouvelle configuration.

On voit clairement que $|y_2-x_2|\leq|y_1-x_1|$. Ainsi, la poursuite de ce processus entraînera une réduction continue de la valeur de$|A-B|$ jusqu'à ce qu'il atteigne sa valeur la plus basse, c'est-à-dire $0$.

À ce stade, nous aurions $A=B$. Prenant ainsi$A$ des boules des deux urnes videraient les deux urnes.

$\therefore $ Les deux urnes peuvent être vidées en un nombre fini d'opérations.

Je sais que des approches plus simples sont possibles pour cette question, mais je veux vérifier si mon approche est également correcte ou non. Veuillez vérifier mon approche et fournir des suggestions. Aussi désolé pour je ne pouvais pas penser à un meilleur titre.

MERCI

Answer 1

Supposons que nous ayons $x_1,y_1$ balles dans les urnes $A,B$respectivement. Nous pouvons prendre les cas suivants:

Cas 1 :$x_1=y_1 \implies$ nous supprimons $x_1$boules des deux urnes les vidant tous les deux. Nous avons fini!

Cas 2 : Sans perte de généralité, soit$1<x_1<y_1$. Nous supprimons$x_1-1$ balles des deux urnes, nous donnant $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ laisser $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, de sorte que maintenant nous avons $1,y_2$ boules respectivement dans des urnes $A,B$respectivement.
Si$y_2=1$, allez au cas 1 ,
sinon doublez le nombre de balles dans l'urne$A$ à plusieurs reprises, jusqu'à ce qu'il y ait $x_2=2^k$ boules dans l'urne $A$, pour que $$x_2=2^k\le y_2<2^{k+1}$$ alors maintenant nous avons $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Notez que $x_2\le y_2$), donc si $x_2=y_2$aller au cas 1 $\qquad \qquad \qquad (*)$
sinon, revenez au début du cas 2 et répétez les étapes avec$x_2,y_2$ au lieu de $x_1,y_1$. (Donc, ensuite nous aurons$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ où $y_3=y_2-x_2+1<y_2$ depuis $x_2>1$,
(parce que$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ qui aurait déjà dû apparaître dans $(*)$))

Notre processus prendra définitivement fin car $y_1>y_2>\cdots$est une suite strictement décroissante d'entiers positifs et nous ne pouvons pas avoir une suite infinie strictement décroissante d'entiers positifs. Donc à un moment donné, nous finirons par$x_n=y_n$quand on videra les deux urnes (c'est précisément le cas évoqué dans la dernière ligne du cas 2 ci-dessus).