HMMT 二月 2021 · COMB 赛 · 第 3 题

HMMT February 2021 — COMB Round — Problem 3

Let N be a positive integer. Brothers Michael and Kylo each select a positive integer less than or equal to N , independently and uniformly at random. Let p denote the probability that the product N of these two integers has a units digit of 0. The maximum possible value of p over all possible choices N a of N can be written as , where a and b are relatively prime positive integers. Compute 100 a + b . b

解析

Let N be a positive integer. Brothers Michael and Kylo each select a positive integer less than or equal to N , independently and uniformly at random. Let p denote the probability that the product N of these two integers has a units digit of 0. The maximum possible value of p over all possible choices N a of N can be written as , where a and b are relatively prime positive integers. Compute 100 a + b . b Proposed by: James Lin Answer: 2800 b N/k c Solution: For k ∈ { 2 , 5 , 10 } , let q = be the probability that an integer chosen uniformly at k N 1 random from [ N ] is a multiple of k . Clearly, q ≤ , with equality iff k divides N . k k The product of p , p ∈ [ N ] can be a multiple of 10 in two ways: 1 2 • one of them is a multiple of 10; this happens with probability q (2 − q ); 10 10 • one of them is a multiple of 2 (but not 5) and the other is a multiple of 5 (but not 2); this happens with probability 2( q − q )( q − q ). 2 10 5 10 This gives p = q · (2 − q ) + 2( q − q )( q − q ) N 10 10 2 10 5 10 ( ) ( ) 1 1 ≤ q · (2 − q ) + 2 − q − q 10 10 10 10 2 5 1 2 = (1 + 3 q + 5 q ) 10 10 5 ( ) 1 3 5 ≤ 1 + + 5 10 100 27 = , 100 and equality holds iff N is a multiple of 10.