PUMaC 2017 · 数论（B 组） · 第 2 题

PUMaC 2017 — Number Theory (Division B) — Problem 2

Let S = { 1 , 22 , 333 , . . . , 999999999 } . For how many pairs of integers ( a, b ) where a, b ∈ S and a < b is it the case that a divides b ?

解析

Let f ( n ) = nnn · · · n , the integer with n n ’s. (i.e. S = { f (1) , f (2) , . . . , f (9) } .) f ( a ) | f ( b ) only when a | b , since f ( n ) = n · (111 · · · 1) (with n 1’s) so when m | n the n 1’s can be broken up into blocks of size m each. We thus need to count the number of pairs ( a, b ) of integers between 1 and 9 inclusive for which a | b (and a < b ). 9: 3,1 8: 4,2,1 7: 1 6: 3,2,1 5: 1 4: 2,1 3: 1 2: 1 There are 14 pairs contained in the above list. Problem written by Eric Neyman