RMO 1991 คำถาม 4

Question

แต่ละโกศมีสองลูกโดยพลการ ทั้งสองไม่ว่างเพื่อเริ่มต้นด้วย เราได้รับอนุญาตให้ดำเนินการสองประเภท:
$(a)$ นำลูกบอลจำนวนเท่ากันออกจากโกศพร้อมกันและ
$(b)$เพิ่มจำนวนลูกบอลเป็นสองเท่าในหนึ่งในนั้น
แสดงว่าหลังจากดำเนินการเหล่านี้อย่างสมบูรณ์หลาย ๆ ครั้งแล้วโกศทั้งสองจะว่างเปล่า

คำถามนี้ถูกถามอย่างน้อยที่สุด $3$ครั้ง[1] [2] [3]แต่ดูเหมือนจะไม่มีใครใช้วิธีที่ฉันใช้ ตอนนี้ฉันไม่แน่ใจว่าแนวทางของฉันถูกต้องหรือไม่ แต่ฉันต้องการตรวจสอบ

แนวทางของฉัน:

ปล่อย $A$ เป็นจำนวนลูกบอลในโกศ $1$ และ $B$ เป็นจำนวนลูกบอลในโกศ $2$ ในเวลาใดก็ได้

ให้โกศประกอบด้วย $x_1$ และ $y_1$ลูกตามลำดับในตอนแรก ($x_1<y_1$ ไม่เสียสกุลแน่นอน)

ลบ $x_1-1$ ลูกบอลจากทั้งสองโกศจึงให้ $(1,y_1-x_1+1)$ เป็นการกำหนดค่าใหม่

ให้เพิ่มจำนวนที่ต่ำกว่าเป็นสองเท่าจนกว่า $|A-B|$ ถึงค่าต่ำสุดที่เป็นไปได้

Suppoe ค่าต่ำสุดของ $|A-B|$ ถึงการกำหนดค่า $(x_2,y_2)$. ลบหนึ่งที่น้อยกว่าจำนวนที่ต่ำกว่าของ$x_2,y_2$ (สมมติ $x_2$) ให้ $(1,y_2-x_2+1)$ เป็นการกำหนดค่าใหม่

จะเห็นได้ชัดเจนว่า $|y_2-x_2|\leq|y_1-x_1|$. ดังนั้นการดำเนินการต่อไปจะส่งผลให้มูลค่าของ$|A-B|$ จนกว่าจะถึงค่าต่ำสุดนั่นคือ $0$.

ในขั้นตอนนั้นเราจะมี $A=B$. ดังนั้นการ$A$ ลูกบอลจากโกศทั้งสองจะทำให้โกศทั้งสองว่างเปล่า

$\therefore $ โกศทั้งสองสามารถล้างออกได้ในจำนวนการดำเนินการที่ จำกัด

ฉันรู้ว่าแนวทางที่ง่ายกว่านั้นเป็นไปได้สำหรับคำถามนี้ แต่ฉันต้องการตรวจสอบว่าแนวทางของฉันถูกต้องหรือไม่ โปรดตรวจสอบแนวทางของฉันและให้คำแนะนำ ขออภัยด้วยที่ฉันคิดชื่อเรื่องที่ดีกว่านี้ไม่ได้

ขอบคุณ

Answer 1

สมมติว่าเรามี $x_1,y_1$ ลูกบอลในโกศ $A,B$ตามลำดับ เราสามารถรับกรณีต่อไปนี้:

กรณีที่ 1 :$x_1=y_1 \implies$ เราลบ $x_1$ลูกบอลจากทั้งสองโกศล้างทั้งสองลูก เสร็จแล้ว!

กรณีที่ 2 : หากไม่มีการสูญเสียทั่วไปให้$1<x_1<y_1$. เราลบ$x_1-1$ ลูกบอลจากทั้งสองโกศให้เรา $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ ปล่อย $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$ดังนั้นตอนนี้เรามี $1,y_2$ ลูกตามลำดับในโกศ $A,B$ตามลำดับ
ถ้า$y_2=1$ไปที่กรณีที่ 1 ,
อื่นสองเท่าของจำนวนลูกในโกศ$A$ ซ้ำ ๆ จนกว่าจะมี $x_2=2^k$ ลูกในโกศ $A$, ดังนั้น $$x_2=2^k\le y_2<2^{k+1}$$ ตอนนี้เรามี $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (สังเกตว่า $x_2\le y_2$) ดังนั้นถ้า $x_2=y_2$ไปที่กรณีที่ 1 $\qquad \qquad \qquad (*)$
กลับไปที่จุดเริ่มต้นของกรณีที่ 2และทำซ้ำขั้นตอนด้วย$x_2,y_2$ แทนที่ $x_1,y_1$. (ดังนั้นต่อไปเราจะมี$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ ที่ไหน $y_3=y_2-x_2+1<y_2$ ตั้งแต่ $x_2>1$,
(เพราะ$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ ซึ่งควรจะปรากฏใน $(*)$))

กระบวนการของเราจะสิ้นสุดลงอย่างแน่นอนเพราะ $y_1>y_2>\cdots$เป็นลำดับที่ลดลงอย่างเคร่งครัดของจำนวนเต็มบวกและเราไม่สามารถมีลำดับของจำนวนเต็มบวกที่ลดลงอย่างไม่มีที่สิ้นสุด ดังนั้นในบางขั้นตอนเราจะจบลงที่$x_n=y_n$เมื่อเราจะล้างทั้งสองโกศ (เป็นกรณีที่กล่าวถึงในบรรทัดสุดท้ายของกรณีที่ 2ด้านบน)