Maths Olympiad Prep

Library / /219 of 348

Number theory Difficulty 5.0 AIME Find the answer

A positive integer nn is magical if n=n\lfloor\sqrt{\lceil\sqrt{n}\rceil}\rfloor=\lceil\sqrt{\lfloor\sqrt{n}\rfloor}\rceil where \lfloor\cdot\rfloor and \lceil\cdot\rceil represent the floor and ceiling function respectively. Find the number of magical integers between 1 and 10,000, inclusive.

A number or a short expression. Spacing and $ signs are ignored.

Solution

First of all, we have n=n\lfloor\sqrt{n}\rfloor=\lceil\sqrt{n}\rceil when nn is a perfect square and n=n1\lfloor\sqrt{n}\rfloor=\lceil\sqrt{n}\rceil-1 otherwise. Therefore, in the first case, the original equation holds if and only if n\sqrt{n} is a perfect square itself, i.e., nn is a fourth power. In the second case, we need m=nm=\lfloor\sqrt{n}\rfloor to satisfy the equation m+1=m\lfloor\sqrt{m+1}\rfloor=\lceil\sqrt{m}\rceil, which happens if and only if either mm or m+1m+1 is a perfect square k2k^{2}. Therefore, nn is magical if and only if (k21)2<n<(k2+1)2\left(k^{2}-1\right)^{2}<n<\left(k^{2}+1\right)^{2} for some (positive) integer kk. There are (k2+1)2(k21)2=4k21\left(k^{2}+1\right)^{2}-\left(k^{2}-1\right)^{2}=4 k^{2}-1 integers in this range. The range in the problem statement includes k=1,2,,9k=1,2, \ldots, 9 and the interval (992,1002]\left(99^{2}, 100^{2}\right], so the total number of magical numbers is 4(12+22++92)9+(1002992)=49(9+1)(18+1)6+190=13304\left(1^{2}+2^{2}+\cdots+9^{2}\right)-9+\left(100^{2}-99^{2}\right)=4 \cdot \frac{9 \cdot(9+1) \cdot(18+1)}{6}+190=1330

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.