Problem Solving Post

PROBLEM:
You are part of a group of friends who choose which to treat to lunch in the following manner:

1. They arrange themselves in an (approximate) circle.
2. They begin reciting the positive natural numbers, in order, in a counter-clockwise direction (viewed from above), starting with the friend at the northern extreme of the circle (who utters "one").
3. As a friend utters an even number, he or she is eliminated from the counting (and consideration for lunch). The counting "wraps around" so that those who avoided one of the dreaded even numbers on the first round may be
exposed on subsequent rounds.
4. The last person left is treated to lunch.

For example, if there are friends f1, f2, f3, f4, and f5 arranged
counter-clockwise, with f1 at the northern extreme, the first round would
eliminate f2 and f4. Then f1 and f5 would be eliminated in the next round,
leaving f3 to enjoy the free lunch.

If there are n friends, where should you position yourself to get the free
lunch? Do you have a technique that will work for any positive natural number n?

1. Understanding the Problem:

This problem strives to find some kind of equation to model the last person in a circle to say an even number. The condition is that all friends must say the successive positive integer, beginning with one.

It is possible to satisfy the condition, so long as the number of friends is a finite amount. Eventually, there will only be two people remaining, and then it is certain that one person will remain who has not spoken a positive integer.

2. Devising a Plan:

To solve this problem, I'd like to take a look at the winning positions for a finite, small number of friends that will be easy to calculate. My intuition tells me that the solution will be an equation based on the number 2, likely 2 raised to a certain number. This is related to the use of even numbers. In the first round, each person with an even number will be eliminated. Subsequent reshuffling of the remaining players will eventually lead to the winner.

3. Carrying Out the Plan:

First, let's analyze some empirical data:
Column A = Number of friends in circle
Column B = Position of winning friend

A B
1 None (person has to pay for themselves)
2 f1

3 f3

4 f1

5 f3

6 f5

7 f7

8 f1

9 f3

10 f5

11 f7

12 f9

13 f11

14 f13

15 f15

16 f1

17 f3

18 f5

19 f7

20 f9

Notice that the first person wins in cases where the number of friends equal 2, 4, 8, 16, all of which are exponents of 2. The second person can never win, obviously, because they have to be the first person to state an even number, since they directly follow one. In fact, an even player will never win, which makes sense because any even number friend will be eliminated on the first go around. The third player wins on 3, 5, 9, 17, all of which are one greater than an exponent on 2 (compare with the values for f1). The fifth player wins on 6, 10, 18, which are one more than f3, except for 3 but f5 cannot win with 4 friends, since f5 is not in the group at that point. The seventh friend wins on 7, 11 and 19, which, again, are one more than the values for f5.

Now, a pattern begins to emerge. If the number of friends is an exponent of 2, then f1 will win the lunch. If it is one more than an exponent of 2, then f3 will win, If it is more two more than an exponent of 2, f5 will win; 3 moer, and f7 wins, and so on. So, to find the winning position, given n friends, find the closest exponent of 2 that is not greater than n, and stand at the position one greater than the difference between n and the cloest exponent of 2, since 0 = f1.

4. Looking Back

A formal proof for my solution could be done using induction, but a rigorous mathematical solution would first have to be contrived. A possible secondary solution could be made using modulous division, I think, but it would likely be more convoluted than the original. No other application of this solution comes to mind, although I certainly wouldn't rule any out, but would rather place the lack of ideas on my creative thinking limitations.