Here's mine and peph8's solution to the Free Lunch problem, since we would love free food. Who wouldn't?
We also worked on the Paper Folding problem together, and it can be found here:
http://peph8.blogspot.ca/2013/01/paper-folding-creases.html
Understanding the Problem
Unknown:
- What's the best position to be in to get a free, nice, hot lunch, for any given number of participants? (Or cold, if you like cold lunches.)
Given:
- Each participant must say the next natural number in ascending chronological order.
- Whoever says an even number doesn't get the free lunch. Sucks for them.
- The last person standing (or sitting, I guess) gets the free lunch. Yay!
[*] To stay on-theme, the winner gets to join the Mad Tea-Party. My best friend is the Dormouse.
Figure:
Oh no. No drawing tablet when I actually need it.
f1
f2 f5
f3 f4 (an example of the position of five participants)
Original: f1 f2 f3 f4 f5
Survivors of the First Round: f1 f3 f5
Survivor of the Second Round: f3
You go, f3!
Devising a Plan
Some brute forcing gives me this beautiful chart of ultimate beauty:
# of participants : winner
1 : f1
2 : f1
3 : f3
4 : f1
5 : f3
6 : f5
7 : f7
8 : f1
9 : f3
10 : f5
15 : f15
20 : f9
Observations:
- Even-numbered players never win, since they're eliminated after the first round. Don't be even -- be odd.
- f1 wins when there is 1 player, as well as when there are 2, 4, or 8 players.
- f3 wins when there are 3, 5, or 9 players.
- f5 wins when there are 6 or 10 players.
f1 seems to be very interesting, since f1 wins whenever the number of players is a power of 2... Weird.
There's also another pattern visible here, so it's time to start carrying out our plan for free food.
Carrying Out the Plan
1 = 2^0 participants = f1 is the winner.
2 = 2^1 participants = f1 is the winner.
3 = 2^1 + 1 = f3
4 = 2^2 = f1
5 = 2^2 + 1 = f3
6 = 2^2 + 2 = f5
7 = 2^2 + 3 = f7
8 = 2^3 = f1
9 = 2^3 + 1 = f3
10 = 2^3 + 2 = f5
11 = 2^3 + 3 = f7
12 = 2^3 + 4 = f9
13 = 2^3 + 5 = f11
14 = 2^3 + 6 = f13
15 = 2^3 + 7 = f15
16 = 2^4 = f1
So, it seems that we find the closest power of 2 that is no larger than n, and the best position there would be at f1. Counting onwards, you go to the next odd number, so at 2^x +1 (the closest power of 2 that is no larger than n + 1), you go to f3, then f5, then f7, and so on.
n - 2^x = [0, 1, 2, 3, ...]
In order to get the closest odd number (which is defined as "2k + 1"), you would have to use:
2(n - 2^x) + 1
Lost your lunch money? Just remember 2(n - 2^x) + 1.
Looking Back
The formula appears to work for any given value, and returns the expected result for every number tested so far.
Posting from my phone, so I have no idea if this will display me as peph8 or not.
ReplyDeleteWe tried to find a similar pattern with multiples of 3, but our results were pretty erratic. By that I mean '1, 2, 2, 1, 4, 1, 4, 7, 1, 4, 7, 10, 13, 2, 5'
And I have no idea what patterns arise from that. Aaahhhh. It's sort of sad, but then again, it's 1AM and my motivation is as high as a bear's while it's hibernating.