A Referendum Puzzle

Here is another puzzle from Konstantin Knop. Puzzle. A town has 801 residents, and they vote on 9 different questions. On each question, everyone votes either “Yes” or “No”, and the majority wins. A resident is happy with the result of a question if the final decision matches their own vote. We will call a resident satisfied if they are happy with at least 5 of the 9 final decisions. What is the smallest possible number of satisfied residents? I leave the solution to the reader, but I want to recast the puzzle in the language of coding theory. Write each ballot as a string of 9 zeros and ones. For example, a 1 can mean “Yes” and a 0 can mean “No”. A ballot is then a point in the 9-dimensional Hamming cube. The final result is another string of 9 zeros and ones, obtained by taking the majority vote in each coordinate. The Hamming distance between two strings is the number of positions in which they differ. A resident is satisfied exactly when their ballot has Hamming distance at most 4…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town