On Tue, 8 Dec 1998, Tom Carlile wrote:
> Sun's CEO wanted to see how smart their engineers were, so he
> took them all to a room and gave them black jackets to put on.
> He told them that some of them have white Sun logos on the back
> of their jackets. When you discover that you have a logo
> go to the front of the room and he will check on them
> each hour until they have all the logo'ed at the front.
> You can not look at the back of your jacket, feel it, use
> mirrors or test for texture. You can only see everyone
> elses' jacket. How do you determine if you have a logo or not?
>
> Ok, I follow the beginning steps of induction here.
> "Try not. Do. Or do not. There is no try."
> -Yoda
Warning!!! A long, pedantic answer follows. Yoda's quote applies!
The statement is a little nicer if you the CEO says, "I'll come back every
hour. If you know that you have a white logo on your back, hand me your
jacket when I come in."
The Principle of Mathematical Induction goes something like this:
Let "S(k)" stand for a statement about a number k.
If the truth of S(k) implies the truth of S(k+1) AND S(0) is true,
then the statement holds for all non-negative integers.
Now, I'll explain the answer in the terms used above.
(It helps the explanation if we don't think about being in the room.)
S(k) = "If engineer sees k others with white logos,
then he can determine whether he has a white logo on his back
after k hours (after the CEO has come and gone the kth time)."
^^^^^^^^^^^^^
S(0) is true.
S(0)="If an engineer sees 0 others with white logos, then
he can determine whether he has a white logo on his back
after 0 hours."
You explained it nicely. The CEO said that there is at least
one white logo. If an engineer sees no one else with a white logo,
then he knows immediately (after 0 hours, when the CEO hasn't come and
gone at all) that he has the white logo. When the CEO returns after the
first hour, the engineer can go to the CEO and give him the jacket.
Now we *assume* that S(k) is true. That is, if an engineer sees k others
with white logos, then he can determine whether he has a white logo on his
back after k hours.
To prove that the statement is true no matter how many white logos an
engineer sees, the Principle of Mathematical Induction says that we just
have to induce the argument for S(k+1) from the assumed truth for S(k)
since S(0) is known to be true.
S(k+1) = If an engineer sees k+1 others with white logos, then he can
determine whether he has a white logo on his back after k+1 hours.
Let's see. We have this engineer, Tom, who can see k+1 white logos. Tom
assumes for the sake of argument that he doesn't have a white logo. Then
all of the white logoed ones will see *k* others with white logos...sound
familiar? That's the statement S(k). We assumed that S(k) was true.
Thus, after k hours have passed, and the CEO has come and gone for the kth
time, all of those k+1 engineers who could see k white logos know for sure
that they have white logos. That is, the truth of S(k) applies to those
k+1 engineers with white logos.
The CEO comes in the k+1 time after k+1 hours. If Tom doesn't have a
white logo, the k+1 white logoed ones know (by the truth of S(k)) that
they have white logos. They go up to the CEO and hand him their jackets.
Thus, Tom knows that he must not have had a black logo after k+1 hours (he
didn't know for sure until then as we see in the next paragraph).
If the k+1 engineers didn't go up to the CEO when he entered after k+1
hours, then they weren't sure whether they had white or black logos. If
they each saw k logos and weren't sure after the kth hour, then we have
contradicted S(k)...but we assumed S(k) was true. The only way S(k) could
still be true is if each of the k+1 white logoed ones saw k+1 other white
logoed ones. So each white logoed engineer sees k+1 white logos, not
counting himself. Thus, there are k+2 white logos in the room. Since Tom
can see everyone but himself and only counts k+1, he knows that he has a
white logo after k+1 hours have passed (and the CEO has come and gone
k+1 times).
We just showed that S(0) is true and that S(k) implies S(k+1).
Therefore, by the Princ. of Math. Induction, for all n=0,1,2,3,4,....
If an engineer in the room sees "n" others with a white logo,
he can determine after "n" hours whether he has a white logo.
I heard the game theorist John Conway give a talk on this problem. He
called it something like "Game for a room full of infinitely intelligent
people" because one has to assume that everyone else in the room also
knows how to find out whether he has a white logo on his back. You'll
notice that I ignored the fact that even if S(k) is true, one of our k+1
engineers might not be able to figure out whether he has a logo. I guess
the sun CEO is trying to figure out whether his engineers are all
infinitely intelligent. ;)
The CEO condition is a little confusing. I saw this problem once stated
as follows:
There is an island with many couples. Each woman knows whether all of the
husbands but her own are having affairs. If a woman discovers that her
husband is having an affair, she will kill him during the night of the
first night she knows. They couples live happily for many years. Then,
one morning, a man comes to the island and says, "k of the men on this
island are having affairs." What happens?
The answer is that on the kth night following this statement, k men are
killed. The question you asked is essentially, "Can we put any k greater
than 1 in the above riddle, and still have the answer be that k men are
killed on the kth night following this statement?"
> "true for n, true for n+1, true for all n" logic, for some cases
> anyway.
> n = 1; # one is prime
> n+1= 2; # two is prime
> therefore:
> n = 4; # four is prime
If you understood the above explanation, you know now why this isn't
induction. We need to be able to say:
k is prime implies k+1 is prime
You can't prove that statement in general since it doesn't work for k=3.
With some practice, you'll be able to spot correct induction from fake
induction in....k+1 seconds. ;)
Can you tell that I was a math major?
---------------------------------------------------------------------------
Send administrative requests to [EMAIL PROTECTED]
