Maths Olympiad Prep

Library / /12 of 13

Algebra Difficulty 7.0 National olympiad, round 2 Prove it China

Given the set P={1,2,3,4,5}P = \{1, 2, 3, 4, 5\}, define f(m,k)=i=15mk+1i+1f(m, k) = \sum_{i=1}^{5} \lfloor m \sqrt{\frac{k+1}{i+1}} \rfloor for any kPk \in P and positive integer mm, where a\lfloor a \rfloor denotes the greatest integer less than or equal to aa. Prove that for any positive integer nn, there is kPk \in P and positive integer mm, such that f(m,k)=nf(m, k) = n.

Solution

Proof Define set A={mk+1mN,kP}A = \{m\sqrt{k+1} \mid m \in \mathbb{N}^*, k \in P\}, where N\mathbb{N}^* denotes the set of all positive integers. It is easy to check that for any k1,k2P,k1k2k_1, k_2 \in P, k_1 \neq k_2, k1+1k2+1\frac{\sqrt{k_1+1}}{\sqrt{k_2+1}} is an irrational number. Therefore, for any k1,k2Pk_1, k_2 \in P and positive integers m1,m2m_1, m_2, m1k1+1=m2k2+1m_1\sqrt{k_1+1} = m_2\sqrt{k_2+1} implies m1=m2m_1 = m_2 and k1=k2k_1 = k_2.

Note that AA is an infinite set. We arrange the elements in AA in ascending order. Then we have an infinite sequence. For any positive integer nn, suppose the nnth term of the sequence is mk+1m\sqrt{k+1}. Any term before the nnth can be written as mii+1m_i\sqrt{i+1}, and
mii+1mk+1. m_i \sqrt{i+1} \le m \sqrt{k+1}.
Or equivalently, mimk+1i+1m_i \le m \frac{\sqrt{k+1}}{\sqrt{i+1}}. It is easy to see that there are mk+1i+1\lfloor m \frac{\sqrt{k+1}}{\sqrt{i+1}} \rfloor such mim_i for i=1,2,3,4,5i = 1, 2, 3, 4, 5. Therefore,
n=i=15mk+1i+1=f(m,k). n = \sum_{i=1}^{5} \lfloor m \frac{\sqrt{k+1}}{\sqrt{i+1}} \rfloor = f(m, k).

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.