Return to Revisions

It seems to me that the problem is indeterministic which probably means I'm missing something. At the very least, it's too loosely worded.

If 50% of the peasants get to heaven and peasants all know the numbers $1-5$, that means that the numbers is in the set $[1-5]$ 50% of the time and in the set $[6-32]$ 50% of the time.

Peasants will guess all the numbers in the set $[1-5]$ in some order. We know they don't perform a binary search like the robots because, if they had, they would always get it right by the 3rd guess (or not at all). We know they got it right with equal probability for each guess to they either pick the numbers randomly or simply count from $1$ to $5$ with the devil saying "Higher" each time.

As suggested in the comments, a machine is likely to use a dichotomic search. That means they're going to start with the midpoint ($16$) and keep choosing the next midpoint based on whether the devil says the answer is higher or lower. In practice, that would look like this:

First:                                                              16                                                          
Second:                             8                                                               24                          
Third:              4                               12                              20                              28          
Fourth:     2               6               10              14              18              22              26              30  
Fifth:  1       3       5       7       9       11      13      15      17      19      21      23      25      27      29      31

Note that $32$ is never chosen by the robot. It would need a 6th guess to get that one. (It would know the answer by the 5th guess ($\log_232=5$) but it wouldn't have an opportunity to actually say it.) For any other number, the robot is guaranteed to get it by the 5th guess. Since only 50% of the robots get it right, that means that $32$ is the answer 50% of the time.

Now comes the problem: We know the answer is $32$ 50% of the time and we know the answer is somewhere in $[1-5]$ the other 50%. We know the devil chose each with equal probability because of how the peasants were guessing. That means the final answer is $47$.

Caveat:

There are problems in the question's wording:

1. We're only assuming that each peasant can count to 5 but, based on the wording of what the peasant said, it's more likely that most can't.
2. The devil, being not so very nice, could have had a different scheme for the robots and peasants. There's no reason why, when it's a peasant, he picks $[1-5]$ 50% of the time and $[6-32]$ 50% of the time while for a robot he picks $[1-31]$ 50% and $[32]$ 50%. The final answer can be anything between $33$ and $528$.
3. If the peasants guess randomly in the set $[1-5]$, then it's possible for the devil to pick, say, $3$ 50% and $32$ 50%. Depending on when they peasants randomly guessed $3$, that gives the 20% / guess result. The final answer can be anything between $33$ and $47$.
4. The robots could have picked 17 as their midpoint which can shift which number(s) they'll never guess. In that case, the answer can be anything be as low as $19$.
5. The peasants can only count to $5$ but that doesn't mean they don't know other numbers exist. It's possible for the devil to pick a number higher than $5$, the peasant randomly guesses $5$ first, the devil says "Higher", and the peasant says, "Uhhh... 14?". The wording only implies that the peasant doesn't know numbers higher than $5$.