I have (1) a math problem to tell you about (though I suspect many readers already know it), (2) a story about it, and (3) a point to make. TODAY I'll just do the math problem. Feel free to leave comment with solutions--- so if you haven't seen it before and want to try it, then don't look at the comments. Tommorow or later I will tell you the story and make my points.
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. They CAN meet ahead of time to discuss strategy.
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. They want to MAXIMIZE how many of them say THEIR hat color. Assume that Mr. Bad knows the strategy the people will use.
What is the best they can do?
Here is a strategy: pn says R if the MAJORITY are R, and B if the MAJORITY are B, and then everyone says what pn says. They are guaranteed around n/2 correct.
Here is a strategy: Assume n is even. pn says the color of p(n-1). p(n-1) then says what pn said and gets it right. then p(n-2) says what p(n-3) has. Then p(n-3) gets it right. You are guaranteed to get around n/2 right.
GEE- can we do better than n/2? Or can one prove (perhaps using Ramsey Theory, perhaps something I learned at Erdos 100 over dinner) that you can't beat n/2 (or perhaps something like n/2 + log(log(n))).
PROBLEM 2: Same as Problem 2 but now there are c colors of hats.
NOTE- there are MANY hat problems and MANY variants of this scenario--- some where you want to maximize prob of getting them all right, some where everyone sees everyones hat but their own. These are all fine problems, but I am just talking about (1) people are in a row, (2) Want to maximize how many they get right in the worst case.
ADDED LATER- WARNING- THE ANSWER TO PROBLEM 1 IS IN THE COMMENTS NOW.
SO IF YOU WANT TO SOLVE IT YOURSELF DO NOT LOOK AT THE COMMENTS.
A key piece of the puzzle is missing. Along with "Then pn says R or B, p(n-1) says R or B, etc.": Mr Bad shoots the person who answers incorrectly. I.e., the rest of the people know the correctness of each of the answers given by earlier folks.
ReplyDeleteHow about a binary / parity solutions?
ReplyDeletep(n) computes the parity bit for the rest of the peoples' hats (use Red=0, Blue=1) and uses that as his guess. He has a 50/50 chance of being right about his own hat (we'll assume he's wrong).
Now everyone else can correctly compute their hat's color when it is their turn because they will know everyone's hat color other than their own (they can see those in front of them and they heard the answers of those behind them) and can use the parity information to determine their hat's color.
So, worst case, n-1 will be correct.
We can get (n-1)/n correct in the worst case for problem 1. The first person can count the number of red hats (for instance) worn by p1...p(n-1). If pn sees an even number of red hats, he guesses red. If he sees an odd number of red hats, he guesses odd. Now p(n-1) knows whether there are an even number of red hats worn between p(1) and himself or an odd number. But he can check for himself how many red hats tehre are between p(1) and p(n-2), so it's easy for him to figure out what his own hat color is. Then each person from that point on will be able to figure out their own hat color. The first person has no choice but to guess, so the worst case is (p-1)/p.
ReplyDeleteEG and Magnamimous- yes, you have it correct (this is MATH so
ReplyDeleteyou already knew that). Magnamious- you are giving the answer
as the fraction that are right rather than the number that are right,
which is fine of course.
NOW- try to do the c-color case.
c-color case. Similar approach. For three/four/five/six colors, you can use the first two people, using each of the 9,16,25, or 36 possible choices (respectively) to encode the parity of each of the colors (although you only need to encode parity of c-1 colors). When you get to 7, there are only 49 possible encodings, when you need 64 to describe the number of possible states so you need more people. Not a complete answer, but I will think about this some more.
ReplyDelete2^2<3^2
2^3<4^2
2^4<5^2
2^5<6^2
2^6>=7^2
Two cases:
ReplyDelete(a) People know value of 'c': In this case I can save
$n - ( c - 1 ) log_c n$
people in the worst case.
(b) People do not know value of 'c'. In this case I can save
$n - log_2 n - ( c - 1 ) log_c n$
people in the worst case.
Both are obtained by having people who are in front of the line encode the exact number of different hats after the 'K'th person in the line.
Magnamimous and Space2001- Good solutions but
ReplyDeletebetter is known.
Space2001- good alternative problem- what if c
is not known. I don't know if one can do better
than you did in that case.
mine grows at n-log_c(2^(c-1)) by the way. it's slightly better than space2001's because i'm not representing the exact number of different hats, only the parity of each color. But that seems to me to be the minimal amount of information needed to represent the state of the system. I don't know how i can use any less information than that =(
ReplyDeletewe use modular arithmetic (mod c)
ReplyDelete(1) if the colors are known, then they are assigned numbers from 0 to c-1, beforehand. Then p_n announces the sum (mod c) of all numbers he sees. The rest can announce their colors correctly. So (n-1) worst case.
(2) If c is known but not the color names, the the last c guys announce the color names. The colors are numbered from 0 to c-1 in the order they are announced. Then we continue as case (1). The worst case is (n - c - 1).
(3) If c is not known, then the same strategy as (2) works since the person announcing the sum will have to repeat a color name.
You can extend the 2-color case to the c-color case. Assign the color c_i to the number i (0<=i<c) and compute the sum of all colors multiplied with the number of hats of this color mod c. The first one guesses the color c_j if j is the result of this computation. Then the next one computes the same, only that his value k differs from j exactly in his hat-color mod c. Everyone can compute the current value mod c with the previous answers and compute his own color. So n-1 people can be saved.
ReplyDeleteThe funny variant of this game is with a infinite number of participants (and a finite number of colors)...
ReplyDeleteIf c is unknown, it seems the first person can say c and the others can apply the sum modulo c strategy for a guaranteed n-2.
ReplyDeleteOr maybe I didn't really understand the problem.
revised answers:
ReplyDelete(a) People know $c$: we can save $n - ( c - 1 )$ persons.
The first $(c - 1)$ persons will encode remainder modulo $c$ of the counts of each of first $(c - 1)$ colors among the last $n - (c - 1)$ people. Thereafter the $c-2$ person in the list can perfectly reconstruct his hat color and so on. To encode the remainder modulo $c$ we only need a $c$-ary bit.
(b) People don't know 'c': we can save $n - log_2 n - ( c - 1 )$ people by encoding c followed by (a). Maybe can do better with regards to encoding c.
Further improved: we can save
ReplyDelete$n - \frac{c - 1}{log_2 c}$ people.
In the previous solution instead of sending remainder modulo $c$ the first set of people only need to send remainder modulo $2$ of the counts for $c-1$ colors among last $n-K$ people.
I.e., a $c-1$ bit binary vector.
We can do this using $\frac{c - 1}{log_2 c}$ $c$-ary bits and therefore $K = \frac{c - 1}{log_2 c}$.
I think you want to look at this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.267
ReplyDeleteThat paper talks about the problem where everyone sees everyones
Deletehat except their own. An excellent paper, and rather odd in
that the hat problem is used to do something with autored sequences,
but not a paper on the problem at hand.
but you are RIGHT- a paper I DO want to look at.
Ah sorry, you are right. It seems that I assumed the problem to be the one I know while I read the problem definition.
DeleteBut it might be interesting to think about translations between them or transfers of the proofs...