숫자 카드를 하나 고르면, 남아 있는 약수 카드는 수집자에게 줘야 해요. 그렇다면 가장 큰 숫자부터 고르는 편이 유리할까요? 1, 2, 4, 8, 5, 25 여섯 장에서는 25보다 2를 먼저 골라야 최고 점수를 얻어요.
규칙을 정확히 정할게요. 고른 카드의 수보다 작은 양의 약수를 진약수라 해요. 고를 때에는 남아 있는 진약수 카드가 적어도 한 장 있어야 해요. 자신은 고른 카드 한 장을 받고, 수집자는 그때 남아 있는 진약수 카드를 모두 받아요. 같은 숫자의 카드는 한 장씩이에요. 더 고를 카드가 없으면 나머지는 수집자가 받아요. 자신의 카드값 합을 최대화하며, 수집자보다 높은 점수를 얻는 조건은 따로 넣지 않아요.
25를 먼저 고르면 1과 5를 줘요. 다음에 8을 골라 2와 4를 줄 수 있지만, 자신의 합은 33입니다. 2부터 고르면 1을 주고, 8을 골라 4를 주고, 25를 골라 5를 줘요. 자신의 합은 35가 돼요. 2 뒤에 25를 먼저 고르고 8을 나중에 골라도 같은 35입니다.
| 처음 고른 카드 | 그 선택 뒤 얻을 수 있는 최고 합 |
|---|---|
| 2 | 35 |
| 5 | 13 |
| 25 | 33 |
5를 먼저 고르면 1이 사라져요. 이후 25의 진약수 5도 이미 자신의 손에 있어, 25를 고를 수 없어요. 그때 8을 얻어 13으로 끝낼 수 있어요. 작은 수가 항상 좋다는 규칙도 아니에요. 첫 선택이 어떤 카드를 수집자에게 없애는지가 중요해요.
Math for Love의 Tax Collector 수업 자료는 매 선택마다 수집자에게 지급할 약수가 있어야 한다는 규칙과 첫 선택을 토론하는 질문을 제시해요. 그 자료는 연속된 정수 카드 판에서 가장 큰 소수로 시작하는 이유를 물어요. 위의 띄엄띄엄 놓인 판에 그 질문의 답을 그대로 적용해도 될까요? 원문의 연속된 판이 잘못됐다는 뜻은 아니에요. 판에 실제로 놓인 수가 달라졌기 때문에 전략의 적용 조건을 다시 따지는 거예요.
이 차이를 모든 크기의 판에서 확인해 볼까요? 서로 다른 소수 p₁부터 pᵣ까지를 고르고, 각 소수의 거듭제곱을 mᵢ단계까지 놓아요. r과 모든 mᵢ는 1 이상인 유한 정수예요. 카드 1은 묶음마다 주지 않고, 판 전체에 딱 한 장만 놓아요.
소수란 1보다 크고 양의 약수가 1과 자기 자신뿐인 정수예요. 서로 다른 소수의 묶음 사이에는 진약수 관계가 없어요. 각 거듭제곱의 판 위 진약수는 1과 같은 묶음의 더 작은 거듭제곱뿐이에요.
첫 선택에서는 어떤 묶음이든 카드 1로 지급할 수 있어요. 첫 선택이 끝나면 1은 사라져요. 다른 묶음에서 그 소수 자체를 고르는 것은 이제 불가능해요. 다만 제곱 이상의 카드는 그 아래 거듭제곱으로 지급할 수 있어요. 따라서 1이 어느 묶음의 첫 선택에 쓰이는지가 묶음 전체의 최고 합에 관여해요.
한 묶음에서 지수 k를 골랐다면 더 낮은 카드가 모두 사라져요. 지수 k+1은 지급할 카드가 없어 고를 수 없어요. 지수 k+2 이상은 바로 아래의 남은 카드로 지급할 수 있어요. 즉 자신의 카드 지수는 작은 것부터 큰 것 순서로, 적어도 두 단계씩 떨어져야 해요.
그런 선택 중 합이 가장 큰 것은 꼭 맨 위 카드를 포함해요. 소수 p는 2 이상이므로
맨 위 카드 하나가 그 아래 카드 전부를 더한 것보다 커요. 맨 위를 빼는 선택은 모두 손해예요. 맨 위를 포함하면 바로 아래는 제외해야 하고, 그보다 아래에서 같은 판단을 반복해요. 그래서 최고 선택 집합은 맨 위에서 두 단계씩 내려간 카드들로 유일하게 정해져요. 이 계산은 알려진 거듭제곱과 등비합을 도구로 사용해요.
카드 1을 이미 잃은 묶음 i의 최고 합을 Bᵢ라 해 볼까요? 지수 1은 고를 수 없으므로 아래와 같이 2 이상까지만 내려가요. mᵢ=1이면 더할 항이 없어 Bᵢ=0입니다.
첫 묶음도 mᵢ가 짝수이면 최고 선택이 지수 2에서 끝나므로 Bᵢ와 같아요. 홀수이면 지수 1의 카드 pᵢ를 더 받을 수 있어 Bᵢ+pᵢ입니다. 따라서 길이가 홀수인 묶음이 있다면, 그중 소수가 가장 큰 묶음에 카드 1을 쓰는 것이 유일하게 최선이에요. 그 묶음의 번호를 j라 해 볼까요?
홀수 길이 묶음이 있으면 최적 첫 카드는 pⱼ 하나뿐이에요. 그 묶음에서는 지수 1, 3, …, mⱼ를 고르고, 다른 묶음에서는 위에서 두 단계씩 내려오되 지수 2 이상인 카드만 골라요. 실제로 고르는 순서는 각 묶음 안에서 지수가 증가해야 해요. 그 조건과 첫 카드 pⱼ만 지키면 다른 묶음의 선택을 중간에 자유롭게 끼워도 합은 M입니다.
모든 길이가 짝수이면 최적 첫 카드는 어느 묶음의 pᵢ²라도 돼요. 각 묶음에서 지수 2, 4, …, mᵢ를 작은 것부터 고르면 돼요. 이 경우에도 최적 카드 집합은 유일하지만, 서로 다른 묶음의 순서는 하나로 정해지지 않아요. 카드 집합의 유일성과 실행 순서의 유일성을 구별해야 해요.
최고 합을 얻는 실행은 몇 가지일까요? 묶음 i에서 자신이 받는 카드 수를 Kᵢ, 그 합을 K라 해 볼까요? 모두 짝수 길이면 Kᵢ=mᵢ/2입니다. 홀수 길이 묶음이 있으면 첫 묶음 j만 Kⱼ=(mⱼ+1)/2이고, 나머지는 Kᵢ=⌊mᵢ/2⌋입니다. 바닥 기호는 그 수 이하의 가장 큰 정수를 뜻해요.
같은 묶음의 차례는 작은 지수부터 이미 정해져 있어요. 따라서 묶음 이름을 Kᵢ번씩 적어 나열하면 카드 순서가 자동으로 정해져요. 홀수 길이 경우에는 맨 앞의 j를 먼저 고정한 뒤 나머지만 나열해요. 제공 교재의 같은 것을 포함한 순열을 이용한 계산이며, 같은 숫자의 실제 카드가 여러 장이라는 뜻은 아니에요. 0!=1로 두면 선택을 못 하는 한 장짜리 묶음도 포함돼요.
처음의 판에서 2의 묶음 길이는 3, 5의 길이는 2입니다. 홀수 길이 묶음은 2의 묶음뿐이어서 반드시 2부터 시작해요. 최고 카드 집합은 2, 8, 25이고 실행은 두 가지예요. 반면 모든 묶음이 한 장짜리라면 가장 큰 소수 한 장만 얻고 끝나요. 다른 소수들은 1을 잃어 지급할 약수가 없기 때문이에요. 묶음이 하나이고 길이가 한 단계일 때에도 소수 카드 한 장과 실행 한 가지라는 결론이 맞아요.
교사는 먼저 첫 카드만 정한 답과 그 뒤까지 최선으로 마친 합을 나누어 적게 할 수 있어요. 이어 각 묶음을 서로 독립된 판으로 나누어 카드 1을 한 장씩 주고, 해당 판의 진약수만 지급하는 규칙으로 바꾸면 첫 선택의 경쟁이 왜 사라지는지 물어요. 이 규칙 변경은 원래 판의 전략을 확인하는 비교 질문이며, 학생의 성취나 학습효과를 측정한 결과는 아니에요. 단순히 가장 큰 수, 가장 큰 소수, 가장 작은 수 중 하나를 외우게 하는 대신, 어떤 카드가 누구에게 넘어가는지 설명하도록 제안해요.
착안: Math for Love, Tax Collector Lesson Plans, PDF 2–6쪽. 진약수 지급 게임과 첫 선택을 토론하는 관점만 참고했어요. 소수 거듭제곱 묶음과 공유 카드 1의 조건, 최고 합·최적 첫 선택·모든 실행의 분류와 증명은 자체 교육용으로 작성했어요. 원문의 카드 도판이나 특정 학생의 응답·성과 자료를 옮기지 않았어요.