Maths Olympiad Prep

Library / /29 of 31

Number theory Difficulty 6.6 National olympiad Prove it Estonia

Masha has an electric carouse in her garden that she rides every day. As she likes order, she always leaves the carouse in the same position after each ride. But every night three bears sneak into the garden and start turning the carouse. Bear dad turns the carouse each time by 17\frac{1}{7} of the full circle. Bear mum turns the carouse each time by 19\frac{1}{9} of the full circle. Bear cub turns the carouse each time by 132\frac{1}{32} of the full circle. Every bear can turn the carouse as many times as he or she wants. In how many different positions may Masha find the carouse in the morning?

Solutions — 2

Solution 1

As 7932=20167 \cdot 9 \cdot 32 = 2016, all turns are integral multiples of 12016\frac{1}{2016} of the full turn. Thus the carouse can be in at most 2016 distinct positions. It remains to show that all these positions are possible. For that, we show that the bears can turn the carouse by exactly 12016\frac{1}{2016} of the full turn. Then the same sequence of operations can be repeated to obtain also 22016,32016,,20162016\frac{2}{2016}, \frac{3}{2016}, \dots, \frac{2016}{2016} of the full turn. Exactly 12016\frac{1}{2016} of the full turn is obtained, for instance, if bear dad turns the carouse once in one direction and both bear mum and bear cub turn the carouse once in the opposite direction since 1719132=288224632016=12016\frac{1}{7} - \frac{1}{9} - \frac{1}{32} = \frac{288-224-63}{2016} = \frac{1}{2016}.

Solution 2

The carouse turns by an integral multiple of 17\frac{1}{7} of the full turn due to bear dad, an integral multiple of 19\frac{1}{9} of the full turn due to bear mum and an integral multiple of 132\frac{1}{32} of the full turn due to bear cub. As the result, the carouse turns by x7+y9+z32\frac{x}{7} + \frac{y}{9} + \frac{z}{32} of the full turn where x,y,zx, y, z are some integers. As x7+y9+z32=288x+224y+63z2016\frac{x}{7} + \frac{y}{9} + \frac{z}{32} = \frac{288x+224y+63z}{2016}, the carouse can be turned only by integral multiples of 12016\frac{1}{2016} of the full turn. As gcd(288,224,63)=gcd(932,732,79)=1\text{gcd}(288, 224, 63) = \text{gcd}(9 \cdot 32, 7 \cdot 32, 7 \cdot 9) = 1, there exist integral coefficients a,ba, b and cc such that a288+b224+c63=1a \cdot 288 + b \cdot 224 + c \cdot 63 = 1. Hence taking x=na,y=nbx = na, y = nb and z=ncz = nc for any integer nn, the carouse turns by exactly n2016\frac{n}{2016} of the full turn. Hence all integral multiples of 12016\frac{1}{2016} of the full turn are possible, i.e., the carouse can be left in 2016 distinct positions.

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.