분자가 1인 분수를 계속 빼면, 언젠가는 끝날까요?

분자가 1인 양수 분수만 빼면서 남은 값이 계속 작아진다면, 유한 번 뒤에 0이 될까요? 1/2에서 차례로 1/4,1/8,1/16,…을 빼는 규칙을 볼까요? 뺀 분수는 모두 서로 다르며 매번 남은 값보다 작아요.

매번 잔량은 감소하고 0에 가까워지지만, 어느 유한 n에서도 0이 아니에요. 빼기 규칙에 단위분수라는 조건을 준 것만으로 유한 종료가 따라오지 않아요.

이제 선택을 더 제한해요. 현재 잔량을 기약분수 a/b, 0<a<b로 적고, 잔량을 넘지 않는 단위분수 중 가장 큰 1/q를 빼요. a, b는 양의 정수이며 기약분수는 두 수의 최대공약수가 1인 표기예요. q는 b/a 이상인 가장 작은 정수예요. 잔량이 0이면 바로 끝내요. 4/13의 실제 추적은 다음과 같아요.

통분한 새 잔량의 분자는 aq−b입니다. q−1<b/a≤q이므로

약분은 양수 분자를 더 크게 만들지 않아요. 따라서 아직 잔량이 남았다면 기약분자의 양의 정수값이 매번 엄격히 줄어들어요. 처음 분자가 a였으면 늦어도 a번의 빼기 안에 끝나요. 첫 규칙에서는 잔량의 크기만 감소했고 기약분자는 계속 1이었어요.

분모가 중복되지 않는지도 확인해야 해요. q≥2이고 a/b<1/(q−1)이라 새 잔량은 1/[q(q−1)]보다 작고, 따라서 1/q보다 작아요. 다음 가장 큰 단위분수의 분모는 q보다 커야 해요. 뺀 항들의 합은 마지막 잔량 0을 더해 원래 분수와 같으므로 서로 다른 단위분수의 유한 합이 완성돼요.

Eppstein의 원문은 탐욕 선택의 종료와 항수 상계를 설명해요. 여기서는 같은 단위분수 빼기를 계속하면서도 끝나지 않는 자체 규칙을 나란히 두었어요. 원문의 알려진 탐욕법을 새 알고리즘으로 소개하거나, 고대 이집트가 이 방법으로 계산했다고 쓰지 않아요.

교사는 “작아진다” 다음에 무엇이 작아지는지 적게 해요. 양의 실수는 끝없이 작아질 수 있지만, 고정한 자연수 아래의 양의 정수는 무한히 엄격 감소할 수 없어요. 컴퓨터에서 잔량이 작다고 임의로 0으로 처리한 실행 결과를 이 종료 증명과 섞지 않아요.

착안: Eppstein, The Greedy Method, Introduction. 비교 규칙·문항·표·통분과 증명은 직접 구성했어요.