Hat guessing with 100 hats case

Question

My question is regarding to the question which was asked here: A riddle about guessing hat colours (which is not among the commonly known ones)

$100$ prisoners are put a hat on top of their head, which can be red or blue. The colours are chosen at random by $100$ independent fair coin tosses. Then each prisoner can guess their own hat colour (red or blue) or pass. The prisoners can see each other, but not hear each other's calls and of course they have no other means of communication. This means that each call can only depend on the other prisoners' hat colours. However, before the distributing of hats begins, the prisoners are told the rules and can agree on a strategy. The prisoners win iff no prisoner guesses wrong and at least one prisoner guesses right. Which strategy should the prisoners use so that the winning probability becomes maximal?

on this question they found answer for $n=2^k-1$ and $2^k$ but my question is how can I solve for other cases? specificly for $n=100$

Answer 1

It is in general an open problem to find the optimal probability of success for $n$ prisoners when $n\notin\{2^k-1,2^k\mid k\in \mathbb N_+\}$, except for all values of $n$ up to $9$. The best known bounds for $n$ up to $33$ are given in the table in the linked answer.

Even though an optimal strategy is unknown, the following is a pretty good strategy. Find the largest integer $m$ such that $m\le n$ and $m=2^k-1$, for some $k$. The first $m$ prisoners use the Hamming code strategy, while the remaining $n-m$ prisoners pass. This gives a probability of failure of $1/(m+1)$, which is at most $2/(n+1)$. Since it can be shown that every strategy has a failure rate of at least $1/(n+1)$, this strategy is within a factor of $2$ of optimal.

For $n=100$, the success rate is $63/64\approx 98\%$.

I will now prove that every strategy must fail with probability at least $1/(n+1)$. Fix a strategy, and tabulate the number of people who are wrong in each of the $2^n$ possible scenarios. Whenever the prisoners win, there is at least one correct guess, and whenever the prisoners lose, there are at most $n$ incorrect guesses. Furthermore, each prisoner is correct on average half of the times that they guess, so over all cases, the number of correct and incorrect guesses must be equal. Letting $W$ be the number of winning situations and $L$ the number of losing situations, the previous discussion implies $$ W\le nL, $$ which can be manipulated to show that $$ P(\text{losing})=\frac{L}{W+L}\ge \frac{1}{n+1}. $$