HMMT 十一月 2024 · GEN 赛 · 第 4 题

HMMT November 2024 — GEN Round — Problem 4

Compute the number of ways to pick a 3 -element subset of 1 2 3 4 5 6 7 { 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 } such that the product of the 3 numbers in the subset has no digits besides 0 and 1 when written in base 10 .

解析

Compute the number of ways to pick a 3-element subset of 1 2 3 4 5 6 7 { 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 , 10 + 1 } such that the product of the 3 numbers in the subset has no digits besides 0 and 1 when written in base 10. Proposed by: Albert Wang Answer: 26 a b c Solution: Given a subset { 10 +1 , 10 +1 , 10 +1 } , we can directly expand the product of its elements: a b c a + b + c b + c a + c a + b a b c (10 + 1)(10 + 1)(10 + 1) = 10 + 10 + 10 + 10 + 10 + 10 + 10 + 1 . In order for all digits to be 0 or 1, all 7 numbers a + b + c, b + c, a + c, a + b, a, b, c should be distinct and nonzero, with the latter being guaranteed. Without loss of generality, we can assume c > b > a . Then, a + b + c > b + c > a + c > max( a + b, c ) and min( a + b, c ) > b > a, so the only two numbers that could be the same are a + b and c . There are 9 triples ( a, b, c ) where 1 ≤ a < b < c ≤ 7 and a + b = c , namely (1 , 2 , 3), (1 , 3 , 4), (1 , 4 , 5), (1 , 5 , 6), (1 , 6 , 7), (2 , 3 , 5), (2 , 4 , 6), (2 , 5 , 7), and (3 , 4 , 7). The remaining triples ( a, b, c ) all work, so the 7 answer is − 9 = 26 . 3