이상한 계산기 1

문제

U 버튼, D 버튼과 디스플레이가 있는 계산기가 있다.

디스플레이에는 처음에 \(1/1\) 이 표시되어 있으며, U버튼을 누르면 분모가 분자에 더해지고, D버튼을 누르면 분자가 분모에 더해진다.

당신은 이 계산기로 악마와 내기를 한다.

악마는 아무 양의 유리수를 말한다. 당신은 디스플레이에 표시된 수가 악마가 말한 수와 같도록 만들면 이긴다.

내기에서 항상 이길 수 있을까?

풀이

항상 이길 수 있다.

반대로, U버튼과 D버튼을 누르면 기존의 기능을 반대로 하는 계산기가 있고, 디스플레이에 악마가 말한 유리수 \(p/q\)가 있다고 가정하자. 이 경우 목적은 \(1/1\)을 (또는 \(n/n\) 꼴을) 만드는 것이다.

유클리드 호제법에 의해, 큰 수를 작은 수로 뺄셈하는 작업을 계속 반복하면 반드시 한쪽이 \(p\), \(q\)의 최소공약수 \(l\)에 도달한다. 두 수 모두 \(l\)의 배수이므로 \(l/l\) 꼴을 만들 수 있다.