RMO 1991 soru 4
Her biri rastgele sayıda top içeren iki torba vardır. Başlangıçta ikisi de boş değildir. İki tür operasyona izin verilir:
$(a)$ eşit sayıda topu aynı anda torbalardan çıkarın ve
$(b)$herhangi birindeki top sayısını iki katına çıkarın.
Bu işlemleri sonlu sayıda gerçekleştirdikten sonra, her iki torbanın da boşaltılabileceğini gösterin.
Bu soru en az soruldu $3$kez [1] [2] [3] , ancak hiçbiri benim kullandığım yaklaşımı kullanmıyor. Şimdi yaklaşımımın doğru olup olmadığından emin değilim ama doğrulamak istiyorum.
Benim yaklaşımım:
İzin Vermek $A$ torbadaki topların sayısı $1$ ve $B$ torbadaki topların sayısı $2$ Herhangi bir zamanda.
Vazoların içmesine izin ver $x_1$ ve $y_1$başlangıçta sırasıyla topları. ($x_1<y_1$ elbette cins kaybı olmadan)
Çıkar $x_1-1$ her iki torbadaki toplar $(1,y_1-x_1+1)$ yeni konfigürasyon olarak.
Kadar düşük sayıyı ikiye katlamaya devam edin. $|A-B|$ mümkün olan en düşük değere ulaşın.
En düşük değerini destekleyin $|A-B|$ yapılandırmada ulaşıldı $(x_2,y_2)$. Bir küçük sayıdan daha az$x_2,y_2$ (varsayalım $x_2$) verir $(1,y_2-x_2+1)$ yeni konfigürasyon olarak.
Açıkça görülebilir ki $|y_2-x_2|\leq|y_1-x_1|$. Bu nedenle, bu işlemin devam ettirilmesi,$|A-B|$ en düşük değerine ulaşana kadar, yani $0$.
O aşamada, sahip olurduk $A=B$. Böylece alarak$A$ Her iki torbadan çıkan toplar her iki torbayı da boşaltır.
$\therefore $ Her iki kutu da sınırlı sayıda işlemle boşaltılabilir.
Bu soru için daha basit yaklaşımların mümkün olduğunu biliyorum, ancak yaklaşımımın da doğru olup olmadığını kontrol etmek istiyorum. Lütfen yaklaşımımı kontrol edin ve önerilerde bulunun. Daha iyi bir başlık düşünemediğim için de üzgünüm.
TEŞEKKÜRLER
Yanıtlar
Varsayalım ki bizde $x_1,y_1$ çömleklerdeki toplar $A,B$sırasıyla. Aşağıdaki davaları alabiliriz:
Durum 1 :$x_1=y_1 \implies$ kaldırıyoruz $x_1$Her iki torbadaki toplar ikisini de boşaltır. İşimiz bitti!
Durum 2 : Genelliği kaybetmeden,$1<x_1<y_1$. Kaldırıyoruz$x_1-1$ bize veren iki torbadan toplar $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ İzin Vermek $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, böylece şimdi sahibiz $1,y_2$ çömleğe sırasıyla toplar $A,B$sırasıyla.
Eğer$y_2=1$, Durum 1'e gidin ,
yoksa torbadaki topların sayısını ikiye katlayın$A$ olana kadar tekrar tekrar $x_2=2^k$ torbadaki toplar $A$, Böylece $$x_2=2^k\le y_2<2^{k+1}$$ yani şimdi sahibiz $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Bunu not et $x_2\le y_2$), öyleyse $x_2=y_2$gidin Durumunda 1 $\qquad \qquad \qquad (*)$
Aksi takdirde 2. Durumun başına dönün ve adımları tekrarlayın$x_2,y_2$ yerine $x_1,y_1$. (Yani, sonra sahip olacağız$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ nerede $y_3=y_2-x_2+1<y_2$ dan beri $x_2>1$,
(çünkü$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ zaten görünmesi gereken $(*)$))
Sürecimiz kesinlikle sona erecek çünkü $y_1>y_2>\cdots$pozitif tam sayıların kesin olarak azalan bir dizisidir ve sonsuz, kesin olarak azalan bir pozitif tam sayı dizisine sahip olamayız. Yani bir adımda, sonunda$x_n=y_n$Her iki torbayı da boşaltacağımız zaman (bu tam olarak yukarıdaki Durum 2'nin son satırında bahsedilen durumdur ).