RMO 1991 domanda 4
Ci sono due urne ciascuna contenente un numero arbitrario di palline. Entrambi sono non vuoti per cominciare. Ci sono consentiti due tipi di operazioni:
$(a)$ rimuovere un numero uguale di palline contemporaneamente dalle urne, e
$(b)$raddoppia il numero di palline in ognuna di esse.
Dimostrare che dopo aver eseguito finitamente molte volte queste operazioni, entrambe le urne possono essere svuotate.
Questa domanda è stata posta almeno $3$volte [1] [2] [3] , ma nessuno di loro sembra utilizzare l'approccio che sto usando. Ora non sono sicuro che il mio approccio sia corretto o meno, ma voglio verificarlo.
Il mio approccio:
Permettere $A$ essere il numero di palline nell'urna $1$ e $B$ essere il numero di palline nell'urna $2$ in qualunque momento.
Lascia che le urne contengano $x_1$ e $y_1$palle rispettivamente inizialmente. ($x_1<y_1$ senza perdita di generalità ovviamente)
Sottrarre $x_1-1$ palle da entrambe le urne dando così $(1,y_1-x_1+1)$ come la nuova configurazione.
Continua a raddoppiare il numero inferiore fino a $|A-B|$ raggiungere il valore più basso possibile.
Suppoe il valore più basso di $|A-B|$ viene raggiunto in configurazione $(x_2,y_2)$. Sottraendo uno in meno rispetto al numero inferiore di$x_2,y_2$ (supponiamo $x_2$) dà $(1,y_2-x_2+1)$ come la nuova configurazione.
Lo si vede chiaramente $|y_2-x_2|\leq|y_1-x_1|$. Pertanto, continuare questo processo comporterà una riduzione continua del valore di$|A-B|$ finché non raggiunge il suo valore più basso, cioè $0$.
A quel punto, avremmo $A=B$. Prendendo così$A$ le palle fuori da entrambe le urne svuoterebbero entrambe le urne.
$\therefore $ Entrambe le urne possono essere svuotate in numero finito di operazioni.
So che sono possibili approcci più semplici per questa domanda, ma voglio verificare se anche il mio approccio è corretto o meno. Si prega di controllare il mio approccio e fornire suggerimenti. Mi dispiace anche perché non ho potuto pensare a un titolo migliore.
GRAZIE
Risposte
Supponiamo di averlo fatto $x_1,y_1$ palline in urne $A,B$rispettivamente. Possiamo accettare i seguenti casi:
Caso 1 :$x_1=y_1 \implies$ rimuoviamo $x_1$palline da entrambe le urne svuotandole entrambe. Abbiamo chiuso!
Caso 2 : senza perdita di generalità, lascia$1<x_1<y_1$. Rimuoviamo$x_1-1$ palle da entrambe le urne, dandoci $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ permettere $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, così ora abbiamo $1,y_2$ palle rispettivamente in urne $A,B$rispettivamente.
Se$y_2=1$, vai al caso 1 ,
altrimenti raddoppia il numero di palline nell'urna$A$ ripetutamente, finché non ci sono $x_2=2^k$ palline in urna $A$, così che $$x_2=2^k\le y_2<2^{k+1}$$ così ora abbiamo $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Nota che $x_2\le y_2$), quindi se $x_2=y_2$vai al caso 1 $\qquad \qquad \qquad (*)$
altrimenti torna all'inizio del caso 2 e ripeti i passaggi con$x_2,y_2$ al posto di $x_1,y_1$. (Quindi, il prossimo avremo$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ dove $y_3=y_2-x_2+1<y_2$ da $x_2>1$,
(perché$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ che dovrebbe essere già apparso in $(*)$))
Il nostro processo finirà sicuramente perché $y_1>y_2>\cdots$è una sequenza strettamente decrescente di interi positivi e non possiamo avere una sequenza infinita rigorosamente decrescente di interi positivi. Quindi, ad un certo punto, finiremo in$x_n=y_n$quando svuoteremo entrambe le urne (questo è precisamente il caso menzionato nell'ultima riga del caso 2 sopra).