못은 5개짜리와 8개짜리 꾸러미로만 살 수 있다고 해 볼까요? 포장을 뜯어 일부만 사거나 남은 물건을 버리는 일은 허용하지 않아요. 각 꾸러미는 필요한 만큼 계속 살 수 있어요. 정확히 27개는 만들 수 없지만, 그보다 큰 수량은 모두 맞출 수 있을까요? 실제 판매 조건이 아닌 자체 주문 모형이에요.
28개는 5개짜리 네 묶음과 8개짜리 한 묶음, 29개는 5개짜리 한 묶음과 8개짜리 세 묶음이에요. 30, 31, 32개도 차례로 만들 수 있어요. 다섯 수량이 연속으로 가능하면 여기에 5개씩 더해 그 뒤의 모든 수량을 만들어요. 그런데 27개가 정말 마지막 빈칸인지, 처음부터 세어 보지 않고 증명할 방법도 있어요.
두 포장 단위를 양의 정수 a, b라 해 볼까요? 먼저 a,b≥2이고 최대공약수가 1인 경우를 다뤄요. 이를 서로소라고 해요. 원하는 수량 n은 0 이상의 정수예요. 주문 가능한 조건은 다음 식에 0 이상의 정수 해가 있는 거예요.
x나 y가 음수여도 된다고 바꾸면 다른 문제예요. 예를 들어 27=7×5−1×8은 정수 식으로 맞지만, 8개짜리 꾸러미를 한 묶음 반납해 빼는 주문이에요. 지금 규칙에서는 이런 답을 사용할 수 없어요.
b짜리 묶음의 개수를 0,1,…,a−1로 제한해 나머지를 볼까요? b와 a가 서로소라 이 a개 수량 jb는 a로 나눈 나머지가 모두 달라요. 두 나머지가 같다면 a가 b(j₁−j₂)를 나누며, 서로소 조건에서 j₁−j₂도 나눠요. 두 묶음 개수의 차는 절댓값이 a보다 작아 두 개수가 같을 수밖에 없어요. a가지 나머지를 빠짐없이 한 번씩 얻어요.
그러므로 어떤 정수 n도 다음 정규화 표시를 정확히 하나 가져요. 이때 k는 음수일 수도 있어요.
오른쪽에서 왼쪽으로는 그대로 k묶음과 j묶음을 사면 돼요. 반대 방향도 확인해 볼까요? 어떤 주문 n=ax+by가 있다면 y=j+ta로 쓸 수 있어요. y≥0이고 0≤j<a라 t≥0입니다. 따라서 정규화한 k는 x+tb≥0입니다. 이 양방향을 확인해야 음수인 k를 다른 주문으로 피할 수 없다는 결론이 돼요.
불가능한 수량은 k≤−1인 표시에서 나와요. 그런 표시 중 가장 큰 값을 만들려면 k=−1, j=a−1을 골라요. 그 값은
F 자체는 정규화한 k가 −1이므로 불가능해요. F보다 큰 n에서는 k가 음수일 수 없어 반드시 주문된다. 5와 8에서는 F=27입니다. 27 하나의 실패와 그 뒤의 몇 성공만 비교한 것이 아니라, 모든 큰 수량까지 허용하는 경계를 증명했어요.
빈칸은 모두 몇 개일까요? 0부터 F까지에서 n과 F−n을 짝지으면 주문 가능 여부가 반대가 돼요. n=ka+jb에 대응하는 정규화 표시는 다음과 같아요.
정수 k와 −1−k 중 정확히 하나만 0 이상이에요. 그래서 한 쌍 중 한 수량만 가능해요. 서로소 a,b에서는 둘 다 짝수일 수 없어 (a−1)(b−1)이 짝수이고 F는 홀수예요. 짝짓기의 가운데 고정점도 없어요. 0부터 F까지의 F+1개 중 절반, 즉 (a−1)(b−1)/2개가 불가능해요. 0은 주문하지 않는 선택으로 가능하므로 이 수는 양의 빈 수량의 개수이기도 해요. 5와 8의 빈칸은 14개예요.
서로소 조건을 빼면 마지막 빈칸이 사라질 수 있어요. 10개와 16개 포장은 합이 항상 짝수여서 아무리 큰 홀수 수량도 불가능해요. 일반적으로 최대공약수 d>1이면 d의 배수가 아닌 수량은 끝없이 빠져요. 배수 수량만 비교하면 단위를 d로 나누어 서로소 문제로 되돌릴 수 있어요. 한 포장 단위가 1이면 모든 수량이 가능해 양의 빈칸 자체가 없어요.
교사는 ‘정수 해가 있다’, ‘개수가 음수가 아니다’, ‘모든 큰 수량이 가능하다’를 다른 줄에 쓰게 해요. 제공 교재의 필요충분조건은 정규화한 k의 부호와 주문 가능성을 두 방향으로 연결하는 기초예요. 두 포장 단위의 정리 전체가 그 교재에 수록됐다는 뜻은 아니에요.
착안: Jean Gallier, The Frobenius Coin Problem, University of Pennsylvania, 두 단위의 표현과 경계. 알려진 두 단위 정리와 나머지 전략을 명시하고, 꾸러미 주문의 조건·자료·전개를 자체 작성했어요. 원문의 실물 통화·도판·문항을 옮기지 않았어요.