동전은 같은 지갑에서 필요한 만큼 골라 쓰되, 거스름돈을 받지 않는다고 해 볼까요? 1부터 15까지 어떤 정수 금액을 요구해도 낼 수 있는 동전 여섯 개를 만들 수 있을까요? 실제 통화 대신 양의 정수인 자체 액면을 쓰고, 두 종류만 허용해요.
1짜리 세 개와 4짜리 세 개를 챙기면 돼요. 4짜리를 0, 1, 2, 3개 쓰는 경우에 작은 동전 세 개를 붙이면 다음 네 구간을 만들어요.
같은 동전을 매번 새로 살 수 있다는 뜻은 아니에요. 각 요청 금액을 낼 때 처음의 지갑에서 부분 집합을 골라 쓰며, 여러 요청을 연속해서 지불하는 상황은 묻지 않아요.
큰 액면을 더 키우면 더 좋은 지갑이 될까요? 1짜리 세 개와 5짜리 세 개의 총액은 18입니다. 그러나 4를 만들 수 없어 처음부터 연속으로 내는 범위는 3까지예요. 총액과 빈 금액 없는 범위는 다른 수예요.
이제 동전 K개로 가능한 가장 긴 범위를 구해 볼까요? K≥2이며 두 액면을 실제로 모두 써요. 1을 만들려면 작은 액면은 반드시 1이어야 해요. 그 개수를 a≥1, 큰 액면 d≥2의 개수를 b≥1로 두면 a+b=K입니다. 큰 동전을 j개 쓸 때 가능한 정수는
입니다. d≤a+1이면 이 구간들이 빈 정수 없이 이어져 0부터 a+bd까지 모든 금액을 만들어요. d>a+1이면 a+1이 첫 구간과 다음 구간 사이에서 빠져요. 그 경우 연속 범위는 a까지이고, 최적 후보에서 제외할 수 있어요.
고정한 a,b에서 빈칸을 만들지 않는 가장 큰 액면은 d=a+1입니다. 최대 끝값은
따라서 동전 개수를 둘로 나누는 문제로 바뀌어요. 두 수 a+1,b+1의 합은 K+2이고,
두 개수의 차가 작을수록 곱이 커요. K가 짝수이면 a=b=K/2, 홀수이면 a와 b가 이웃한 정수일 때만 최대예요. 전체 답은
바닥 기호는 주어진 실수 이하의 가장 큰 정수를 뜻해요. 최대 지갑은 위 개수 조건과 d=a+1을 동시에 만족하는 것뿐이에요. 액면을 더 낮추면 b≥1이므로 끝값이 작아지고, 첫 빈칸이 있는 지갑은 a≤K−1까지만 보장해 위 최대에 못 미쳐요.
예를 들어 K=6의 최적 지갑은 1짜리 3개·4짜리 3개뿐이에요. K=7에서는 1짜리 3개·4짜리 4개, 또는 1짜리 4개·5짜리 3개가 모두 19까지 만들어요. 액면만 같아야 최적인 것도 아니고, 총액이 같기만 하면 충분한 것도 아니에요.
NRICH의 동전 구성 질문에 착안하되 고정된 총개수에서 최대 범위와 모든 최적 지갑을 자체 문항으로 증명했어요. 교사는 작은 금액의 첫 빈칸, 구간의 연결, 끝값의 최대를 차례로 확인하게 해요. 동전을 양쪽 저울에 올리거나 빚을 허용하는 규칙으로 바꾸면 이 증명을 그대로 쓰지 않아요.
출처·착안: NRICH, Wearing a Hole in Your Pocket. 자체 액면·문항·최대 범위와 등호 조건이며 실제 화폐 정책이나 지불 관행의 분석이 아니다.