u/Tc14Hd

During one of your long journeys, you come across a desolate mountaintop in the middle of nowhere. To your surprise, you are met with a crowd of gods arguing with each other. Upon seeing you, they stop their debate to tell you that they will grant you a wish if you can solve their riddle.​

There are 100 gods in total. When asked a question, 90 of them will always answer truthfully, while the remaining 10 will answer each question randomly. Initially, you don’t know which god falls into which of the two categories, but each god knows it for every other god.

Your goal is to identify at least one truth-telling god using at most 20 yes-or-no questions. Each question can be directed at only one god at a time, though multiple gods can be asked the same question one after another, with each asking counting towards the limit.

Can you come up with a strategy that is guaranteed to work?

For years now, the evil mathematician wizard has been capturing and lining up groups of prisoners to let them guess the colors of the hats he put on them in exchange for their freedom. But since everybody nowadays already knows how to solve this problem, almost everybody escapes, prompting the wizard to come up with something more difficult. What if he used numbers instead of colors?

The next time he captures 1,000 prisoners, he lines them up in a row and gives everyone a hat with a positive integer written on it, subject to the following condition: The number of the first prisoner is at most 1, the number of the second one is at most 2, the number of the third one is at most 3, all the way to the 1,000th prisoner, whose number is at most 1,000.

Everything else is as usual:

• The prisoners are asked to guess the number of their hat in the order they are standing in.
• Every prisoner can only guess a number that is in the set of possible numbers for that prisoner.
• Every prisoner can only see the numbers of the prisoners that come after them, but they can hear the guesses of everyone.
• After everyone has guessed, the wizard frees those who guessed correctly and imprisons forever those who did not.
• The prisoners know the rules of this "game" and are allowed to agree on a strategy in advance.

What is the maximal number of prisoners that can be guaranteed to be freed?