[07a] A Mad Tea-Party // alt. Problem Solving: Free Lunch (yes, please!)

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.

[06a] Pig and Pepper

peph8 = Pig
cs-tah = Pepper

I'm kinda drawing tablet-less, so I can't make ugly pictures to fill up the void that is my SLoG... so text is all you'll be getting. :(

I'm slightly confused at the moment. Are we allowed to upload one problem-solving question as a pair? peph8 and I both worked on that Paper Folding problem together (http://peph8.blogspot.ca/2013/01/paper-folding-creases.html), but if we each need our own posted solutions, I could go and quickly type up the solution to a different problem we've solved.

Here's hoping marks won't be docked for asking this super late.

I suppose the best solution would be to just post another solution right now, so I'll go work on typing up the solution to the Free Lunch problem, I guess.

Just a few more weeks until the final exam.
What a joyous occasion.

[05a] Advice from a Caterpillar

The caterpillar tells me I've been neglecting this SLoG as of late and I should get around to fluffing it up into the beautiful piece of work it should be.

Where do I start? Oh, yes -- Big-O.

Tutorials have been very helpful in keeping me up-to-date and on-the-ball with course work and topics. I find how we take up the questions in-tutorial is very thorough and useful to me. I'll admit I've been slacking off during lectures lately, but the tutorials always seem to get me back on track.

There are definitely some things I'll just have to commit to memory, such as the definition of O and Ω, and then there are just some steps I'll have to practice over and over again until I get a hang of things. Though it's kind of late, I'm happy I've managed to get used to proof structures and am careful to make sure I don't mess up my negations like I did on the second midterm. Lost 5 marks on the second question, I think. Ouch.

Well, off to my tutorial I go. I'll draw a picture after I get back!