Maths Olympiad Prep

Library / /237 of 377

Algebra Difficulty 5.2 AIME, harder Prove it United States

Problem:

Let x\lfloor x\rfloor denote the greatest integer less than or equal to xx. How many positive integers less than 20052005 can be expressed in the form xx\lfloor x\lfloor x\rfloor\rfloor for some positive real xx?

Solution

Solution:

Let {x}=xx\{x\} = x - \lfloor x\rfloor be the fractional part of xx. Note that
xx=(x+{x})x=x2+{x}x. \lfloor x\lfloor x\rfloor\rfloor = \lfloor (\lfloor x\rfloor + \{x\})\lfloor x\rfloor \rfloor = \lfloor x\rfloor^{2} + \lfloor \{x\}\lfloor x\rfloor \rfloor.
Because {x}\{x\} may take on any value in the half-open interval [0,1)[0,1), the quantity {x}x\lfloor \{x\}\lfloor x\rfloor \rfloor can take on any integer value between 00 and x1\lfloor x\rfloor - 1, inclusive.

If x=n\lfloor x\rfloor = n, then xx\lfloor x\lfloor x\rfloor\rfloor can be any of the numbers n2,n2+1,,n2+n1n^{2}, n^{2} + 1, \ldots, n^{2} + n - 1. In other words, there are precisely nn possible values that xx\lfloor x\lfloor x\rfloor\rfloor can take, and moreover, all of them are less than (n+1)2(n+1)^{2}.

Because 442+43=1979<200544^{2} + 43 = 1979 < 2005 and 452=2025>200545^{2} = 2025 > 2005, nn can range between 11 and 4444, inclusive. Therefore, the answer is
n=144n=44452=990 \sum_{n=1}^{44} n = \frac{44 \cdot 45}{2} = 990

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.