Maths Olympiad Prep

Library / /10 of 11

Combinatorics Difficulty 6.5 National Olympiad Prove it Singapore

One hundred balls labelled 11 to 100100 are to be put into two identical boxes so that each box contains at least one ball and the greatest common divisor of the product of the labels of all the balls in one box and the product of the labels of all the balls in the other box is 11. Determine the number of ways that this can be done.

Solution

First let's assume the two boxes are different. The balls labelled 11 and 22 can be put into either box. All balls with even labels must then be put into the same box that the ball labelled 22 goes. Thus any ball with label which has a common factor greater than 11 with any one of those even labels must be put into the same box too. Therefore, we only need to consider those balls with labels greater than 5050. That leaves with 1010 balls labelled by the primes: 5353, 5959, 6161, 6767, 7171, 7373, 7979, 8383, 8989, 9797. Thus we have twelve entities, namely the ten prime numbers, the number 11 and all the balls that must go with 22. Each can be put into any of the two boxes. Taking away the 22 cases where one of the boxes is empty, the number of ways is 2122=40942^{12} - 2 = 4094. Since the two boxes are identical, we need to divide this number by 22. Therefore the answer is 20472047.

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.