Problem Set 1Due: Tuesday, September 16, 2013Suggested Problems:Required Problems:ESE 523: Introduction to Information Theory Professor Joseph A. O’Sullivan Fall 2013 Problem Set 1 Due: Tuesday, September 16, 2013 Suggested Problems: 1. Look over the problems at the end of chapter 2. 2. Problem 2.9. Required Problems: 1. Problem 2.1. 2. Problem 2.6. 3. Problem 2.10. 4. Problem 2.12. 5. Problem 2.16. 6. Solve the problem from the New York Times article (see below) for three players and for seven players. April 10, 2001 Why Mathematicians Now Care About Their Hat Color By SARA ROBINSON ERKELEY, Calif., April 9 — It takes a particularly clever puzzle to stump a mind accustomed to performing mental gymnastics. So it's no ordinary puzzle that's spreading through networks of mathematicians like a juicy bit of gossip. Known as "the hat problem" in its most popular incarnation, this seemingly simple puzzle is consuming brain cycles at universities and research labs across the country and has become a vibrant topic of discussion on the Internet. The reason this problem is so captivating, mathematicians say, is that it is not just a recreational puzzle to be solved and put away. Rather, it has deep and unexpected connections to coding theory, an active area of mathematical research with broad applications in telecommunications and computer science. In their attempts to devise a complete solution to the problem, researchers are proving new theorems in coding theory that may have applications well beyond mathematical puzzles. "This puzzle is unique since it connects to unsolved mathematical questions," said Dr. Joe Buhler, deputy director of the Mathematical Sciences Research Institute here and a hat problem enthusiast. The hat problem goes like this: Three players enter a room and a red or blue hat is placed on each person's head. The color of each hat is determined by a cointoss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own. No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly. The same game can be played with any number of players. The general problem is to find a strategy for the group that maximizes its chances of winning the prize. One obvious strategy for the players, for instance, would be for one player to always guess "red" while the other players pass. This would give the group a 50 percent chance of winning the prize. Can the group do better? Most mathematicians initially think not. Since each person's hat color is independent of the other players' colors and no communication is allowed, it seems impossible for the players to learn anything just by looking at one another. All the players can do, it seems, is guess. "I tell someone the problem and they think they don't have the conditions right," said Dr. Peter Winkler, director of fundamental mathematics research at Bell Labs of Lucent Technologies in Murray Hill, N.J. "But if you try to prove it's impossible, it doesn't quite work." Mathematicians credit the problem to Dr. Todd Ebert, a computer science instructor at the University of California at Irvine, who introduced it in his Ph.D. thesis at the University of California at Santa Barbara in 1998. Dr. Ebert said he discovered the problem's appeal only recently, when he offered extra credit to his students for solving a seven-player version he called the "seven prisoners puzzle." Next thing he knew, the problem was posted on Internet news groups and in chat rooms. "I started getting e-mail from all over the country," Dr. Ebert said. Meanwhile, Dr. Winkler, a well- known collector and distributor of clever puzzles, heard the problem from a colleague and spread it widely. It has cropped up at Microsoft Research in Redmond, Wash., at Hewlett-Packard Laboratories in Palo Alto, Calif., and at mathematics, statistics and computer science departments at universities across the country. The problem has even spread to the Caribbean. At a workshop at a research institute in Barbados, one hardy group of theoretical computer scientists stayed up late one rum- soaked night, playing a drinking game based on the puzzle. It spread to Berkeley after Dr. Winkler bumped into Dr. Elwyn Berlekamp, a professor in the Berkeley math department, at a conference in New Orleans in January. "I told him about the problem and next thing I knew he was leaving messages on my hotel phone saying, `Great problem, haven't gotten it yet,' then finally, `I got it,' " Dr. Winkler said. "I thought, with his knowledge of coding theory, he'd find that approach, and he didn't disappoint me." Dr. Berlekamp, a coding theory expert, said he figured out the solution to the simplest case in about half an hour, but he saw the coding theory connection only while he was falling asleep that night. "If you look at old things that you know from a different angle, sometimes you can't see them," he said. The first thing Dr. Berlekamp saw was that in the three-player case, it is possible for the group to win three- fourths of the time. Three-fourths of the time, two of the players will have hats of the same color and the third player's hat will be the opposite color. The group can win every time this happens by using the following strategy: Once the game starts, each player looks at the other two players' hats. If the two hats are different colors, he passes. If they are the same color, the player guesses his own hat is the opposite color. This way, every time the hat colors are distributed two and one, one player will guess correctly and the others will pass, and thegroup will win the game. When all the hats are the same color, however, all three players will guess incorrectly and the group will lose. "If you look at the total number of guesses made, it's still the case that half are right and half wrong," Dr. Winkler said. "You only make progress if, when players are guessing wrong, a great many are guessing wrong." The strategy gets far more complicated for larger numbers of players. Still, it all comes down to making sure that most of the time no one is wrong and occasionally everyone is wrong at once. As it turns out, this requirement