Problem:
A frog is placed at the origin on the number line, and moves according to the following rule: in a given move, the frog advances to either the closest point with a greater integer coordinate that is a multiple of , or to the closest point with a greater integer coordinate that is a multiple of . A move sequence is a sequence of coordinates which correspond to valid moves, beginning with , and ending with . For example, is a move sequence. How many move sequences are possible for the frog?
Solution:
The set of move sequences can be partitioned into two subsets, namely the set of move sequences that contain , and the set of move sequences that do not contain . If a move sequence does not contain , then it must contain the subsequence . To count the number of such sequences, note that there are six ways for the frog to get to (five ways that go through , and one way that does not go through ), and there are four ways for the frog to get from to , since any of can be the second to last element of a move sequence. Thus there are move sequences that do not contain . If a move sequence contains , then it either contains or it does not. If such a move sequence does not contain , then it must contain the subsequence , and in this case, there is one way for the frog to get from to , and there are ways for it to get from to . If a move sequence contains and , then there are five ways for the frog to get from to , and there are are five ways for it to get from to . Thus there are ways for the frog to get from to , and there are five ways for the frog to get from to , for a total of move sequences that contain . Thus there are a total of move sequences for the frog.
There are five sequences from to , five from to , and five from to . There are four sequences from to not containing and four sequences from to not containing . Finally, there are four sequences from to containing neither nor . Thus there are sequences in all.
The problems on this page are the property of the MAA's American Mathematics Competitions