Competition problem — Number theory

Library / /39 of 82

Number theory Difficulty 5.6 AIME, harder Prove it Croatia

On the playground there are $2014$ athletes with the numbers from $1$ to $2014$ on their shirts (each number is on exactly one shirt). At the beginning they are all standing. In certain time intervals the coach shouts out all positive integers from $1$ to $2014$ in the increasing order. All athletes having a multiple of the shouted number on their shirts change their position from the standing position to crouch and vice versa.
How many athletes are crouching after the coach shouts out the number $2014$ ?

Solution

Every athlete will change his position as many times as the number on his shirt has divisors. Hence, at the end in the position of crouch will be those athletes whose shirt numbers have an odd number of divisors.
All divisors of the number $n$ can be grouped into two element sets $\{d, \frac{n}{d}\}$ , unless $n = d^2$ for some positive integer $d$ when $\frac{n}{d} = d$ . That means that a positive integer has an odd number of divisors if and only if it is a square of an integer.
Among numbers $1, \ldots, 2014$ the squares are $1^2, 2^2, \ldots, 44^2$ (because $44^2 = 1936$ and $45^2 = 2025$ ). At the end, there are $44$ athletes crouching.

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 and solution reproduced as published; topic and difficulty added by this site.