tag:blogger.com,1999:blog-3722233.post2402516266256884857..comments2021-11-26T15:18:15.242-06:00Comments on Computational Complexity: A problem and later a story and a point.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-23958817206252578132013-07-17T02:32:34.988-05:002013-07-17T02:32:34.988-05:00Ah sorry, you are right. It seems that I assumed t...Ah sorry, you are right. It seems that I assumed the problem to be the one I know while I read the problem definition.<br />But it might be interesting to think about translations between them or transfers of the proofs...Anonymoushttps://www.blogger.com/profile/07476739423406915690noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32811236057503808832013-07-16T12:28:52.786-05:002013-07-16T12:28:52.786-05:00That paper talks about the problem where everyone ...That paper talks about the problem where everyone sees everyones<br />hat except their own. An excellent paper, and rather odd in<br />that the hat problem is used to do something with autored sequences,<br />but not a paper on the problem at hand.<br /><br />but you are RIGHT- a paper I DO want to look at.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26335067975935359412013-07-16T08:30:04.223-05:002013-07-16T08:30:04.223-05:00I think you want to look at this paper: http://cit...I think you want to look at this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.267Anonymoushttps://www.blogger.com/profile/07476739423406915690noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7379646169126876992013-07-16T07:41:03.535-05:002013-07-16T07:41:03.535-05:00Further improved: we can save
$n - \frac{c - 1}{l...Further improved: we can save <br />$n - \frac{c - 1}{log_2 c}$ people.<br /><br />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. <br />I.e., a $c-1$ bit binary vector. <br />We can do this using $\frac{c - 1}{log_2 c}$ $c$-ary bits and therefore $K = \frac{c - 1}{log_2 c}$.Space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-522881855079778712013-07-16T05:41:35.174-05:002013-07-16T05:41:35.174-05:00revised answers:
(a) People know $c$: we can save...revised answers:<br /><br />(a) People know $c$: we can save $n - ( c - 1 )$ persons. <br />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.<br /><br />(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.Space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24238496876427753312013-07-16T03:42:21.168-05:002013-07-16T03:42:21.168-05:00If c is unknown, it seems the first person can say...If 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.<br /><br />Or maybe I didn't really understand the problem.Enzo90910https://www.blogger.com/profile/01011450402149086824noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46225913324153938122013-07-16T03:07:38.083-05:002013-07-16T03:07:38.083-05:00The funny variant of this game is with a infinite ...The funny variant of this game is with a infinite number of participants (and a finite number of colors)... B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13890628634070127762013-07-16T02:29:55.620-05:002013-07-16T02:29:55.620-05:00You can extend the 2-color case to the c-color cas...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4528346855886719142013-07-15T23:55:28.029-05:002013-07-15T23:55:28.029-05:00we use modular arithmetic (mod c)
(1) if the colo...we use modular arithmetic (mod c)<br /><br />(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.<br /><br />(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).<br /><br />(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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14068882600194358922013-07-15T22:41:50.213-05:002013-07-15T22:41:50.213-05:00mine grows at n-log_c(2^(c-1)) by the way. it'...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 =(Magnanimoushttps://www.blogger.com/profile/17220880071029127545noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8330249725215082442013-07-15T21:14:30.314-05:002013-07-15T21:14:30.314-05:00Magnamimous and Space2001- Good solutions but
bett...Magnamimous and Space2001- Good solutions but<br />better is known.<br /><br />Space2001- good alternative problem- what if c<br />is not known. I don't know if one can do better<br />than you did in that case.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83052124778531627002013-07-15T20:57:24.826-05:002013-07-15T20:57:24.826-05:00Two cases:
(a) People know value of 'c':...Two cases: <br /><br />(a) People know value of 'c': In this case I can save <br />$n - ( c - 1 ) log_c n$ <br />people in the worst case.<br /><br />(b) People do not know value of 'c'. In this case I can save <br />$n - log_2 n - ( c - 1 ) log_c n$ <br />people in the worst case.<br /><br />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.Space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29677377380653711022013-07-15T20:28:44.368-05:002013-07-15T20:28:44.368-05:00c-color case. Similar approach. For three/four/f...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.<br />2^2<3^2<br />2^3<4^2<br />2^4<5^2<br />2^5<6^2<br />2^6>=7^2Magnanimoushttps://www.blogger.com/profile/17220880071029127545noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4222352798662697742013-07-15T19:54:56.290-05:002013-07-15T19:54:56.290-05:00EG and Magnamimous- yes, you have it correct (this...EG and Magnamimous- yes, you have it correct (this is MATH so<br />you already knew that). Magnamious- you are giving the answer<br />as the fraction that are right rather than the number that are right,<br />which is fine of course.<br /><br />NOW- try to do the c-color case.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70630646190295652652013-07-15T19:45:28.254-05:002013-07-15T19:45:28.254-05:00We can get (n-1)/n correct in the worst case for p...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.Magnanimoushttps://www.blogger.com/profile/17220880071029127545noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90771238177308093882013-07-15T18:47:11.134-05:002013-07-15T18:47:11.134-05:00How about a binary / parity solutions?
p(n) compu...How about a binary / parity solutions?<br /><br />p(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).<br /><br />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.<br /><br />So, worst case, n-1 will be correct.EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80751671414498904242013-07-15T18:08:17.303-05:002013-07-15T18:08:17.303-05:00A key piece of the puzzle is missing. Along with &...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.Space2001noreply@blogger.com