Understand the 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 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?
This picture helps illustrate the problem. Basically, you don't want to ever say an even number.
Devise a Plan
Go through the first couple of natural n by hand and see if a patter emerges.
Carry out the Plan
n
|
Iterations
|
winner
|
1
|
F1
|
F1
|
2
|
F1 f2
|
F1
|
3
|
F1 f2 f3
F1 f3
|
F3
|
4
|
F1 f2 f3 f4
F1 f3
|
F1
|
5
|
F1 f2 f3 f4 f5
F1 f3 f5
|
F3
|
6
|
F1 f2 f3 f4 f5 f6
F1 f3 f5
F1 f5
|
F5
|
7
|
F1 f2 f3 f4 f5 f6
f7
F1 f3 f5 f7
F3 f5
|
F5
|
8
|
F1 f2 f3 f4 f5 f6
f7 f8
F1 f3 f5 f7
F1 f5
|
F1
|
9
|
F1 f2 f3 f4 f5 f6
f7 f8 f9
F1 f3 f5 f7 f9
F3 f7
|
F3
|
10
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10
F1 f3 f5 f7 f9
F1 f5 f9
F1 f9
|
F1
|
11
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11
F1 f3 f5 f7 f9
f11
F3 f7 f11
F3 f11
|
F3
|
12
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11 f12
F1 f3 f5 f7 f9 f11
F1 f5 f9
F1 f9
|
F1
|
Initial observations:
It’s pretty obvious that you don’t want to be an even numbered
friend. F1 wins all of the even numbered n except for 6. (Realized that I made
an error once I looked back)
Look Back
An obvious pattern has not revealed itself. I will take a look at another possible source of a patter: what number each of the people say.
n
|
Iterations
|
winner
|
1
|
F1
1
|
F1
|
2
|
F1 f2
1 2
|
F1
|
3
|
F1 f2 f3
F1 f3
4 5
|
F3
|
4
|
F1 f2 f3 f4
F1 f3
5 6
|
F1
|
5
|
F1 f2 f3 f4 f5
F1 f3 f5
6
7 8
|
F3
|
6
|
F1 f2 f3 f4 f5 f6
F1 f3 f5
7 8
9
F1 f5
10 11
|
F5
|
7
|
F1 f2 f3 f4 f5 f6
f7
F1 f3 f5 f7
8 9
10 11
F3 f7
12 13
|
F7
|
8
|
F1 f2 f3 f4 f5 f6
f7 f8
F1 f3 f5 f7
9 10 11 12
F1 f5
13 14
|
F1
|
9
|
F1 f2 f3 f4 f5 f6
f7 f8 f9
F1 f3 f5 f7 f9
10 11 12 13 14
F3 f7
15 16
|
F3
|
10
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10
F1 f3 f5 f7
f9
11 12 13 14 15
F1 f5 f9
16 17 18
F1 f9
19 20
|
F1
|
11
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11
F1 f3 f5
f7 f9 f11
12 13 14 15 16 17
F3 f7 f11
18 19 20
F3 f11
21 22
|
F3
|
12
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11 f12
F1 f3 f5 f7 f9 f11
13 14 15 16 17 18
F1 f5 f9
19 20 21
F1 f9
22 23
|
F9
|
Initial observations:
I actually made one error in finding out who won, so I should
really double check my work.
Winner
|
1
|
2
|
3
|
1
|
3
|
5
|
7
|
1
|
3
|
1
|
3
|
9
|
# said to win
|
1
|
1
|
5
|
5
|
7
|
11
|
13
|
13
|
15
|
19
|
21
|
23
|
Look Back
Still no obvious pattern. I am out of ideas at this point,
and will continue on later and look for more complex patterns.
No comments:
Post a Comment