HMMT 十一月 2012 · THM 赛 · 第 5 题

HMMT November 2012 — THM Round — Problem 5

[ 7 ] Given any positive integer, we can write the integer in base 12 and add together the digits of its 1 2 3 4 5 6 base 12 representation. We perform this operation on the number 7 repeatedly until a single base 12 digit remains. Find this digit. Rock-paper-scissors In the game of rock-paper-scissors, two players each choose one of rock, paper, or scissors to play. Rock beats scissors, scissors beats paper, and paper beats rock. If the players play the same thing, the match is considered a draw.

解析

[ 7 ] Given any positive integer, we can write the integer in base 12 and add together the digits of its 1 2 3 4 5 6 base 12 representation. We perform this operation on the number 7 repeatedly until a single base 12 digit remains. Find this digit. Answer: 4 For a positive integer n , let s ( n ) be the sum of digits when n is expressed in base 12. We k k − 1 claim that s ( n ) ≡ n (mod 11) for all positive integers n . Indeed, if n = d 12 + d 12 + · · · + d k k − 1 0 with each d an integer between 0 and 11, inclusive, because 12 ≡ 1 (mod 11), reducing modulo 11 i 1 2 3 4 5 6 gives exactly s ( n ). Thus, our answer is congruent to N = 7 modulo 11, and furthermore must be a one-digit integer in base 12; these two conditions uniquely determine the answer. 1 2 3 4 10 5 By Fermat’s Little Theorem, 7 ≡ 1 (mod 11), and also observe that 6 ≡ 6 (mod 10) because 6 2 2 ∼ ∼ 6 N ≡ 7 ≡ 343 ≡ 2 ≡ 4 (mod 11), which is our answer. = 0 (mod 2) and 6 = 1 (mod 5). Thus, (Additionally, we note that this process of writing the number in base twelve and summing the digits must eventually terminate because the value decreases after each step.) Theme Round