Maths Olympiad Prep

Library / /257 of 520

Number theory Difficulty 5.2 AIME, harder Find the answer

Example 8 A positive integer, if it can be expressed as the difference of squares of two positive integers, is called a "wise number". Arrange all the wise numbers in ascending order. Find the wise number at the 2009th position.

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

Solution

Solution: Let nn be any positive integer.
When n=2k+1(kN+)n=2 k+1\left(k \in \mathbf{N}_{+}\right), we have n=2k+1=(k+1)2k2n=2 k+1=(k+1)^{2}-k^{2}.
Thus, every odd number greater than 1 is a wise number.
When n=4k(kN+,k2)n=4 k\left(k \in \mathbf{N}_{+}, k \geqslant 2\right), we have
n=4k=(k+1)2(k1)2 n=4 k=(k+1)^{2}-(k-1)^{2} \text {. }

Thus, every number greater than 4 and divisible by 4 is a wise number.
When n=4k2(kN+)n=4 k-2\left(k \in \mathbf{N}_{+}\right), let n=p2q2n=p^{2}-q^{2}.
Then 2(2k1)=(p+q)(pq)2(2 k-1)=(p+q)(p-q).
Thus, (p+q)(pq)(p+q)(p-q) is even.
Since p+qp+q and pqp-q have the same parity, both p+qp+q and pqp-q are even. Therefore, 4(p+q)(pq)4 \mid (p+q)(p-q). Hence, 42(2k1)4 \mid 2(2 k-1), which implies 2(2k1)2 \mid (2 k-1), a contradiction.

Therefore, every number of the form 4k2(kN+)4 k-2\left(k \in \mathbf{N}_{+}\right) is not a wise number.

If all wise numbers are arranged in ascending order and, except for the first wise number, the rest are grouped into sets of 3:
3,(5,7,8),(9,11,12), 3,(5,7,8),(9,11,12), \cdots

According to the above discussion, the last number in each set is a multiple of 4, so the kk-th set is
(4k+1,4k+3,4k+4) (4 k+1,4 k+3,4 k+4) \text {. }

Since 20091=3×669+12009-1=3 \times 669+1, the 2009th position in the sequence is the first number of the 670th set, which is 4×670+1=26814 \times 670+1=2681.

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