Maths Olympiad Prep

Library / /7 of 63

Algebra Difficulty 6.1 National olympiad Prove it Japan

Find the smallest integer n10n \ge 10 such that
[n1][n2][n10]=(n10) \left[ \frac{n}{1} \right] \left[ \frac{n}{2} \right] \cdots \left[ \frac{n}{10} \right] = \binom{n}{10}
Here denote by [r][r] the largest integer less than or equal to rr for a real number rr. For example, [3.14]=3[3.14] = 3 and [5]=5[5] = 5.

Solution

2519
Note that [x]>x1[x] > x - 1 for any real number xx. In particular, for an integer 1k101 \le k \le 10 we have nk>nk1\lfloor \frac{n}{k} \rfloor > \frac{n}{k} - 1, thus knk>nkk \lfloor \frac{n}{k} \rfloor > n - k. Since both sides are integers, we have knknk+1k \lfloor \frac{n}{k} \rfloor \ge n - k + 1, thus nknk+1k\lfloor \frac{n}{k} \rfloor \ge \frac{n-k+1}{k}. Since 0<kn0 < k \le n implies nk+1k>0\frac{n-k+1}{k} > 0, multiplying both sides of nknk+1k\lfloor \frac{n}{k} \rfloor \ge \frac{n-k+1}{k} for k=1,2,,10k = 1, 2, \dots, 10 yields
n1n2n10n1n12n910=(n10). \lfloor \frac{n}{1} \rfloor \lfloor \frac{n}{2} \rfloor \dots \lfloor \frac{n}{10} \rfloor \ge \frac{n}{1} \cdot \frac{n-1}{2} \dots \frac{n-9}{10} = \binom{n}{10}.
Therefore the equation in the problem holds if and only if nk=nk+1k\lfloor \frac{n}{k} \rfloor = \frac{n-k+1}{k} for all integers 1k101 \le k \le 10.
If nk=nk+1k\lfloor \frac{n}{k} \rfloor = \frac{n-k+1}{k} holds, kk divides nk+1n-k+1 because the right side is an integer. Conversely, if kk divides nk+1n-k+1 then nk=nk+1k+k1k=nk+1k\lfloor \frac{n}{k} \rfloor = \lfloor \frac{n-k+1}{k} \rfloor + \frac{k-1}{k} = \frac{n-k+1}{k} holds. Therefore the equation nk=nk+1k\lfloor \frac{n}{k} \rfloor = \frac{n-k+1}{k} holds if and only if kk divides nk+1n-k+1, that is, n+1n+1 is a multiple of kk.
Therefore, for an integer n10n \ge 10, the equation in the problem holds if and only if n+1n+1 is a multiple of kk for any integer 1k101 \le k \le 10, that is, n+1n+1 is a common multiple of 1,2,,101, 2, \dots, 10. Since the least common multiple of 1,2,,101, 2, \dots, 10 is 2520, the smallest possible nn is 25201=25192520 - 1 = 2519.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.