Maths Olympiad Prep

Library / /9 of 52

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it Romania

Given a square-free integer n3n \ge 3, evaluate the sum k=1(n2)(n1)kn3\sum_{k=1}^{(n-2)(n-1)} \lfloor \sqrt[3]{kn} \rfloor.

Solution

Let SS be the set of lattice points in the rectangle [1,(n2)(n1)]×[1,n1][1, (n-2)(n-1)] \times [1, n-1]. Since nn is square-free, no point of SS lies on the curve y=nx3y = \sqrt[3]{nx}, so the latter splits SS into two non-empty sets. The required sum counts the points of SS below the curve, while the sum k=1n1k3/n\sum_{k=1}^{n-1} \lfloor k^3/n \rfloor counts the points of SS above the curve. Since S=(n2)(n1)2|S| = (n-2)(n-1)^2, it is sufficient to evaluate the latter sum.

To this end, let tk=k3/nk3/nt_k = k^3/n - \lfloor k^3/n \rfloor, k=1,2,,n1k = 1, 2, \dots, n-1. Clearly, 0tk<10 \le t_k < 1 for all kk, and since nn is square-free, the tkt_k are, in fact, all positive. Since k3/n+(nk)3/n=3k23kn+n2k^3/n + (n-k)^3/n = 3k^2 - 3kn + n^2 is integral, so is tk+tnkt_k + t_{n-k}, and since 0<tk+tnk<20 < t_k + t_{n-k} < 2, it follows that tk+tnk=1t_k + t_{n-k} = 1. Hence
n1=k=1n1(tk+tnk)=2k=1n1tk=2k=1n1k3n2k=1n1k3n=n(n1)222k=1n1k3n. \begin{aligned} n-1 &= \sum_{k=1}^{n-1} (t_k + t_{n-k}) = 2 \sum_{k=1}^{n-1} t_k = 2 \sum_{k=1}^{n-1} \frac{k^3}{n} - 2 \sum_{k=1}^{n-1} \lfloor \frac{k^3}{n} \rfloor \\ &= \frac{n(n-1)^2}{2} - 2 \sum_{k=1}^{n-1} \lfloor \frac{k^3}{n} \rfloor. \end{aligned}
Consequently, k=1n1k3/n=(n2)(n21)/4\sum_{k=1}^{n-1} \lfloor k^3/n \rfloor = (n-2)(n^2-1)/4, and
k=1(n2)(n1)kn3=(n2)(n1)2(n2)(n21)/4=(n2)(n1)(3n5)/4. \sum_{k=1}^{(n-2)(n-1)} \lfloor \sqrt[3]{kn} \rfloor = (n-2)(n-1)^2 - (n-2)(n^2-1)/4 = (n-2)(n-1)(3n-5)/4.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.