(idea) by hikaru Thu Sep 19 2002 at 3:40:43
Answers to some of MinderBender's puzzles:
  • Frogs and Lightbulbs:
    There's an elegant way to figure this out using number theory. The way I actually did it, however, was just to test it out and look for a pattern. I'll list which bulbs are on after each frog hops.
    1. 1 2 3 4 5 ... 100
    2. 1 3 5 7 9 ... 99
    3. 1 5 6 7 10 12 13 17 18 ...
    4. 1 4 5 6 7 8 10 13 17 18 ...
    5. 1 4 6 7 8 13 15 17 18 ...
    6. 1 4 7 8 12 13 15 17 ...
    7. 1 4 8 12 13 14 15 17 ...
    8. 1 4 12 13 14 15 16 17 ...
    9. 1 4 9 12 13 14 15 16 17 18...
    Ah ha!
    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 obvious after you reach 25. The square numbers (and 1) are left on.

    The elegant way: Consider a lightbulb k. 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 hopped. Which numbers have an odd number of factors? From number theory, only perfect squares have an odd number of factors. Well, and the number 1, of course.

  • Election Logic:
    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.
      Contradiction.

    • 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.

  • The Tower and the Glass Balls:
    A more efficient solution than MinderBender'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. MinderBender's solution was n/3 and O(n/3) for the worst case and average case, respectively. This seems pretty elegant, but I haven't proved that it's the most efficient. I've also left out the caveat 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 asymptotic behavior.
I like it!