See all of puzzle
, there are 4 more in this node.
Thu Sep 19 2002 at 3:40:43
Answers to some of
way to figure this out using
. The way I actually did it, however, was just to test it out and look for a pattern. I'll
which bulbs are
1 2 3 4 5 ... 100
1 3 5 7 9 ... 99
1 5 6 7 10 12 13 17 18 ...
1 4 5 6 7 8 10 13 17 18 ...
1 4 6 7 8 13 15 17 18 ...
1 4 7 8 12 13 15 17 ...
1 4 8 12 13 14 15 17 ...
1 4 12 13 14 15 16 17 ...
1 4 9 12 13 14 15 16 17 18...
1, 4, and 9 will be on at the end. 2, 3, 5, 6, 7, and 8 will not. You could keep on going; it will probably be even more
after you reach 25. The square numbers (and 1) are left on.
way: Consider a
. Which frogs will toggle k? All the frogs whose number is a factor of k. Since every lightbulb starts in the off position, only numbers with an odd number of factors will be on after all frogs have
. Which numbers have an odd number of factors? From
, only perfect squares have an odd number of factors. Well, and the number 1, of course.
This is a standard "enumerate every possibility" puzzle. There are two liars and one truth teller. Try each possible man as the truth teller, and look for a contradiction. Return the first guess that doesn't reach a contradiction.
Guess 1: George is telling the truth.
George's true statement -> Al didn't win.
Al's false statement -> one of Al or George won.
Ralph's false statement -> neither George nor Al won.
Contradiction: (one of Al or George won) and (neither George nor Al won) can not both be true.
Guess 2: Al is telling the truth
George false -> Al won.
Al true -> Neither Al nor George won.
Guess 3: Ralph is telling the truth
George false -> Al won.
Al false -> Al or George won.
Ralph true -> George or Al won.
No contradiction. Ralph must be telling the truth.
Since the third set of events is the correct guess, we determine who won the election from the implications of that guess. Therefore Al won.
's (I assume efficient means minimizing trips up and down the tower to retreive dropped balls):
Drop a ball every square_root(n) floors until it breaks, and then try every floor sequentially from the next lowest multiple of square_root(n) until the second ball breaks.
Worst case here will be 2*square_root(n) trips up and down the tower, and O(square_root(n)) trips in the average case.
's solution was n/3 and O(n/3) for the worst case and average case, respectively. This seems pretty
, but I haven't
d that it's the most efficient. I've also left out the
about having to go up and down the tower only every two times when you still have both balls, but this will just be something like a factor of (2/3) (square_root solution) or (1/2) (3 floors solution), and does not effect the
I like it!
Skipping the final
The Drunk Guy on a Cliff Puzzle
Two Envelope Paradox
Babel Fish puzzle
The Missing Dollar
Monks with blue spots puzzle
Life as a Puzzle
World Puzzle Championship
MIT Mystery Hunt
That Time Zeph Wet Herself
The Right To Be Offensive
Does back pain mean a disc?
Lady Jane Grey
Thanks from our Hearts
Hurry up please it's time
Everything Quests: Albums and CDs
Down and Out in Gotham City
Out of the Woods
List of Successful Cavalry Charges in the US Civil War
I made this cloak
Everything2 ™ is brought to you by Everything2 Media, LLC. All content copyright © original author unless stated otherwise.