Problem:
There is a set of switches, each of which has four positions, called , and . When the position of any switch changes, it is only from to , from to , from to , or from to . Initially each switch is in position . The switches are labeled with the different integers , where , and take on the values . At step of a -step process, the th switch is advanced one step, and so are all the other switches whose labels divide the label on the th switch. After step has been completed, how many switches will be in position
Solution:
A switch will finish in position if and only if it has been advanced times for some integer . Each advance of a given switch corresponds to a multiple of its label. Let be the set of integers , where , and take on the values , . Notice that has multiples in . Thus the answer to the problem is the number of triples for which is divisible by . There are two cases in which is not divisible by . If all three factors of are odd, the product will also be odd; this occurs times. If two of the factors are odd and the third is , or , the product will be even but not divisible by; this occurs times. In all, there are triples for which is not divisible by . Therefore after step , the number of switches in position will be .
The problems on this page are the property of the MAA's American Mathematics Competitions