First, we state the problem. Given that
1) Everyone knows that each person can see the color of
every bomb except his or her own,
2) There are N white bombs, but no one knows the value of N, and
3) Everyone knows that everyone knows that N > 0,
can you determine the color of your bomb?
For readability, refer to the preceding problem as the N-white problem.
Of course, if you cannot rely on the other mathematicians' logical
processes, this problem cannot be solved. So let us further postulate that
every mathematician (including you) will make one inductive "step" of
reasoning each evening, and that everyone knows this.
Claim: a) If your bomb is white you will solve the N-white
problem on the evening of day N.
b) On the evening of day N, you will know that someone
wearing a white bomb will solve the N-white problem
on the evening of day N.
c) If your bomb is black you will solve the N-white
problem on the evening of the N+1 day.
Proof: by induction.
Case N=1. (There is one white bomb; the rest are black.)
a) If your bomb is white, you will see zero white bombs.
That evening you will think about it, realize that yours
must be white (since you know that N > 0), and blow up
on the evening of day 1.
b) Whether your bomb is white or black, on the evening of
day 1 you will realize that a person wearing a white
bomb will solve the 1-White problem on the evening of day 1.
c) If your bomb is black, you see one white bomb. That
evening you will think about it and realize that you are
in either the 1-White or 2-White problem, depending on the
color of your bomb. The person wearing the white bomb will
blow up on the evening of day 1. When that one fails to show
up on day 2, you will have the information you need to blow
up on the evening of day 2.
Now, along the lines of classic textbook induction, we make the inductive
assumption that the claim is true for N=k and prove that the claim must be
true for N=k+1.
Case N=k+1. (There are k+1 white bombs; the rest are black.)
a) If your bomb is white, you will see k white bombs. On the
evening of day 1 you know that you are in either the k-White
or the k+1-White problem, depending on the color of your own
bomb. By the inductive assumption, on the evening of day k
you will realize that the k-White problem would be solved by
all persons wearing a white bomb. But everyone shows up to
work on day k+1, so that evening you realize that there must
be k+1 white bombs, and yours must be white. You blow up on
the evening of day k+1.
b) Whether your bomb is white or black, on the evening of day k+1
you realize that the k+1-White problem will be solved by all
persons wearing white bombs on the evening of day k+1.
c) If your bomb is black, you will see k+1 white bombs. On the
evening of day 1 you know that you are in either the k+1-White
or the k+2-White problem. By the evening of day k+1, you know
that people wearing white bombs will solve the k+1-White problem
on the evening of day k+1. When everyone shows up for work on
day k+2, you know that your bomb must be black, so you will
blow up on the evening of day k+2.
[Note for those who care: it would appear that we cannot make this work for
limit ordinals, so transfinite induction will fail. If you are forced to
wear a bomb, then, you should try to join an infinite team of
mathematicians, having made certain that there are infinitely many bombs of
each color.]
I believe that this completes the inductive proof. It is somewhat
bothersome that we must be so restrictive on when the mathematicians do
their thinking and how much thinking they can and must do at each step. But
without these restrictions, I'm not certain that the proof will fly. And
I'm still not certain how important it is for someone external to supply the
information that N > 0, when (in the case of N=17, anyway) not only does
every mathematician know that N > 0, but every mathematician knows that the
others also know. Any comments?
P.S.: If there are 17 white bombs, those 17 mathematicians will blow up on
the 17th evening. All others will blow up on the 18th evening.
>Have you seen this one before. The new guy in our department hit me
>with it - it kept me thinking for quite a while. Very nice, I think -
>and really quite funny. I thought I'd share with the fine folks on this
>list.
>
>There are 50 mathematicians who meet every day. Each one of them has a
>bomb strapped on their back - which is either black or white. Everybody
>can see everybody else's bomb except their own. Nobody ever, ever talks
>about the bombs. If somebody found out what color their bomb is, they
>would blow up that night and not return to work the next day.
>
>One day, somebody (not one of the usual mathematicians) walks in and
>says, "May I have everyone's attention?" and everybody turns to watch
>and hear him say: "There is at least one white bomb," and walk out. So,
>say there were 17 white bombs. How long do the mathematicians live?
>
>Geoff Hagopian
>Thanks to Jim Matthews,
>College of the Desert
>Palm Desert, CA
>
>ps Don't tell me what color my bomb is, and I'll try not to figure it
>out.
>
Kevin Broussard broussard@siskiyous.edu
College of the Siskiyous
800 College Avenue
Weed, CA 96094
(916) 938-5320
****************************************************************************
* To post to the list: email mathedcc@archives.math.utk.edu *
* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
* In the mail message, enter ONLY the words: unsubscribe mathedcc *
* Words in the Subject: line are NOT processed! *
* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
****************************************************************************