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…