CSC236 SLOG #7

Here's the description of the question:

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 lunc.

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?

Dec 3

When I first saw the question, I thought it's easy. I started by experimenting with different number of people, and see who gets the free lunch in each case. Below is the result I got from experimenting:

# of ppl:  1  | 2  | 3  | 4   | 5  | 6  | 7  | 8   | 9  | 10 | 11 | 12 | 13  | 14  | 15   | 16 |

winner:   f1 | f1 | f3 | f1 | f3 | f5 | f7 | f1 | f3 | f5  | f7 |  f9 | f11 | f13 | f15 |  f1 |

In each experiment, I draw a circle that fits the number of people, and then start eliminating in a counter-clockwise direction by crossing out the people who utter even numbers.

After contemplating on the question for a period of time, I come to two lemmas:

1. Obviously, people start with even numbers will never get the free lunch, because they will be eliminate in the first round of counting.

2. When n equals an odd number, the first person will never get the free lunch except n = 1, because he/she will be eliminate in the second run.

And then, I realize I can expand the second lemma to say that when n equals an even number, the third person will never get the free lunch. 

Then I struggled to find some points to build on for about an hour, I decide to call it a day.

Dec 4

Today, I tried to solve the problem from another angle, and it was success. Instead of looking at the process of elimination, I tried to look at the winners as a sequence of numbers. Surprisingly, that clearly showed a sequence - occurrence of 2^a of orderly odd numbers as a starts from 0 and orderly odd numbers start at 1. The way I separate the winners in the following groups will show the sequence:

# of ppl 1: f1

# of ppl 2-3: f1, f3

# of ppl 4-7: f1, f3, f5, f7

# of ppl 8-15: f1, f3, f5, f7, f9, f11, f13, f15

...

After a bit of calculation I come up to this formula: (let cap(n) be the smallest power of 2 that is equal to or greater than n) winner = (cap(n+1)/2 - (cap(n+1) - 1 - n)) * 2 - 1 = 2n + 1 - cap(n+1)

But how can I prove the formula is right? Or can I come up of an explanation?

So I tried to make a prove by induction. By the nature of increasing number of people 1 at time, I believed that if induction works, mathematic induction is the right choice. 

The base case is easy: when there is one people, he/she is the only choice. But what about the inductive steps? There is no obvious sign of induction. So I started contemplating the numbers again.

Then I came up with one more clues:

Except when n=1, the last count being eliminated is always (n-1)*2.

And then I realized that if n results in a winner of 7, the winner of n+1 could be either 9 or 1. Up to here, I was stuck. I couldn't any process after that. So I decide to move my mind to other objects.

Dec 5

After a day of fresh air, I came back to the free-lunch problem.

I came up with a thought on subway. I can explain when exactly n will result in a winner of 1. It's actually quite easy to understand. When n is a power of 2, the winner will be 1. The reason is that in every round of elimination, because the number of people is a power of 2, the last number being eliminated will be the first number on the right side of 1, which makes 1 the first number in the next run and the count of 1 will be an odd number. So 1 will be left to the end.

So now we know what will happen if (n+1) is a power of 2. What happens if it's not a power of 2??

After half an hour of contemplating, I realize that the game will not end with a odd counting number, because the game ends when the second last number standing is eliminated and the counting has to be even. Following the logic, the counting before the last counting will be on the winner. Given that, if n people has a winner of x, then the winner of n+1 people will be the that number that counts next after x is eliminated, because the counting is shift up by 1. Given that even number cannot be the winner, the winner of n+1 will be x+2.

So when n+1 is a power of 2, the winner will be 1. If it's not power of 2, the winner will be 2n + 1 - cap(n+1) + 2 given that the winner of n people is 2n + 1 - cap(n+1)  # IH.

Let's see if it real works mathematically. 

when n+1 is a power of 2: 

cap((n+1)+1) = (n+1)*2, thus 2(n+1) + 1 - cap((n+1)+1) = 2n + 3 - 2*(n+1) = 1.

When n+1 is not a power of 2:

cap((n+1+1) = cap(n+1), thus 2(n+1) + 1 - cap((n+1)+1) = 2n + 3 - cap(n+1) = (2n + 1 - cap(n+1)) + 2.

Then, the formula holds in both cases.

Combine the base case and the inductive steps, we can conclude that when n people is playing, the (2n + 1 - cap(n+1))th person will get the free lunch.

Cheers, I have solved the problem finally!!!