Skip to main content
OlympiadHQ

Browse · MathNet

Print

Mathematica competitions in Croatia

Croatia number theory

Problem

On the playground there are athletes with the numbers from to 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 to 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 ?
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 can be grouped into two element sets , unless for some positive integer when . 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 the squares are (because and ). At the end, there are athletes crouching.
Final answer
44

Techniques

τ (number of divisors)Factorization techniques