RMO 1991 질문 4
각각 임의의 수의 공이 들어있는 두 개의 항아리가 있습니다. 둘 다 처음에는 비어 있지 않습니다. 두 가지 유형의 작업이 허용됩니다.
$(a)$ 항아리에서 같은 수의 공을 동시에 제거하고
$(b)$그중 하나의 공 수를 두 배로 늘립니다.
이러한 작업을 여러 번 수행 한 후 두 항아리를 모두 비울 수 있음을 보여줍니다.
이 질문은 최소한 요청되었습니다 $3$times [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|$ 가능한 가장 낮은 값에 도달하십시오.
최저 가치를 제공하십시오 $|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 $ 두 항아리 모두 유한 한 수의 작업으로 비울 수 있습니다.
이 질문에 대해 더 간단한 접근 방식이 가능하다는 것을 알고 있지만 내 접근 방식도 올바른지 확인하고 싶습니다. 내 접근 방식을 확인하고 제안을 제공하십시오. 더 나은 제목을 생각하지 못해서 미안합니다.
감사
답변
우리가 가지고 있다고 가정 $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 의 마지막 줄에서 언급 한 경우입니다 ).