Monday Math Madness #4: The tradition continues!
09 Apr 2008 Quan Quach 24 comments 6973 views
Photo from jarkko
The Contest Problem
Daniel: Hey Quan, we just received a shipment of 25 Macbook Pros from Apple Inc.
Quan: WOWIE PAZOWIE! What are we going to do with 25 Macbook Pros?
Daniel: Let’s keep 3 of them for personal use and give the other 22 away to the winner of this contest.
Quan: Okay. But personally, I think the winner would rather prefer a 10 dollar GC to amazon.
Daniel: You’re probably right. In that case, we’ll just take a sledgehammer and smash the other 22 laptops to oblivion. Anyhow, since all Macbook Pros are not created equally, let’s determine which 3 Macbook Pros are the fastest. Those are the one’s that we’ll keep.
Quan: Good idea. We can go to the computer lab and run a simple test.
Daniel: Right. We can hook them up to the blinkdagger station and have each laptop process a special algorithm that I developed in MATLAB.
Quan: But we can only hook up 5 Macbook Pros at one time. And the station only ranks the 5 laptops from 1 (fastest) to 5 (slowest). It doesn’t give us any other information. This could potentially take forever!
Daniel: Don’t worry Quan. The optimal strategy will only take ______ iterations.
How many iterations do Quan and Daniel have to run to determine which 3 Macbooks are the fastest?
The Rules
-
The winner will receive their choice of a 10 dollar gift certificate to Amazon.com or this spiffy Rubik’s Cube (the cube is only available to US participants).
-
Email your answers to mondaymathmadness at gmail dot com.
-
Only one entry per person.
-
Inelgible for any one person to win more than once per year. But you should still submit your answer!
-
Answer must be explained. You must show your work! We will be the final judge on whether an answer was properly explained or not.
-
The deadline to submit answers is April 21st 2008, Tuesday 12:00 AM Pacific Standard Time
-
The winner will be chosen randomly from all the submittals using a random number generator.
-
The winner will be announced at 9:00 AM PST April 25th, 2008.
-
Comments for this post should only be used to clarify the problem. Please do not discuss ANY potential solutions.
-
Please spread the word about our contest! We’re aiming for 50 submissions for this contest. If we meet 50, we will announce two winners! So please stumble this post or advertise by word of mouth!
Hi Guys..
I is ok to assume that each macbook pro has a unique speed such that no two coms have the same speed?
PS.. Smashing up macbook is really a waste! I am in need of a new notebook i prefer that as a prize over the $10 gift voucher
Kompressor smash your Macbook!
So what would be considered an “iteration”. If I tested all 25 laptops (5 at a time), is that one single iteration? Or five of them?
Octopus,
Each time you test a group of 5 computers, that is considered 1 iteration. Hope that clears it up!
Quan
Hey, How do I submit an answer?
Rule #2) Email your answers to mondaymathmadness at gmail dot com.
Answer must be explained. You must show your work! We will be the final judge on whether an answer was properly explained or not.
For this problem, are we to explain why our algorithm correctly produces the three fastest machines, or are we (also) to explain why no other algorithm could do so in fewer steps?
TwoPi,
Just explain how you arrived at your answer. You do not need to prove why no other algorithm could do so in fewer steps.
Quan
well this is my first submission (and first comment post :O)
One hand has fingers crossed hoping my answer is right
The other hand’s fingers are crossed hoping that I’ll win if I’m right
XD
btw, If I win I want a rubric’s cube
<3 blinkdagger
i was at school today thinking about this, but i mis-remembered the problem, and thought that we had to order all 25 laptops from slowest to fastest. um, can we say “way harder problem?”
Hmm. Stumbled across the site, figured I’d enter.
I’m probably wrong because I used pencil and paper and devised my own, possibly inefficient, algorithm. The answer was low enough, however, that I figured I may have been right or close.
stumbled on as well,
I figured, what the heck, I’ll try it. Though I probably entirely missed the problem because it seems to simple…
[…] at random times during the day and evening, I couldn’t help but get addicted to working on Blinkdagger’s Monday Math Madness problem. I think I found a solution, but the great (and cruel) thing about optimization problems is that […]
Ok, solution submitted! Do we get an acknowledgement? I tend not to trust email delivery… Best of British to the rest of you!
yea i got mine acknowledgement.
I didn’t get an acknowledgement.
We will acknowledge all the people who answered the problem correctly next friday!
stumbled upon and figured i might enter.
not sure if my answer is right, seemed a bit too easy.
I’ve submitted my solution, i think it’s wrong, anyway could you tell us if the answer is below ..5? or 10?
But, folks, isn’t it all about a quick sorter? But with the extension to compare not only 2 but 5 items at a time.
Faaabio: I think it’s easy to reason that the answer is >= 5. You’d need to run each laptop through the Blinkdagger at least once. I don’t think I’ll ruin anyone’s fun by positing an upper bound.
Nurpsi: The problem is quite different from sorting. I believe it can be solved without having any idea of the relative ordering of the machines below the top three. In fact, the question is worded such that you don’t even need to know the relative ordering of the top three.
It’s an interesting question however: What’s the minimum number of runs required to sort all the machines? Answer that, and you’d get Faaabio’s upper bound…
[…] 23, 2008 · No Comments This week’s Monday Math Madness was a bit of a brain strainer. I didn’t get the ideal solution, but hey, whatever. I still […]
[…] Monday Mac Madness was the most successful contest we have conducted to date. In total, we received 103 submissions, which is twice as many as our original goal of 50. And since we received more than 50 submissions, we chose two winners for this contest! […]
six iterations