Maths Olympiad Prep

Library / /10 of 22

Number theory Difficulty 5.1 AIME, harder Find the answer Italy

Problem:

Caboyara, a famous Australian circus performer, once again this year performs a great trick. He sets up a spectacular staircase with N=p1p2p2015N = p_{1} \cdot p_{2} \cdot \ldots \cdot p_{2015} steps, where p1,p2,,p2015p_{1}, p_{2}, \ldots, p_{2015} are distinct prime numbers; the steps corresponding to divisors of NN (including the first and the NN-th step) are special and are initially lit up green.
During the show, 2015 trained kangaroos climb the staircase one after another; for i=1,2,,2015i = 1, 2, \ldots, 2015, the ii-th kangaroo jumps pip_{i} steps at a time, starting from the foot of the staircase (it jumps onto step pip_{i}, then onto 2pi2 p_{i}, and so on until it reaches step NN). Every time a kangaroo jumps onto a special step, it changes color: from green it becomes red, from red it becomes green.
How many special steps will be lit up green at the end of the performance?

Pick one

Solution

Solution:

The answer is (B). Given the special step corresponding to the divisor dd of NN, the ii-th kangaroo will jump onto it if and only if the prime pip_{i} is a factor of dd; the light of the step will then change color as many times as the number of prime factors of dd: it will be green at the end of the performance if and only if dd has an even number of prime factors. On the other hand, for every divisor dd of NN with an odd number of prime factors, the divisor N/dN / d (which is different from dd, since NN is not a perfect square) has an even number of them, and vice versa: therefore the green lights will be exactly half of the divisors of NN. The total number of special steps (that is, of positive divisors of NN) is equal to the number of subsets of the set {p1,,p2015}\{p_{1}, \ldots, p_{2015}\}, that is 220152^{2015}. Therefore the final number of green lights will be 220142^{2014}.

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 translated into English from it; metadata (topic, difficulty) added by this project.