## The Raven’s Hat

I agreed to review the book, The Raven’s Hat, because of the hats. I love hat puzzles. When I give them to my students, I bring hats to class to reenact the solutions.

The book contains eight awesome puzzles as well as ideas for playing with them. I both loved and hated this book. I loved it because it is great, and hated it because it isn’t perfect. Let me start with three places I didn’t like.

Consider a famous hat puzzle when there are hats of N colors. The sages are in a line, and hats are put on their heads. As usual, they are not allowed to give each other signals. Each of them has to announce their hat’s color, and they want to minimize the number of mistakes.

The big idea is to number the colors. The book suggests that the last sage in line calculates the total number of colors they see modulo N and announces the result to the rest. Then the others, starting from the end of the line, one by one, can calculate and name their hat colors. With this strategy, only the last sage in line might be mistaken.

This is a correct solution, but this is the first place I didn’t like. I prefer a different strategy, where everyone assumes that the total sum of the hat colors is 0 modulo N. In this case, every sage makes the same calculation: each sage sums up everything they see or hear and subtract the result from 0 modulo N. This solution is more elegant, since all the sages follow the same rule.

Then the book extends the same puzzle to an infinite number of sages. My second point of contention is that the authors think that, in this case, two sages might be mistaken. No. The answer is still the same, there is a strategy where not more than one sage is mistaken. See my blog post for the solution.

My third pet peeve happened when the authors introduced ballroom dancing in the puzzle on picture hanging. What is the connection between picture hanging and ballroom dancing? I’ll keep the book’s secret. My beef is with how the roles in ballroom dancing are described. Ballroom dancing is usually danced in pairs with asymmetric roles, which, in the past, were designated for males and females. Gender doesn’t play such a big role anymore; anyone can dance any role.

The authors are afraid to be politically incorrect by calling the dancers male and female. Instead, they say that the dancers dance male and female parts. Though formally, this choice of words might be politically correct, it still sounds awkward and draws attention to gender. If the authors ever talked to any person who has ever danced, they would have known that there is a much simpler way to describe dance roles. The dancers are divided into leaders and followers.

Did I ever tell you that reviewing my students’ writing is part of my job? So I am good at it and like critiquing other people’s writing. Now that my complaints are out, the issues with the book are actually minor.

The book is great. I even bought a second inflatable globe because of this book. The game, described in the book, is to rotate two globes randomly and then find a point on the globes in the same relative position towards the center. The game helped me teach my students that any movement of a sphere is a rotation.

My main goal in this post is to describe the only puzzle in the book that I haven’t seen before.

Puzzle. In a group of opera singers, there are two stars who are either friends or enemies. Surprisingly, only the host, who is not an opera singer, knows who the stars are and the nature of their relationship (the stars do not know that they are stars and whether or not they are friends). The group’s common goal is to identify the stars and to determine whether they are friends or enemies. To do so, they send a few of the singers to sing opera on a stage, which is divided into two halves: left and right. During the opera, the singers do not move between the halves. After the opera is over, the host classifies the opera. If there were no stars or only one star on stage, he classifies it as “neutral”. If both stars were on stage, the opera is a big success or a disaster. If both stars are friends and sing on the same half of the stage, or if they are enemies and sing on different halves, then the opera is a big success. Otherwise, it is a disaster.
What is the best strategy for a group of five singers to determine who are the stars and what is their relationship? What is the smallest number of operas they have to sing to guarantee that they can figure everything out?

It is weird that two people do not know whether they are friends. But sacrifices are needed for mathematics. I am excited that there is a nontrivial puzzle related to information theory, and it is ternary based. All other such puzzles I know are about weighing coins on a balance scale. I wrote too many papers about coin weighing. Now I can switch to opera singers with passionate relationships, secret from themselves.

Share:

1. #### Leo B.:

Cute puzzle. 3 operas are enough, as there are only 20 variants. A first try with 2 singers on each side splits the possibilities as 8 (neutral), and 6 each in case of success and failure. 8 possibilities can be told apart in two tries, by putting one now known star one one side with one of the original pairs, and a singer frmo the other pair on another side. This splits the space into 2-3-3; the third step is straightforward.

The 6 possibilities in cases of success of failure can also be distinguished in two tries, first by dropping one singer from one pair, to yield the split 2-3-3, etc.

2. #### Sanandan Swaminathan:

Delightfully different puzzle. Here’s an alternate way to achieve the goal with 3 operas. In a couple of scenarios, only 2 operas suffice. But to guarantee covering all 20 combinations of 2 stars out of 5 singers and their relationship, given that there are 3 possible outcomes from each opera, clearly we need 3 operas. Two operas can cover at most 3×3 = 9 of the 20 singer combinations (3 operas can theoretically cover 27 combinations). Let A, B, C, D, E be the five singers.

Opera1: A, B, C on left; D on right
if opera1 outcome = neutral… (this means E is a star)
Opera2: A, B on left; C, E on right

if opera2 outcome = neutral… (D is a star along with E)
Opera3: D on left; E on right (outcome can’t be neutral since both D and E are stars)
if opera3 outcome = success, D and E are stars and enemies
if opera3 outcome = disaster, D and E are stars and friends

if opera2 outcome = success… (A or B or C is a star apart from E)
Opera3: A, C on left; E on right
if opera3 outcome = neutral, B and E are stars and enemies
if opera3 outcome = success, A and E are stars and enemies
if opera3 outcome = disaster, C and E are stars and friends

if opera2 outcome = disaster… (A or B or C is a star apart from E)
Opera3: A, C on left; E on right
if opera3 outcome = neutral, B and E are stars and friends
if opera3 outcome = success, C and E are stars and enemies
if opera3 outcome = disaster, A and E are stars and friends

if opera1 = success… (E is not a star)
Opera2: A, B on left; C on right

if opera2 outcome = neutral… (D is a star)
Opera3: A on left; B, D on right
if opera3 outcome = neutral, C and D are stars and enemies
if opera3 outcome = success, A and D are stars and enemies
if opera3 outcome = disaster, B and D are stars and enemies

if opera2 outcome = success, A and B are stars and friends (third opera is not needed)

if opera2 outcome = disaster… (C is a star)
Opera3: A on left; C on right (outcome can’t be success)
if opera3 outcome = neutral, B and C are stars and friends
if opera3 outcome = disaster, A and C are stars and friends

if opera1 = disaster… (E is not a star)
Opera2: A, B on left; C on right

if opera2 outcome = neutral… (D is a star)
Opera3: A on left; B, D on right
if opera3 outcome = neutral, C and D are stars and friends
if opera3 outcome = success, B and D are stars and friends
if opera3 outcome = disaster, A and D are stars and friends

if opera2 outcome = success… (C is a star)
Opera3: A on left; C on right (outcome can’t be disaster)
if opera3 outcome = neutral, B and C are stars and enemies
if opera3 outcome = success, A and C are stars and enemies

if opera2 outcome = disaster, A and B are stars and enemies (third opera is not needed).

Thus, all 20 possibilities are covered by 3 operas – 10 where the two stars are friends, and 10 where they are enemies. In other words, each combination results in a different “signature” of 3 outcomes. For example, if B and C were the stars and they were friends, then the outcomes would be success, disaster, neutral. On the other hand, if B and C were the stars and they were enemies, the outcomes would be disaster, success, neutral.