RMO 1991 Frage 4
Es gibt zwei Urnen, die jeweils eine beliebige Anzahl von Kugeln enthalten. Beide sind zunächst nicht leer. Wir dürfen zwei Arten von Operationen durchführen:
$(a)$ Entfernen Sie eine gleiche Anzahl von Kugeln gleichzeitig aus den Urnen und
$(b)$Verdoppeln Sie die Anzahl der Bälle in einem von ihnen.
Zeigen Sie, dass nach einer endlichen Ausführung dieser Vorgänge beide Urnen leer gemacht werden können.
Diese Frage wurde mindestens gestellt $3$mal [1] [2] [3] , aber keiner von ihnen scheint den Ansatz zu verwenden, den ich verwende. Jetzt bin ich mir nicht sicher, ob mein Ansatz korrekt ist oder nicht, aber ich möchte ihn überprüfen.
Mein Ansatz:
Lassen $A$ sei die Anzahl der Bälle in der Urne $1$ und $B$ sei die Anzahl der Bälle in der Urne $2$ zu einem bestimmten Zeitpunkt.
Lassen Sie die Urnen enthalten $x_1$ und $y_1$Bälle jeweils zunächst. (($x_1<y_1$ natürlich ohne Verlust der Großzügigkeit)
Subtrahieren $x_1-1$ Bälle aus beiden Urnen geben also nach $(1,y_1-x_1+1)$ als neue Konfiguration.
Verdoppeln Sie die niedrigere Zahl bis $|A-B|$ den niedrigstmöglichen Wert erreichen.
Angenommen, der niedrigste Wert von $|A-B|$ wird bei der Konfiguration erreicht $(x_2,y_2)$. Subtrahieren Sie eins weniger als die niedrigere Anzahl von$x_2,y_2$ (annehmen $x_2$) gibt $(1,y_2-x_2+1)$ als neue Konfiguration.
Das ist deutlich zu sehen $|y_2-x_2|\leq|y_1-x_1|$. Wenn Sie diesen Prozess fortsetzen, verringert sich der Wert von kontinuierlich$|A-B|$ bis es seinen niedrigsten Wert erreicht, dh $0$.
Zu diesem Zeitpunkt hätten wir $A=B$. Also nehmen$A$ Kugeln aus beiden Urnen würden beide Urnen leeren.
$\therefore $ Beide Urnen können in endlicher Anzahl von Operationen geleert werden.
Ich weiß, dass für diese Frage einfachere Ansätze möglich sind, aber ich möchte prüfen, ob mein Ansatz auch korrekt ist oder nicht. Bitte überprüfen Sie meinen Ansatz und machen Sie Vorschläge. Es tut mir auch leid, dass ich mir keinen besseren Titel vorstellen konnte.
VIELEN DANK
Antworten
Angenommen, wir haben $x_1,y_1$ Bälle in Urnen $A,B$beziehungsweise. Wir können folgende Fälle annehmen:
Fall 1 :$x_1=y_1 \implies$ wir entfernen $x_1$Kugeln aus beiden Urnen entleeren beide. Wir sind fertig!
Fall 2 : Ohne Verlust der Allgemeinheit, lassen Sie$1<x_1<y_1$. Wir entfernen$x_1-1$ Bälle aus beiden Urnen, die uns geben $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ Lassen $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, so dass wir jetzt haben $1,y_2$ Bälle jeweils in Urnen $A,B$beziehungsweise.
Wenn$y_2=1$Fahren Sie mit Fall 1 fort ,
andernfalls verdoppeln Sie die Anzahl der Bälle in der Urne$A$ wiederholt, bis es gibt $x_2=2^k$ Bälle in Urne $A$, damit $$x_2=2^k\le y_2<2^{k+1}$$ also jetzt haben wir $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Beachten Sie, dass $x_2\le y_2$), also wenn $x_2=y_2$Fahren Sie mit Fall 1 fort $\qquad \qquad \qquad (*)$
Andernfalls kehren Sie zum Anfang von Fall 2 zurück und wiederholen Sie die Schritte mit$x_2,y_2$ anstelle von $x_1,y_1$. (Also, als nächstes werden wir haben$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ wo $y_3=y_2-x_2+1<y_2$ schon seit $x_2>1$,
(weil$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ das hätte schon in erscheinen sollen $(*)$))
Unser Prozess wird definitiv enden, weil $y_1>y_2>\cdots$ist eine streng abnehmende Folge positiver Ganzzahlen, und wir können keine unendlich streng abnehmende Folge positiver Ganzzahlen haben. Irgendwann werden wir also bei landen$x_n=y_n$wenn wir beide Urnen leeren (dies ist genau der Fall, der in der letzten Zeile von Fall 2 oben erwähnt wurde).