Question P.176: Let n ≥ 3 be a positive integer. Begin with a circle with n ......
Let n ≥ 3 be a positive integer. Begin with a circle with n marks about it. Starting at a given point on the circle, move clockwise, skipping over the next two marks and placing a new mark; the circle now has n + 1 marks. Repeat the procedure beginning at the new mark. Must a mark eventually appear between each pair of the original marks?
To show why, suppose there is a pair m_1, m_2 of consecutive original marks such that no mark will ever appear between them. This implies that as you move around the circle, you always put a mark just before m_1, then skip over both m_1~and~m_2 and put the next mark right after m_2, as shown in the figure.
Now suppose that for some particular time around the circle, there are x marks in all as you skip m_1~and~m_2. On your next circuit (counting from that moment), you must again arrive just before m_1 in order to skip over m_1~and~m_2, so x must be even and you will be adding x/2 marks during this next circuit, for a total of 3x/2. However, not all integers in the sequence x,(3/2)x,(3/2)²x, . . . can be even. Thus on some circuit there will be an odd number of marks as you skip m_1~and~m_2, and on the next circuit a mark will appear between m_1~and~m_2, a contradiction.
