Observation and experiment for gathering material, induction and deduction for elaborating it

Let S 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 a_{1},a_{2},\ldots,a_{k} , its value V V is defined to be V ( a 1 , a 2 , , a k ) = a 1 a 2 a 2 a 3 a k 1 a k a 1 ! a 2 ! a k ! . V(a_1, a_2, \dots, a_k) = \frac{a_1^{a_2} a_2^{a_3} \cdots a_{k-1}^{a_k}}{a_1! a_2! \cdots a_k!}. Then the sum of the values over all sequences in S S is m n \frac mn where m m and n n are relatively prime positive integers. Compute the last 3 digits of m + n m+n .


The answer is 401.

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.

1 solution

Matt Janko
Oct 4, 2020

Consider 2020 2020 labeled vertices and designate one of the vertices the root. Given a composition a = ( a 1 , a 2 , , a k ) a = (a_1,a_2,\dots,a_k) of 2019 2019 , construct a tree on the 2020 2020 vertices in which a d a_d of the vertices are distance d d from the root for 1 d k 1 \leq d \leq 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 d + 1 to a vertex at distance d d . The number of ways to assign distances is simply the multinomial 2019 ! a 1 ! a 2 ! a k ! . \frac {2019!}{a_1! a_2! \cdots a_k!}. Since each of the a d + 1 a_{d + 1} vertices at distance d + 1 d + 1 is connected to exactly one of the a d a_d vertices at distance d d , the number of ways to make the connections is a 1 a 2 a 2 a 3 a k 1 a k . a_1^{a_2} a_2^{a_3} \cdots a_{k - 1}^{a_k}. Therefore, the composition a = ( a 1 , a 2 , a k ) a = (a_1, a_2 \dots,a_k) corresponds to 2019 ! a 1 a 2 a 2 a 3 a k 1 a k a 1 ! a 2 ! a k ! 2019! \cdot \frac {a_1^{a_2} a_2^{a_3} \cdots a_{k - 1}^{a_k}} {a_1! a_2! \cdots a_k!} distinct labeled trees. By summing this expression over all a S a \in S , we enumerate all trees that can be constructed on 2020 2020 vertices except the star tree in which all 2019 2019 non-root vertices are connected to the root at distance 1. There are 202 0 2018 2020^{2018} distinct trees on 2020 2020 labeled vertices. When we exclude the star tree, our argument shows a S 2019 ! a 1 a 2 a k 1 a k a 1 ! a k ! = 202 0 2018 1 a S V ( a ) = 202 0 2018 1 2019 ! . \sum_{a \in S} 2019! \cdot \frac {a_1^{a_2} \cdots a_{k - 1}^{a_k}} {a_1! \cdots a_k!} = 2020^{2018} - 1 \implies \sum_{a \in S} V(a) = \frac {2020^{2018} - 1}{2019!}. Accordingly, we must compute the last three digits of m + n = 202 0 2018 1 d + 2019 ! d , m + n = \frac {2020^{2018} - 1}d + \frac {2019!}d, where d = gcd ( 202 0 2018 1 , 2019 ! ) = 4080399 d = \gcd(2020^{2018} - 1, 2019!) = 4080399 . Notice that 202 0 2018 1 999 , 1 4080399 599 , 2019 ! 0 ( m o d 1000 ) . 2020^{2018} - 1 \equiv 999, \quad \frac 1{4080399} \equiv 599, \quad 2019! \equiv 0 \pmod{1000}. These congruences imply 202 0 2018 1 d + 2019 ! d 999 × 599 + 0 401 ( m o d 1000 ) . \frac{2020^{2018} - 1}d + \frac {2019!}d \equiv 999 \times 599 + 0 \equiv 401 \pmod{1000}. Therefore, the last three digits of m + n m + n are 401 \boxed{401} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...