RMO 1991 pytanie 4

Question

Istnieją dwie urny, z których każda zawiera dowolną liczbę piłek. Na początku obie nie są puste. Dozwolone są dwa rodzaje operacji:
$(a)$ usunąć równą liczbę piłek jednocześnie z urn, i
$(b)$podwoić liczbę piłek w jednej z nich.
Pokaż, że po wykonaniu tych operacji skończenie wiele razy, obie urny mogą zostać opróżnione.

To pytanie zostało przynajmniej zadane $3$razy [1] [2] [3] , ale żaden z nich nie wydaje się używać podejścia, którego używam. Teraz nie jestem pewien, czy moje podejście jest poprawne, czy nie, ale chcę to zweryfikować.

Moje podejście:

Pozwolić $A$ być liczbą piłek w urnie $1$ i $B$ być liczbą piłek w urnie $2$ w dowolnym czasie.

Niech urny zawierają $x_1$ i $y_1$piłki odpowiednio początkowo. ($x_1<y_1$ oczywiście bez utraty hojności)

Odejmować $x_1-1$ kule z obu urn dając w ten sposób $(1,y_1-x_1+1)$ jako nowa konfiguracja.

Podwajaj niższą liczbę, aż $|A-B|$ osiągnąć najniższą możliwą wartość.

Uzupełnij najniższą wartość $|A-B|$ zostanie osiągnięty w konfiguracji $(x_2,y_2)$. Odejmując o jeden mniej niż mniejszą liczbę$x_2,y_2$ (przypuszczać $x_2$) daje $(1,y_2-x_2+1)$ jako nowa konfiguracja.

Widać to wyraźnie $|y_2-x_2|\leq|y_1-x_1|$. Kontynuacja tego procesu spowoduje więc ciągłe obniżanie wartości$|A-B|$ dopóki nie osiągnie najniższej wartości, tj $0$.

Na tym etapie tak by było $A=B$. Tak więc biorąc$A$ kule z obu urn opróżnią obie urny.

$\therefore $ Obie urny można opróżnić w skończonej liczbie operacji.

Wiem, że w przypadku tego pytania możliwe są prostsze podejścia, ale chcę sprawdzić, czy moje podejście jest również poprawne, czy nie. Sprawdź moje podejście i podaj sugestie. Przepraszam też, że nie mogłem wymyślić lepszego tytułu.

DZIĘKI

Answer 1

Załóżmy, że mamy $x_1,y_1$ kule w urnach $A,B$odpowiednio. Możemy przyjąć następujące przypadki:

Przypadek 1 :$x_1=y_1 \implies$ usuwamy $x_1$kule z obu urn opróżniające je obie. Skończyliśmy!

Przypadek 2 : Bez utraty ogólności, niech$1<x_1<y_1$. Usuwamy$x_1-1$ kule z obu urn, podając nam $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ pozwolić $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, więc teraz mamy $1,y_2$ kule odpowiednio w urnach $A,B$odpowiednio.
Gdyby$y_2=1$przejdź do przypadku 1 , w przeciwnym razie
podwoj liczbę piłek w urnie$A$ wielokrotnie, aż będą $x_2=2^k$ kule w urnie $A$więc to $$x_2=2^k\le y_2<2^{k+1}$$ więc teraz mamy $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Uwaga $x_2\le y_2$), więc jeśli $x_2=y_2$przejdź do przypadku 1 $\qquad \qquad \qquad (*)$
w przeciwnym razie wróć do początku przypadku 2 i powtórz kroki za pomocą$x_2,y_2$ zamiast $x_1,y_1$. (Więc następnym razem będziemy mieć$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ gdzie $y_3=y_2-x_2+1<y_2$ od $x_2>1$,
(ponieważ$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ który powinien już się pojawić w $(*)$))

Nasz proces na pewno się zakończy, ponieważ $y_1>y_2>\cdots$jest ściśle malejącą sekwencją dodatnich liczb całkowitych i nie możemy mieć nieskończonej, ściśle malejącej sekwencji dodatnich liczb całkowitych. Więc na pewnym etapie skończymy na$x_n=y_n$kiedy opróżnimy obie urny (jest to dokładnie przypadek wspomniany w ostatnim wierszu przypadku 2 powyżej).