PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on their heads, RED or BLUE. Nobody can see their own hat color. pn can see p(n-1),...,p1. More generally, pi can see all pj j < i.

Here is the game and the goal: Mr. Bad will put hats on people any way he likes (could be RBRBRB..., could be RRRBBB, could be ALL R's - like when a teacher has a T/F test where they are all FALSE.)

Then pn says R or B, p(n-1) says R or B, etc. When people say the color everyone else can hear it.

They want to MAXIMIZE how many of them say THEIR hat color. The people can meet ahead of time to discuss and agree on a strategy.

Mr. Bad knows the strategy the people will use.

What is the best they can do? Answer: n-1:

pn says RED if the number of REDS he sees is EVEN, BLUE if the number of REDS he sees is ODD. p(n-1) sees all ahead of him, knows the parity of all of them, can deduce his own hat. So can everyone ahead of him- KEY is that they use BOTH what they heard from the people who already spoke and what they see ahead of them. So can do n-1. (NOTE- a nice but not-optimal solution that some people have told me is to use the first log n people to code how many of the remaining hats are RED- this yields n- log(n) correct.)

PROBLEM 2: Same as Problem 2 but now there are c colors of hats.

That hats are colors 0,1,...,c-1. p(n) SUMS up all of the hats ahead of him MOD c. He says that number. p(n-1) heard that answer, See's whats ahead of him and sums that, and can deduce his own color. Again n-1 get it right.

OKAY, that's the problem and the answer. NOW my story and point:

I once had a group of College Students in a summer program working on PROBLEM 1. The plan was that they would first do the people-in-a-row-2-colors version, then people-in-a-row-c-colors version, then other versions. One can learn much math from looking at many variants. They began with the 2-color case and begun working out some examples. They had these tables (Note the word TABLES for later) for the n=3 case - really large decision trees- that (I think) did yield 2 people correct. They then had a table for n=4 where (I think) 2 people correct. They worked out a few more as well, perhaps getting up to n=8. The tables got larger and larger and more complicated. I never did quite understand their tables; however, they may have been doing an ad hoc version of the strategy where

n-log(n) people get the correct hats.)

I let them go on (perhaps too long) since they kept telling me NO BILL, DON"T TELL US HOW TO DO IT, IF YOU KNOW. And I was hoping they would have a breakthrough. But by the end of the second week they still hadn't gotten it (NOTE- this is not an indication that they were bad students--- its hard to tell how hard it is to see the trick once you know it) and asked me if I knew how to do it. I told them the solution above using Parity. I THOUGHT they would say OH, that's very nice, now lets see if we can do something similar for c-colors. But no. They insisted that their solution using tables was more intuitive or more informative or more ... something. None of that is remotely true. What is true is that by that point they were emotionally invested in their tables.

I kept saying DUMP YOUR TABLES now that you have a better way of doing it. They never did. But the phrase DUMP YOUR TABLES I now

use to mean DUMP SOME OLD WAY OF DOING THINGS THAT YOU ARE EMOTIONALLY ATTACHED TO BUT REALLY DOES NOT WORK.

Once you are aware of this phenomena you can see it often.

- You have a proof that uses a certain technique that you like (in my case perhaps Ramsey Theory) but then a better proof comes along. You have to admit that the new proof is better. DUMP YOUR TABLES.

- Your proof idea is beautiful but it just doesn't work. SHOULD YOU DUMP YOUR TABLES? Hard to tell- might work later.

- You get emotionally attached to a certain way to teach a course. Times change, technology changes, and perhaps you should DUMP YOUR TABLES.

- I have an idea for a blog entry that I think is really good and I begin writing it, and it just isn't working. I SHOULD DUMP MY TABLES.

- Sometimes in a story there is ONE really good idea and the rest is crap. This might be that the author had ONE really good idea

but could not build a good story around it. He should have DUMPED HIS TABLES.

- You have a phrase that you are fond of but it distracts from the point you are trying to make. You should

DUMP YOUR TABLES

(See Here For a case).

Specifically about tables, sometimes it helps to first write an ad-hoc solution for the first non-trivial instance and then see "how you did it" to try to get a generalization. For example, if you look at a table for the hats with 4 players, you might notice that the first player is "flippity" in what he/she says, and then maybe think that parity has something to do with it.

ReplyDeleteThere is a good quote from Einstein fitting:

ReplyDelete"Zwei Dinge sind zu unserer Arbeit nötig: Unermüdliche Ausdauer und die Bereitschaft, etwas, in das man viel Zeit und Arbeit gesteckt hat, wieder wegzuwerfen."

in english:

"Two things are required for our job: untiring efforts and the willingness to throw something away in which one has put a lot of work."