Maths Olympiad Prep

Library / /281 of 520

Combinatorics Difficulty 7.0 National olympiad Prove it

Prove that there exist at least 100!100! ways to write 100!100! as sum of elements of set {1!,2!,3!...99!1!,2!,3!...99!}
(each number in sum can be two or more times)

Solution

1. Generalization and Induction Hypothesis:
We generalize the problem by replacing 100100 with n3n \geq 3. We aim to prove the statement by induction on nn, starting with the base case n=4n=4.

2. Induction Step:
Assume the statement is true for some n1n-1, i.e., there exist at least (n1)!(n-1)! ways to write (n1)!(n-1)! as a sum of elements from the set {1!,2!,,(n1)!}\{1!, 2!, \ldots, (n-1)!\}.

3. **Expanding n!n! with ii (n1)!(n-1)!'s:**
For any nonnegative integer in1i \leq n-1, consider the number of ways to expand n!n! as a sum of elements from {1!,2!,,n!}\{1!, 2!, \ldots, n!\} with exactly ii (n1)!(n-1)!'s. After removing ii (n1)!(n-1)!'s, the remaining sum is:
n!i(n1)!=(ni)(n1)! n! - i \cdot (n-1)! = (n-i)(n-1)!
By the induction hypothesis, there are at least (n1)!(n-1)! ways to expand (ni)(n1)!(n-i)(n-1)! using elements from {1!,2!,,(n1)!}\{1!, 2!, \ldots, (n-1)!\}.

4. Counting the Total Number of Ways:
Since we have nn cases (one for each ii from 00 to n1n-1), and each case has more than (n1)!(n-1)! ways, the total number of ways to write n!n! as a sum of elements from {1!,2!,,n!}\{1!, 2!, \ldots, n!\} is:
n(n1)!>n! n \cdot (n-1)! > n!
This completes the induction step.

5. **Base Case n=4n=4:**
We manually verify the base case for n=4n=4:
- If there are no 3!3!, then we have 4!4! ways.
- If there is one 3!3!, then we have 3!3! ways.
- If there are two 3!3!'s, then we have 2!2! ways.
- If there are three 3!3!'s, then we have 1!1! ways.
- If there are four 3!3!'s, then we have 0!0! ways.

Summing these, we get:
4!+3!+2!+1!+0!=24+6+2+1+1=34>4! 4! + 3! + 2! + 1! + 0! = 24 + 6 + 2 + 1 + 1 = 34 > 4!
Thus, the base case holds.

By induction, we have shown that there exist at least 100!100! ways to write 100!100! as a sum of elements from the set {1!,2!,,99!}\{1!, 2!, \ldots, 99!\}.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.