Let S denote the set of positive integer sequences (with at least two terms) whose terms sum to 2019. For a sequence of positive integers a 1 , a 2 , … , a k , its value V is defined to be V ( a 1 , a 2 , … , a k ) = a 1 ! a 2 ! ⋯ a k ! a 1 a 2 a 2 a 3 ⋯ a k − 1 a k . Then the sum of the values over all sequences in S is n m where m and n are relatively prime positive integers. Compute the last 3 digits of m + n .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Problem Loading...
Note Loading...
Set Loading...
Consider 2 0 2 0 labeled vertices and designate one of the vertices the root. Given a composition a = ( a 1 , a 2 , … , a k ) of 2 0 1 9 , construct a tree on the 2 0 2 0 vertices in which a d of the vertices are distance d from the root for 1 ≤ d ≤ k . How many ways can we do this? We can enumerate the trees by first counting the number of ways to assign distances and then counting the number of ways to connect each vertex at distance d + 1 to a vertex at distance d . The number of ways to assign distances is simply the multinomial a 1 ! a 2 ! ⋯ a k ! 2 0 1 9 ! . Since each of the a d + 1 vertices at distance d + 1 is connected to exactly one of the a d vertices at distance d , the number of ways to make the connections is a 1 a 2 a 2 a 3 ⋯ a k − 1 a k . Therefore, the composition a = ( a 1 , a 2 … , a k ) corresponds to 2 0 1 9 ! ⋅ a 1 ! a 2 ! ⋯ a k ! a 1 a 2 a 2 a 3 ⋯ a k − 1 a k distinct labeled trees. By summing this expression over all a ∈ S , we enumerate all trees that can be constructed on 2 0 2 0 vertices except the star tree in which all 2 0 1 9 non-root vertices are connected to the root at distance 1. There are 2 0 2 0 2 0 1 8 distinct trees on 2 0 2 0 labeled vertices. When we exclude the star tree, our argument shows a ∈ S ∑ 2 0 1 9 ! ⋅ a 1 ! ⋯ a k ! a 1 a 2 ⋯ a k − 1 a k = 2 0 2 0 2 0 1 8 − 1 ⟹ a ∈ S ∑ V ( a ) = 2 0 1 9 ! 2 0 2 0 2 0 1 8 − 1 . Accordingly, we must compute the last three digits of m + n = d 2 0 2 0 2 0 1 8 − 1 + d 2 0 1 9 ! , where d = g cd ( 2 0 2 0 2 0 1 8 − 1 , 2 0 1 9 ! ) = 4 0 8 0 3 9 9 . Notice that 2 0 2 0 2 0 1 8 − 1 ≡ 9 9 9 , 4 0 8 0 3 9 9 1 ≡ 5 9 9 , 2 0 1 9 ! ≡ 0 ( m o d 1 0 0 0 ) . These congruences imply d 2 0 2 0 2 0 1 8 − 1 + d 2 0 1 9 ! ≡ 9 9 9 × 5 9 9 + 0 ≡ 4 0 1 ( m o d 1 0 0 0 ) . Therefore, the last three digits of m + n are 4 0 1 .