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.
Saturday, April 6, 2013
Friday, April 5, 2013
[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.
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.
Tuesday, April 2, 2013
[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!
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!
Monday, March 4, 2013
[04b] Factoring feat. peph8
 |
| Figuring out how to make something factor-able after many minutes and a ton of hints. |
[04a] The Rabbit Sends a Little Bill
I managed to sleep through the alarm for both Wednesday and Friday of last week, partially because of a math midterm on the Wednesday, and for no real apparent reason on the Friday. Maybe it was a sign that I was getting sick, since I have the flu now. Darn.
Anyway, onto CSC165-related material.
Began working on assignment 2 on Sunday and -- pardon the geeky statement: thank goodness for assignments. These assignments, in my opinion, really help me to understand the concepts taught over the weeks, since it really gives us some more practical experience. This also goes for tutorial handouts and quizzes, but I feel that it's much better in the form of an assignment, since you're given a lot more time to work on them, and you get to work with a partner (or two, if you're daring) to talk things out and ask questions.
On the other hand, I'm definitely going to have to read over several of the notes on proofs again, now that I understand more about them. Sometimes, the answer is staring me right in the eyes, but I just don't seem to notice them, such as how 15 can be rewritten as 11 + 4 if I need to factor something out. I'm sure this type of intuition will come more naturally with practice, though.
Time to figure out what to draw for this post!
Anyway, onto CSC165-related material.
Began working on assignment 2 on Sunday and -- pardon the geeky statement: thank goodness for assignments. These assignments, in my opinion, really help me to understand the concepts taught over the weeks, since it really gives us some more practical experience. This also goes for tutorial handouts and quizzes, but I feel that it's much better in the form of an assignment, since you're given a lot more time to work on them, and you get to work with a partner (or two, if you're daring) to talk things out and ask questions.
On the other hand, I'm definitely going to have to read over several of the notes on proofs again, now that I understand more about them. Sometimes, the answer is staring me right in the eyes, but I just don't seem to notice them, such as how 15 can be rewritten as 11 + 4 if I need to factor something out. I'm sure this type of intuition will come more naturally with practice, though.
Time to figure out what to draw for this post!
Tuesday, February 12, 2013
[03a] The Caucus Race and a Long Tale
I apologize for the long delay since my last post, but a bunch of things happened. Midterms, Chinese New Year... and these:
I hope you enjoyed the pretty pictures. I think my cellphone got hypothermia from taking these pictures.
Anyway, now that I have stuff to write about, it won't be so bad.
First off, proof outlines look like a lot of work, but I'm sure once I get used to how it's structured, it'll be a lot easier -- just tedious. I'm happy that someone I met in my tutorial knew a great deal more about equivalence laws than I did, and she managed to help me understand them better.
Assignment 1 marks came out recently, and I got a good grade, but I do wish it was 1% higher so that I would have a nice number to look at. Numbers ending with 9 make me sad. :(
The midterm.. definitely was not my best. I'm worried I might have translated the sentence in the last section incorrectly, and I know for sure that I got one part of question 2 wrong. If only I took CSC165 last year... I'd have preferred the previous year's test a lot more. Anyway, that's just me rambling.
Finally, thank goodness for Reading Week.
| The greatest thing to see in the morning. |
| "STOP" blinding me with snow. |
| I actually think this looked pretty. |
| The March of Impending Doom (or, NOOOO.. NOT THE CSC165H TEST ROOM...) |
I hope you enjoyed the pretty pictures. I think my cellphone got hypothermia from taking these pictures.
Anyway, now that I have stuff to write about, it won't be so bad.
First off, proof outlines look like a lot of work, but I'm sure once I get used to how it's structured, it'll be a lot easier -- just tedious. I'm happy that someone I met in my tutorial knew a great deal more about equivalence laws than I did, and she managed to help me understand them better.
Assignment 1 marks came out recently, and I got a good grade, but I do wish it was 1% higher so that I would have a nice number to look at. Numbers ending with 9 make me sad. :(
The midterm.. definitely was not my best. I'm worried I might have translated the sentence in the last section incorrectly, and I know for sure that I got one part of question 2 wrong. If only I took CSC165 last year... I'd have preferred the previous year's test a lot more. Anyway, that's just me rambling.
Finally, thank goodness for Reading Week.
Subscribe to:
Posts (Atom)