Library / /16 of 28

, 2024

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:

Compute the number of even positive integers $n \leq 2024$ such that $1,2, \ldots, n$ can be split into $\frac{n}{2}$ pairs, and the sum of the numbers in each pair is a multiple of $3$ .

Solution

Solution:

There have to be an even number of multiples of $3$ at most $n$ , so this means that $n \equiv 0,2 \pmod{6}$ . (We can also say that there should be an equal number of $1 \pmod{3}$ and $2 \pmod{3}$ numbers, which gives the same restriction.)

We claim that all these work. We know there are an even number of multiples of $3$ , so we can pair them; then we can pair $3k+1$ and $3k+2$ for all $k$ .

This means the answer is $\frac{2022}{3} + 1 = 675$ .

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.