in reply to CarTalk Puzzler

No code is needed. It's about the number of factors. Start with everything off and have someone go through and pull every 1nth cord. Then, someone pulls every 2nd and on with the puzzle. If a number has an even number of factors, then it will be off. If it has an odd number of factors, it will be on. The only numbers that have an odd number of factors is when one of the factors is repeated. That only happens if it's a perfect square. :-)
My criteria for good software:
  1. Does it work?
  2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Replies are listed 'Best First'.
Re^2: CarTalk Puzzler
by tilly (Archbishop) on Nov 17, 2005 at 16:57 UTC
    Your conclusion is good, but your reasoning is not. For instance 8 is a number which is not a perfect square yet has a repeated factor.

    A correct way of reasoning this goes as follows:

    1. The number of times the n'th light is pulled is the same as its number of factors.
    2. It will be on if and only if there are an odd number of factors.
    3. If you write out the prime factorization of a number, P1n1 * P2n2 * ... * Pmnm, then the number of factors the number has is (i1 + 1)(i2 + 1)...(im + 1)
    4. This is odd if only if i1, i2, ... , im are all even.
    5. This is true if and only if n is a perfect square.
    6. From 2) and 5), the n'th light is on if and only if n is a perfect square.
[reply]
      The term "factor" for a non-mathematician (which was my intended audience) is "any number that you multiply by a single other number to get the original number". In the case of 8, 2 is a repeated factor mathematically, but the factors of 8 (according to the gradeschool definition) are 1, 2, 4, and 8 - 4 factors without repetition.
      My criteria for good software:
      1. Does it work?
      2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
[reply]
        Mathematicians have the same definition of factor as what you used. It is your definition of repeated factor that I was confused about. To me if f divides n, and f divides n/f, then f is a repeated factor of n. It seems from your description that to you say that f is a repeated factor of n if and only if f*f=n.

        That isn't confusing in a "non-mathematician vs mathematician" way. That is confusing in a "you used a phrase that described what you meant without noticing that it was very ambiguous" way. That is, I am confident that I would not have understood that as you intended back in highschool. And I was likewise not confused when I first saw the phrase "this factor is repeated 3 times".

        In ths case your reasoning has a non-obvious step from "odd number of factors" to "one factor must be the square root of the number". It is easy enough to fill that in - just add a comment that you can pair off factors by putting i with j if i*j=n, and you will have a left-over if and only if there is a factor i with i*i=n. But since that pairing is the key step, it needs to actually be stated. You can't expect other people to have that flash of brilliance.

[reply]

In Section Meditations