HMMT 二月 2024 · 冲刺赛 · 第 14 题
HMMT February 2024 — Guts Round — Problem 14
题目详情
- [9] Compute the smallest positive integer such that, no matter how you rearrange its digits (in base ten), the resulting number is a multiple of 63 .
解析
- [9] Compute the smallest positive integer such that, no matter how you rearrange its digits (in base ten), the resulting number is a multiple of 63 . Proposed by: Arul Kolla Answer: 111 888 Solution: First, the number must be a multiple of 9 and 7 . The first is easy to check and holds for all permutations. Note that when two adjacent digits a and b are swapped, the number changes by k 9( a − b ) · 10 (we disregard sign), so 9( a − b ) must also be a multiple of 63 for all digits a and b . In particular, this is sufficient, since a permutation can be represented as a series of transpositions. This means that a − b must be a multiple of 7 for all digits a and b , so either all digits are equal or they are in { 0 , 7 } , { 1 , 8 } , or { 2 , 9 } . We find the minimum for each case separately. We first provide the following useful fact: the first repunit (numbers 1 , 11 , 111 , …) that is a multiple of 7 is 111111 . This is because 10 mod 7 = 3 , and 3 is a generator modulo 7 (of course, you can just compute the powers of 3 by hand, and it will not take much longer). If a number k · 1 . . . 1 is a multiple of 63 , then either k or 1 . . . 1 is a multiple of 7 ; if it is k , then it’s clear that we need 777 777 777 to make the sum a multiple of 9 . If 1 . . . 1 is a multiple of 7 , then it is at least 111 111 , then to make a multiple of 9 , we need 333 333 . If the only digits are 7 and 0 , then we need at least nine sevens to make the digit sum a multiple of nine, which has more digits than 333 333 . If the only digits are 8 and 1 , then we can note that since 8 and 1 are both 1 (mod 7) , these numbers are equivalent to the repunits modulo 7 , so such numbers have at least six digits. The best such six-digit number with digits summing to a multiple of 9 is 111 888 , which is our new candidate. If the only digits are 9 and 2 , then by analogous logic such numbers have at least six digits. But the smallest such number is 999 999 , which is not better. So our best answer is 111 888 . It works.