Maths Olympiad Prep

Library / Tajland /6 of 7

Tajland, 2014

Number theory Difficulty 7.0 National Olympiad Prove it Thailand

Let nn be a positive integer. We want to make up a collection of cards with the following properties:
* each card has a number of the form m!m! written on it, where mm is a positive integer;
* for any positive integer t≤n!t \le n!, we can select some card(s) from this collection such that the sum of the number(s) on the selected card(s) is tt.
Determine the smallest possible number of cards needed in this collection.

Solution

We need at least n(n−1)2+1\frac{n(n-1)}{2} + 1 cards.

For example, we can have ii cards with number i!i! for each i=1,2,…,n−1i = 1, 2, \dots, n-1 and another card with number n!n!. For t=n!t = n!, we can simply choose the card with number n!n!. Suppose that 1≤t<n!1 \le t < n!. Let r0=tr_0 = t, and for i=1,2,…,n−1i = 1, 2, \dots, n-1, define integers qiq_i and rir_i inductively, using the division algorithm:
ri−1=qi(n−i)!+ri,0≤ri<(n−i)!. r_{i-1} = q_i(n-i)! + r_i, \quad 0 \le r_i < (n-i)!.
Then t=∑i=1n−1qi(n−i)!t = \sum_{i=1}^{n-1} q_i(n-i)!. Since ri−1<(n−i+1)!r_{i-1} < (n-i+1)!, we have that qi≤n−iq_i \le n-i. Thus, we can choose qiq_i cards with number (n−i)!(n-i)! for each i=1,2,…,n−1i = 1, 2, \dots, n-1 so that the sum of the numbers is tt. So the required properties are satisfied.

Next, consider the smallest set of cards we can make with numbers adding up to n!−1n! - 1. Clearly, this set cannot contain any card with number greater than (n−1)!(n-1)!. For each i=1,2,…,n−1i = 1, 2, \dots, n-1, let cic_i be the number of cards with number i!i! in this set. Then ci≤ic_i \le i for all ii, for if ci≥i+1c_i \ge i+1 then we can replace i+1i+1 cards with number i!i!

in this set with just one card with number (i+1)!(i + 1)!, contradicting the minimality of the set. So now we have that
n!−1=∑i=1n−1cii!≤∑i=1n−1i(i!)=∑i=1n−1((i+1)!−i!)=n!−1. n! - 1 = \sum_{i=1}^{n-1} c_i i! \le \sum_{i=1}^{n-1} i(i!) = \sum_{i=1}^{n-1} ((i + 1)! - i!) = n! - 1.
This implies that all inequalities involved must be equality; that is, ci=ic_i = i for all ii. Thus, this set has 1+2+⋯+(n−1)=n(n−1)21 + 2 + \dots + (n - 1) = \frac{n(n-1)}{2} cards.

Suppose now that we have a collection of cards with the required properties. Then some of these cards have numbers adding up to n!−1n! - 1. So by what we have just shown, this collection must contain at least n(n−1)2\frac{n(n-1)}{2} cards. However, if we have exactly n(n−1)2\frac{n(n-1)}{2} cards, then we must select all these cards for the sum of the numbers to be n!−1n! - 1, but this means that we cannot select cards for the sum of the numbers to be n!n!, a contradiction. Therefore we need at least n(n−1)2+1\frac{n(n-1)}{2} + 1 cards. □\square

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.