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
Merlin's Shop of Mystical Wonders
Merle's Magic Mug Shop
A trip to a minimalist restaurant
Operation Paul Bunyan
Filesystem performance tweaking with XFS on Linux
Playing With Fire
The orange chair
It's only temporary unless it works
One of the dangers of necromancy is you don't really know who's on the other side or what they're going to give you in return.
black magic again
hypertension: The 2017 Clinical Guidelines
He asked for more flesh
Everything2 ™ is brought to you by Everything2 Media, LLC. All content copyright © original author unless stated otherwise.
Monkey! Bat! Robot Hat!