Maths Olympiad Prep

Library / /86 of 101

Number theory Difficulty 7.3 National olympiad, round 2 Prove it Estonia

All integers from 11 to 1212 are written on the edges of a cube so that every edge has exactly one integer. Two robot ants stand in the same vertex of the cube and wish to arrive at the vertex that is furthest away from them. Each ant picks a path consisting of exactly three edges of the cube. They multiply the integers on their path. The product of the integers on the path of the first ant is divisible by 100100, but not by 200200. The sum of the digits of the product of the integers on the path of the second ant is 22 and the integer 11 is not on its path. Find all possible products that either ant can get.

Solution

Since 100100 is divisible by 525^2, but none of the numbers on the edges of the cube are divisible by 525^2, the path of the first ant has to contain two numbers that are divisible by 55. The only two such numbers are 55 and 1010. Their product is divisible by 22, but not by 222^2. Since 100=2252100 = 2^2 \cdot 5^2, the third number on the path of the first ant has to be divisible by 22 but not by 222^2. The numbers on the edges of the cube that are divisible by 22, but not by 222^2, are 22, 66 and 1010. Since 1010 has already been used, the third number on the path of the first ant has to be either 22 or 66.

For the sum of the digits of the product of the second ant to be 22, it has to consist of either one two or two ones, in addition to any number of zeroes. Since the product of the three largest numbers on the edges of the cube is 121110=132012 \cdot 11 \cdot 10 = 1320, the possible products for the second ant are 22, 1111, 2020, 101101, 110110, 200200, 10011001, 10101010 and 11001100. Of these 22, 1111 and 101101 are prime numbers and cannot be the product of three integers that are larger than 11. The number 2020 can also be eliminated, since the only way to write it as a product of three integers larger than one is 2252 \cdot 2 \cdot 5, which includes the number 22 twice. The numbers 10011001 and 10101010 can be eliminated, since 1001=711131001 = 7 \cdot 11 \cdot 13 and there is no 1313 on the edges of the cube, and 1010=251011010 = 2 \cdot 5 \cdot 101 and there is no 101101 on the edges of the cube. This leaves 110110, 200200 and 11001100.

Now note that 200200 and 11001100 are both divisible by 525^2. To get these products, there have to be two numbers on the path of the second ant that are divisible by 55. The only such numbers are 55 and 1010. Hence we can eliminate 11001100, since to get this product the third number would have to be 2222, which is not on the cube. To get the product 200200, the numbers should be 55, 1010 and 44. To get the product 110110 the numbers should be 22, 55 and 1111.

However, the paths of the two ants can have either 00, 11 or 33 edges in common, but not exactly 22 edges. Hence the numbers on the path of the second ant cannot be 55, 1010 and 44, and so the numbers on the path of the second ant have to be 22, 55 and 1111. This leaves the first ant with the numbers 55, 66 and 1010, which give a product of 300300.

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.