RMO 1991 pregunta 4
Hay dos urnas que contienen cada una un número arbitrario de bolas. Ambos no están vacíos para empezar. Se nos permiten dos tipos de operaciones:
$(a)$ retirar un número igual de bolas simultáneamente de las urnas, y
$(b)$duplicar el número de bolas en cualquiera de ellos.
Demuestre que después de realizar estas operaciones un número finito de veces, ambas urnas se pueden vaciar.
Esta pregunta se ha hecho al menos $3$veces [1] [2] [3] , pero ninguno de ellos parece utilizar el enfoque que estoy usando. Ahora no estoy seguro de si mi enfoque es correcto o no, pero quiero verificarlo.
Mi acercamiento:
Dejar $A$ sea el número de bolas en la urna $1$ y $B$ sea el número de bolas en la urna $2$ en cualquier momento dado.
Deja que las urnas contengan $x_1$ y $y_1$bolas respectivamente inicialmente. ($x_1<y_1$ sin pérdida de generaidad por supuesto)
Sustraer $x_1-1$ bolas de ambas urnas dando así $(1,y_1-x_1+1)$ como la nueva configuración.
Siga duplicando el número más bajo hasta $|A-B|$ alcanzar el valor más bajo posible.
Suponga el valor más bajo de $|A-B|$ se alcanza en la configuración $(x_2,y_2)$. Restando uno menos que el número menor de$x_2,y_2$ (suponer $x_2$) da $(1,y_2-x_2+1)$ como la nueva configuración.
Se puede ver claramente que $|y_2-x_2|\leq|y_1-x_1|$. Por lo tanto, continuar este proceso resultará en una reducción continua en el valor de$|A-B|$ hasta que alcance su valor más bajo, es decir $0$.
En esa etapa, tendríamos $A=B$. Tomando así$A$ las bolas de ambas urnas vaciarían ambas urnas.
$\therefore $ Ambas urnas se pueden vaciar en un número finito de operaciones.
Sé que son posibles enfoques más simples para esta pregunta, pero quiero verificar si mi enfoque también es correcto o no. Por favor verifique mi enfoque y proporcione sugerencias. También lo siento porque no pude pensar en un título mejor.
GRACIAS
Respuestas
Supongamos que tenemos $x_1,y_1$ bolas en urnas $A,B$respectivamente. Podemos tomar los siguientes casos:
Caso 1 :$x_1=y_1 \implies$ nosotros quitamos $x_1$bolas de ambas urnas vaciando ambas. ¡Hemos terminado!
Caso 2 : Sin pérdida de generalidad, dejemos$1<x_1<y_1$. Quitamos$x_1-1$ bolas de ambas urnas, dándonos $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ dejar $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, para que ahora tengamos $1,y_2$ bolas respectivamente en urnas $A,B$respectivamente.
Si$y_2=1$, vaya al Caso 1 , de lo
contrario duplique el número de bolas en la urna$A$ repetidamente, hasta que haya $x_2=2^k$ bolas en urna $A$, así que eso $$x_2=2^k\le y_2<2^{k+1}$$ así que ahora tenemos $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Tenga en cuenta que $x_2\le y_2$), Así que si $x_2=y_2$ir al caso 1 $\qquad \qquad \qquad (*)$
de lo contrario, vuelva al principio del Caso 2 y repita los pasos con$x_2,y_2$ en lugar de $x_1,y_1$. (Entonces, a continuación tendremos$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ dónde $y_3=y_2-x_2+1<y_2$ ya que $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 ya debería haber aparecido en $(*)$))
Nuestro proceso definitivamente terminará porque $y_1>y_2>\cdots$es una secuencia estrictamente decreciente de enteros positivos y no podemos tener una secuencia infinita estrictamente decreciente de enteros positivos. Entonces, en algún paso, terminaremos en$x_n=y_n$cuando vaciaremos ambas urnas (este es precisamente el caso mencionado en la última línea del Caso 2 anterior).