Maths Olympiad Prep

Track / Stage 6 / 99 of 400 #1739 of 2604

Problem 1739

National Olympiad, first round
Algebra Difficulty 6.1 Prove it Japan Mathematical Olympiad · Japan

Find the smallest integer n≥10n \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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

2519
Note that [x]>x−1[x] > x - 1 for any real number xx. In particular, for an integer 1≤k≤101 \le k \le 10 we have ⌊nk⌋>nk−1\lfloor \frac{n}{k} \rfloor > \frac{n}{k} - 1, thus k⌊nk⌋>n−kk \lfloor \frac{n}{k} \rfloor > n - k. Since both sides are integers, we have k⌊nk⌋≥n−k+1k \lfloor \frac{n}{k} \rfloor \ge n - k + 1, thus ⌊nk⌋≥n−k+1k\lfloor \frac{n}{k} \rfloor \ge \frac{n-k+1}{k}. Since 0<k≤n0 < k \le n implies n−k+1k>0\frac{n-k+1}{k} > 0, multiplying both sides of ⌊nk⌋≥n−k+1k\lfloor \frac{n}{k} \rfloor \ge \frac{n-k+1}{k} for k=1,2,…,10k = 1, 2, \dots, 10 yields
⌊n1⌋⌊n2⌋…⌊n10⌋≥n1⋅n−12…n−910=(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⌋=n−k+1k\lfloor \frac{n}{k} \rfloor = \frac{n-k+1}{k} for all integers 1≤k≤101 \le k \le 10.
If ⌊nk⌋=n−k+1k\lfloor \frac{n}{k} \rfloor = \frac{n-k+1}{k} holds, kk divides n−k+1n-k+1 because the right side is an integer. Conversely, if kk divides n−k+1n-k+1 then ⌊nk⌋=⌊n−k+1k⌋+k−1k=n−k+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⌋=n−k+1k\lfloor \frac{n}{k} \rfloor = \frac{n-k+1}{k} holds if and only if kk divides n−k+1n-k+1, that is, n+1n+1 is a multiple of kk.
Therefore, for an integer n≥10n \ge 10, the equation in the problem holds if and only if n+1n+1 is a multiple of kk for any integer 1≤k≤101 \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 2520−1=25192520 - 1 = 2519.

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