RMO 1991 câu hỏi 4
Có hai bình đựng một số bi tùy ý. Cả hai đều không trống để bắt đầu. Chúng tôi được phép thực hiện hai loại hoạt động:
$(a)$ loại bỏ một số lượng bằng nhau các quả bóng đồng thời từ các bình, và
$(b)$nhân đôi số quả bóng trong bất kỳ một trong số chúng.
Chứng tỏ rằng sau khi thực hiện các thao tác này nhiều lần, cả hai bình đều có thể trống rỗng.
Câu hỏi này đã được hỏi ít nhất $3$lần [1] [2] [3] , nhưng dường như không ai trong số họ sử dụng cách tiếp cận mà tôi đang sử dụng. Bây giờ tôi không chắc liệu cách tiếp cận của tôi có đúng hay không, nhưng tôi muốn xác minh nó.
Phương pháp tiếp cận của tôi:
Để cho $A$ là số lượng bóng trong bình $1$ và $B$ là số lượng bóng trong bình $2$ tại bất kỳ thời điểm nào.
Hãy để những chiếc bình chứa $x_1$ và $y_1$ban đầu các quả bóng tương ứng. ($x_1<y_1$ tất nhiên là không mất tính chung)
Trừ đi $x_1-1$ bóng từ cả hai bình do đó cho $(1,y_1-x_1+1)$ như cấu hình mới.
Tiếp tục nhân đôi số thấp hơn cho đến khi $|A-B|$ đạt giá trị thấp nhất có thể.
Bổ sung giá trị thấp nhất của $|A-B|$ đạt được ở cấu hình $(x_2,y_2)$. Trừ một số nhỏ hơn số thấp hơn của$x_2,y_2$ (giả sử $x_2$) cho $(1,y_2-x_2+1)$ như cấu hình mới.
Có thể thấy rõ rằng $|y_2-x_2|\leq|y_1-x_1|$. Do đó, tiếp tục quá trình này sẽ dẫn đến việc giảm liên tục giá trị của$|A-B|$ cho đến khi nó đạt đến giá trị thấp nhất, tức là $0$.
Ở giai đoạn đó, chúng tôi sẽ có $A=B$. Do đó lấy$A$ bóng ra khỏi cả hai bình sẽ làm trống cả hai bình.
$\therefore $ Cả hai bình có thể được làm trống trong một số lần hoạt động hữu hạn.
Tôi biết rằng có thể áp dụng các cách tiếp cận đơn giản hơn cho câu hỏi này, nhưng tôi muốn kiểm tra xem liệu cách tiếp cận của mình có đúng hay không. Vui lòng kiểm tra cách tiếp cận của tôi và cung cấp các đề xuất. Cũng xin lỗi vì tôi không thể nghĩ ra một tiêu đề tốt hơn.
CẢM ƠN
Trả lời
Giả sử chúng ta có $x_1,y_1$ bóng trong bình $A,B$tương ứng. Chúng ta có thể lấy các trường hợp sau:
Trường hợp 1 :$x_1=y_1 \implies$ chúng tôi loại bỏ $x_1$bóng từ cả hai bình làm rỗng cả hai. Chúng ta xong rồi!
Trường hợp 2 : Không mất tính tổng quát, hãy$1<x_1<y_1$. Chúng tôi loại bỏ$x_1-1$ bóng từ cả hai bình, cho chúng tôi $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ để cho $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, để bây giờ chúng ta có $1,y_2$ quả bóng tương ứng trong bình $A,B$tương ứng.
Nếu$y_2=1$, chuyển đến Trường hợp 1 ,
nếu không thì nhân đôi số bóng trong bình$A$ lặp đi lặp lại, cho đến khi có $x_2=2^k$ bóng trong lọ $A$, vậy nên $$x_2=2^k\le y_2<2^{k+1}$$ vì vậy bây giờ chúng tôi có $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Lưu ý rằng $x_2\le y_2$), vì thế nếu $x_2=y_2$chuyển đến Trường hợp 1 $\qquad \qquad \qquad (*)$
nếu không, hãy quay lại phần đầu của Trường hợp 2 và lặp lại các bước với$x_2,y_2$ thay cho $x_1,y_1$. (Vì vậy, tiếp theo chúng ta sẽ có$$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ Ở đâu $y_3=y_2-x_2+1<y_2$ từ $x_2>1$,
(bởi vì$x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ mà lẽ ra đã xuất hiện trong $(*)$))
Quá trình của chúng tôi chắc chắn sẽ kết thúc vì $y_1>y_2>\cdots$là một dãy số nguyên dương giảm dần và chúng ta không thể có một dãy số nguyên dương giảm dần vô hạn. Vì vậy, ở một số bước, chúng ta sẽ kết thúc ở$x_n=y_n$khi chúng ta sẽ làm trống cả hai bình (đây chính xác là trường hợp được đề cập trong dòng cuối cùng của Trường hợp 2 ở trên).