Solution for the general case using Hamming codes
on
The Three Hat Problem
·
· Score: 5
Nobody seems to have posted this yet, and since I've wasted a few hours on this already, I figured I should share. Here's the solution for the general case where the number of players is n=2^k-1; it involves Hamming codes.
The general case is perhaps best illustrated by example for the case of 7 players. Here's how it goes:
First, number the players 1 through 7. Now think of a player with a red hat as being assigned a binary zero, and a player with a blue hat as being assigned a binary 1. Then an assignment of hats to the players can be associated with a length 7 binary sequence: As an example, if all the players have red hats, this correspond to the sequence 0000000 (seven zeros), and if all but the last player have red hats, we get the sequence 0000001. We'll call length 7 binary sequences words; every hat assignment has an associated word, and vice versa. For future reference, denote the two words in the example above as c0 and c1 respectively.
A brief digression on Hamming codes: A length 7 Hamming code is a certain (carefully chosen) subset of the 2^7=128 possible words. This subset consists of 16 words, called codewords. We need just one fact about Hamming codes to describe the players' strategy: [Fact 1] If any one bit in a codeword is flipped, the resulting word is not a codeword. For example: c0, the all zero word, is always a codeword in a Hamming code; c1, which differs from c0 in just one bit, cannot be a codeword.
Suppose I am one of the players. Here's my strategy:
By observing the hats of the other 6 players, I construct two words. The first, w0, is the word that would be associated with our hat assignments if my hat is red. The second, w1, is the word that would be associated with our hat assignments if my hat is blue. We have 3 possible cases:
Neither w0 nor w1 is a codeword
w0 is a codeword
w1 is a codeword
Cases 2 and 3 are mutually exclusive because of Fact 1. My strategy?
In case 1, I say nothing, in case 2, I declare my hat to be blue, and in case 3, I declare my hat to be red.
That's it. This strategy will result in the team winning every time the word associated with the hat assignment is not a codeword, which happens (128-16)/128=7/8 of the time.
So, why does this work? To understand, we need one more property of Hamming codes: [Fact 2] For every word that is not a codeword, there is a unique bit, which if flipped, will produce a codeword. For instance, if the last bit in c1 is flipped, we get c0, the all zero codeword. Now suppose that the hat assignment is associated with a word that's not a codeword (which, as shown above, happens 7/8 of the time). To be specific, suppose the assignment corresponds to c1. Here, the 7th bit is the unique bit that can be flipped to get a codeword. Then, by Fact 2, players 1 through 6, after constructing their w0 and w1 words, will find themselves in Case 1 : neither word is a codeword. They'll keep quiet, while the 7th player will declare his hat to be blue (Case 2). Success!
Of course, if the hat assignment corresponds to a codeword, then every player will speak up, and they'll all guess wrong! Example again: if every player is assigned a red hat (corresponding to c0), they'll all say they have blue hats.
It's not hard to see how this generalizes for an arbitrary number of players n, where n=2^k-1. The players will succeed if and only if the associated word is not a codeword. A Hamming code of length n=2^k-1 has 2^(n-k) codewords, so success is achieved 1-2^-k of the time, which tends to 1 as k tends to infinity.
There, I knew those grad courses in coding theory would come in useful sometime!
I strongly recommend you take a look at the book "Digital Multimedia" by Nigel and Jenny Chapman. The book's website has more info and additional materials to accompany the book.
The book contains a wealth of info, and is very well written. Of particular interest to the ask slashdotter is the last section on Multimedia Practice. It contains a variety of ideas for multimedia projects, illustrating what is possible.
The question is: what were the odds of seeing the hockey card? If it was a certainty, then if every boy plays hockey, we're done: there can only be one boy (i.e. it's one boy, 2 girls a 100%)
But if the odds of seeing the card are not 1, then surely it's more likely that a card is observed if there's 2 boys rather than 1?
I guess I'm trying to make the same argument for an increased likelihood of there being two boys as you make for an increased likelihood of there being two girls.
The use of LaTeX vs. Word is very much a field dependent thing. In the Systems area of Electrical Engineering (Communications/Controls/Signal Processing), LaTeX is used almost exclusively. On the other hand, the use of Word is quite common among EEs in the semiconductor area. I suspect that much depends on how "math heavy" your papers are. Interesting aside: to go with the above, conference presentations in the Comm field are almost always made using good old fashioned transparencies made using LaTeX, whereas semiconductor folk often use PowerPoint.
Disclaimer: I can speak with some authority regarding Comm., but the semiconductor obervations above are based on limited experience.
I've been searching for the right tool for quite a while now, but am yet to find it. We use latex/bibtex for all our papers, so I need to keep my refs in bibtex format. For now, I just use Emacs' bibtex mode, which functions quite nicely for entering biblio information. Fancier GUIs are available: for instance, take a look at the cross-platform TkBibTeX.
You can also "roll your own" using the perl modules from btOOL.
My general dissatisfaction with the freely available tools means that a bibliography manager will be one of my first programming projects when I lay my hands on an OS X box in a few weeks (drool...)
Check out Camp CAEN offered by the College of Engineering at the University of Michigan. There's C++, Java, web and digital video stuff (makes good use of the cool Media Union facilities), and Palm development.
Plus, Ann Arbor is a really nice place in the summer!
Here's something I have been puzzled about for a long time: it is generally accepted that click-through licenses are unenforceable. Does the same hold for the GPL? Will RMS or anyone else actually be able to claim a copyright violation if people use the source to Free Software without sticking to the terms of the GPL?
More generally, not accepting click-through licenses as valid, while demanding compliance with the GPL would appear a double-standard. If the courts eventually rule that click-through's are invalid, will the GPL still have a leg to stand on? (Legally that is; community displeasure and general bad PR will of course count for a lot, and discourage violation)
i) MathType. It's a
souped up version of the free Equation editor. I haven't used it
myself, but I've heard good things about it. Pros: You can still
use Powerpoint. Cons: It costs money!
ii) Use LaTeX/LyX to create the slides (the seminar class
works fairly well). Then convert the whole thing to pdf and
display using the full screen feature of Acrobat Reader. If
you're running LaTeX under Unix/Linux, remember to first
generate the postscript with Type 1 fonts, or the pdf file
will look awful on screen. Pros: Everything is free (except
Acrobat distiller, and maybe you could use something like dvi2pdf
or pdftex instead). Cons: You can't use snazzy Powerpoint
effects, although acrobat will let you use some transitions
effects between slides.
iii) Another untried solution: Mathematica. If you don't
have Mathematica, you could try Publicon,
which is essentially the Mathematica front-end being marketed
separately as a technical publishing tool. Look
here for some examples. This is another free solution.
They have discarded way to many Unix conventions for my liking. They have come up with their own method of 'controlling' services.
This actually might turn out to be a Very Good Thing. The OS X config files system appears to be actually more consistent and uses XML extensively. See the excellent series of articles on the DP releases by John Siracusa over at Ars.
To get these services to not start at boot required hacking config files (after 30 minutes of searching to find them).
I feel that there is certainly the potential in OS X for considerably reducing the time it takes to tweak configuration settings over typical Unices.
I strongly urge all wise aged Linux veterans to try to look at OS X with a different pair of lenses; I actually hope that some of these "under the hood" ideas in OS X will find their way into a Linux distribution in the near future.
The "angle" example above generalizes roughly like this:
A (monic*) polynomial p(x) of degree k is completely determined by knowing its value at k distinct points. So, you can "prove" that you have collected k different values by generating p(0) based on these values. If you had fewer than k values, the information is useless, because p(0) could be any real number at all!
Of course, you could distribute the value of the polynomial at n different (non-zero!) points to n different servers and any subset of size k would do the trick.
*monic polynomials are polynomials for which the coefficient of the highest order term is 1.
I think it is important to note that not every download of an MP3 file through Napster represents a loss to the artist; there is a loss to the artist only if, in the absence of Napster, the person who downloads the MP3 would have bought the CD instead.
Of course, I see no way of actually estimating what fraction of users are using MP3s in lieu of buying CDs.
In fact, there is presumably some (small!) fraction of people who hear music obtained illegally through Napster, and then proceed to buy the CD in order to support the artist (or even just as a convenience); these folks may never have listened to the said artist otherwise.
In the Sep/Oct 99 issue of the magazine IEEE Network, Richard Edell and Pravin Varaiya of Berkeley put forth an interesting critique of flat rate pricing for ISPs. The article (which describes a prototype of an alternative ISP model) is available in PDF and in Postscript.
Two quotes are pertinent to AOLs latest action. They point out that flat rate pricing "...creates an incentive for the ISP to passively or actively degrade service quality, since per subscriber usage and cost decrease with worse quality but revenue remains the same." A little later, they state,
"The only incentive to limit service degradation is the threat of loss of subscribers to other ISPs. ISPs reduce this threat by increasing the cost of switching to other providers. For example, in order to switch, a subscriber would have to reconfigure her computer which she may find difficult to do, and her e-mail would not be forwarded."
Hmmm.
(Note: for the purposes of this comment, AOL is considered an ISP, although the authors do mention that "...AOL's Internet service provision is now handled by UUNet, so AOL may properly be said not to be an ISP any more.")
Slashdot Mirror
The general case is perhaps best illustrated by example for the case of 7 players. Here's how it goes:
First, number the players 1 through 7. Now think of a player with a red hat as being assigned a binary zero, and a player with a blue hat as being assigned a binary 1. Then an assignment of hats to the players can be associated with a length 7 binary sequence: As an example, if all the players have red hats, this correspond to the sequence 0000000 (seven zeros), and if all but the last player have red hats, we get the sequence 0000001. We'll call length 7 binary sequences words; every hat assignment has an associated word, and vice versa. For future reference, denote the two words in the example above as c0 and c1 respectively.
A brief digression on Hamming codes: A length 7 Hamming code is a certain (carefully chosen) subset of the 2^7=128 possible words. This subset consists of 16 words, called codewords. We need just one fact about Hamming codes to describe the players' strategy: [Fact 1] If any one bit in a codeword is flipped, the resulting word is not a codeword. For example: c0, the all zero word, is always a codeword in a Hamming code; c1, which differs from c0 in just one bit, cannot be a codeword.
Suppose I am one of the players. Here's my strategy:
By observing the hats of the other 6 players, I construct two words. The first, w0, is the word that would be associated with our hat assignments if my hat is red. The second, w1, is the word that would be associated with our hat assignments if my hat is blue. We have 3 possible cases:
- Neither w0 nor w1 is a codeword
- w0 is a codeword
- w1 is a codeword
Cases 2 and 3 are mutually exclusive because of Fact 1. My strategy? That's it. This strategy will result in the team winning every time the word associated with the hat assignment is not a codeword, which happens (128-16)/128=7/8 of the time.So, why does this work? To understand, we need one more property of Hamming codes: [Fact 2] For every word that is not a codeword, there is a unique bit, which if flipped, will produce a codeword. For instance, if the last bit in c1 is flipped, we get c0, the all zero codeword. Now suppose that the hat assignment is associated with a word that's not a codeword (which, as shown above, happens 7/8 of the time). To be specific, suppose the assignment corresponds to c1. Here, the 7th bit is the unique bit that can be flipped to get a codeword. Then, by Fact 2, players 1 through 6, after constructing their w0 and w1 words, will find themselves in Case 1 : neither word is a codeword. They'll keep quiet, while the 7th player will declare his hat to be blue (Case 2). Success!
Of course, if the hat assignment corresponds to a codeword, then every player will speak up, and they'll all guess wrong! Example again: if every player is assigned a red hat (corresponding to c0), they'll all say they have blue hats.
It's not hard to see how this generalizes for an arbitrary number of players n, where n=2^k-1. The players will succeed if and only if the associated word is not a codeword. A Hamming code of length n=2^k-1 has 2^(n-k) codewords, so success is achieved 1-2^-k of the time, which tends to 1 as k tends to infinity.
There, I knew those grad courses in coding theory would come in useful sometime!
The book contains a wealth of info, and is very well written. Of particular interest to the ask slashdotter is the last section on Multimedia Practice. It contains a variety of ideas for multimedia projects, illustrating what is possible.
The question is: what were the odds of seeing the hockey card? If it was a certainty, then if every boy plays hockey, we're done: there can only be one boy (i.e. it's one boy, 2 girls a 100%)
But if the odds of seeing the card are not 1, then surely it's more likely that a card is observed if there's 2 boys rather than 1?
I guess I'm trying to make the same argument for an increased likelihood of there being two boys as you make for an increased likelihood of there being two girls.
Disclaimer: I can speak with some authority regarding Comm., but the semiconductor obervations above are based on limited experience.
You can also "roll your own" using the perl modules from btOOL.
My general dissatisfaction with the freely available tools means that a bibliography manager will be one of my first programming projects when I lay my hands on an OS X box in a few weeks (drool...)
Plus, Ann Arbor is a really nice place in the summer!
More generally, not accepting click-through licenses as valid, while demanding compliance with the GPL would appear a double-standard. If the courts eventually rule that click-through's are invalid, will the GPL still have a leg to stand on? (Legally that is; community displeasure and general bad PR will of course count for a lot, and discourage violation)
Here are a few options to consider.
i) MathType. It's a souped up version of the free Equation editor. I haven't used it myself, but I've heard good things about it. Pros: You can still use Powerpoint. Cons: It costs money!
ii) Use LaTeX/LyX to create the slides (the seminar class works fairly well). Then convert the whole thing to pdf and display using the full screen feature of Acrobat Reader. If you're running LaTeX under Unix/Linux, remember to first generate the postscript with Type 1 fonts, or the pdf file will look awful on screen. Pros: Everything is free (except Acrobat distiller, and maybe you could use something like dvi2pdf or pdftex instead). Cons: You can't use snazzy Powerpoint effects, although acrobat will let you use some transitions effects between slides.
iii) Another untried solution: Mathematica. If you don't have Mathematica, you could try Publicon, which is essentially the Mathematica front-end being marketed separately as a technical publishing tool. Look here for some examples. This is another free solution.
Oh, and as a bonus, they take the kids on a free plane ride one afternoon (one of the planes being flown by Thompson).
This actually might turn out to be a Very Good Thing. The OS X config files system appears to be actually more consistent and uses XML extensively. See the excellent series of articles on the DP releases by John Siracusa over at Ars.
I feel that there is certainly the potential in OS X for considerably reducing the time it takes to tweak configuration settings over typical Unices.I strongly urge all wise aged Linux veterans to try to look at OS X with a different pair of lenses; I actually hope that some of these "under the hood" ideas in OS X will find their way into a Linux distribution in the near future.
Also, Apple will release the developer tools to all online ADC members (free registration) in mid-October.
This is the serious problem in universities across the country today!
A (monic*) polynomial p(x) of degree k is completely determined by knowing its value at k distinct points. So, you can "prove" that you have collected k different values by generating p(0) based on these values. If you had fewer than k values, the information is useless, because p(0) could be any real number at all!
Of course, you could distribute the value of the polynomial at n different (non-zero!) points to n different servers and any subset of size k would do the trick.
*monic polynomials are polynomials for which the coefficient of the highest order term is 1.
Of course, I see no way of actually estimating what fraction of users are using MP3s in lieu of buying CDs.
In fact, there is presumably some (small!) fraction of people who hear music obtained illegally through Napster, and then proceed to buy the CD in order to support the artist (or even just as a convenience); these folks may never have listened to the said artist otherwise.
Two quotes are pertinent to AOLs latest action. They point out that flat rate pricing "...creates an incentive for the ISP to passively or actively degrade service quality, since per subscriber usage and cost decrease with worse quality but revenue remains the same." A little later, they state,
Hmmm.
(Note: for the purposes of this comment, AOL is considered an ISP, although the authors do mention that "...AOL's Internet service provision is now handled by UUNet, so AOL may properly be said not to be an ISP any more.")