# The devils number

You are in a room tied to a chair. The devil tells you that he is gonna ask two groups of 1000 "people" a question and then he will ask you something. If you answer correctly you go to heaven, else you go to hell.

He steps back a bit and a dirty man pops into the space to the devils left side out of thin air. He looks scared and is crying, his clothes are dirty and just look like rags like from middle ages. From the best of your knowledge he could be from the middle ages. The devil tells the man that he has to guess a number between 1 and 32 (including both) and that he has 5 tries. After every guess he will know if the guessed number was bigger or smaller than the one the devil had in mind. If he answers correctly he can go to heaven, if not he goes to hell. The man cries and says that he barely knows someone who can count to 5. The devil doesn't care.

Suddenly a glass barrier is erupted between you and the devil; you can't hear anything but you can still see what's going on. After the man opened his mouth for the fifth time a trap door opens and he falls down into the fiery depths.

The glass barrier disappears and the devil summons a half robot half human looking thing to his right side. The robot/human doesn't indicate that he feels anything or is scared. The devil asks him again the same question. The robot says that its impossible to answer this correctly he also adds that he is a deterministic being and doesn't like using randomness. Again the devil doesn't care.

The glass barrier is erupted again. After the robots speaker lights up for the fifth time, he is also thrown down into hell.

This procedure goes until 1000 peasants and 1000 robots have come through. You counted all the results and came to the surprising result that around 50% of the peasants and robots actually went to heaven! You also counted the number of guesses it took the candidates if they got the correct number. For the peasants it was completely random, 20% chance that they succeeded on the first guess, 20% on the second etc... The robots, on the other hand, guessed correctly only at the third, fourth, or fifth guess; never sooner.

Now the devil comes over to you and asks you: "If you add up all the numbers I chose, without duplicates, what do you get?"

Some clarifications:

• Around 50% of the peasants survived and around 50% of the robots survived
• For the sake of clarifying things, the devil choose a different number then the one before after each person (he can still choose 1,2,1,2 etc., just different from the one before)
• The devil didn't say he is gonna choose a number at random, he follows a system obviously
• It's not 448
• The peasants don't know the number 32 even though they just heard it
• The peasants always count from 1 to 5
• Dichotomic search, I choose you! – Narmer Apr 29 '15 at 12:35
• To clarify the question: If the Devil chose the number 6 500 times and the number 5 500 times, then the sum without duplicates would be 11? – Engineer Toast Apr 29 '15 at 12:42
• @EngineerToast yep – Vajura Apr 29 '15 at 12:46
• The number is the same for both a peasant and a robot or the devil choses one for each every time? – Narmer Apr 29 '15 at 13:13
• @Vajura Please to add some clarifications to the question. It's too broad as is and is up for closure. – Engineer Toast Apr 29 '15 at 14:11

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.

We can safely conclude that the robots did not pick $17$ as the first midpoint. They are deterministic and do not like randomness so we can assume they all followed the same scheme. Similarly, it follows that, had they picked the higher midpoint, then they would have always picked the higher midpoint. That means the lower half would split at $17$, $9$, $5$, $3$, $2$. In that case, they would have never chosen $1$ as an answer instead of never choosing $32$. However, they could have solved for any number $[2-32]$. If 50% of the robots go to hell, that means that the devil picked $1$ 50% of the time. This contradicts with what we know based on the peasants' pattern. Therefore, we reject $17$ as the first midpoint.

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: (All have been clarified by OP)

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$.
• Why are you excluding numbers 6-31? The 50% of peasants who did not make it to Heaven and the 50% of robots who did could have easily had a number between 6 and 31. – Bailey M Apr 29 '15 at 13:06
• @Engineer Toast. It is stated that the robots that guess correct always guess it on the third try. This indicates that the number [1-5] must be 4 because that number is on the third try as you can see in your diagram :) – Ivo Beckers Apr 29 '15 at 13:08
• @BaileyM No, because 50% of the robots go to hell so it must be $32$ 50% of the time. 50% of the peasants live so it must be $[1-5]$ 50% of the time. That's 100%. – Engineer Toast Apr 29 '15 at 13:08
• @BaileyM The 50% of robots that go to heaven are when the number is $[1-5]$. The 50% of peasants that go to hell are when the number is $32$. – Engineer Toast Apr 29 '15 at 13:13
• Why can't 17 be the midpoint of [1,32] instead of 16? – leoll2 Apr 29 '15 at 13:18

Middle-age men can only count up to $5$,so they choose a number between $1$ and $5$. Since they have a $50%$ chance of surviving, we deduce that the devil guessed a number between $1$ and $5$ half the times, and a number greater of $5$ the other times.
Every robot is asked the same question of his previous peasant, meaning that the devil guessed the same number for the robot and the middle-age man.
An intelligent robot would use a binary search algorithm to identify the number, starting from $16$ or $17$. After one wrong attempt, they try $8$ or $9$ or $24$ or $25$ (depending on what the devil answered). After a second wrong attempt, they try $4$, $12$, $20$ or $29$, and so on, until they find the number. Since the robots have always failed to identify the number with the first two steps, we deduce that the devil never guessed $8$, $9$, $16$,$17$, $24$, $25$.
Among the remainings, we can't know which ones he chose, he could have chosen just one or all. If only one, we get the the minimum sum, which is $1+2+3+4+5+6+7=28$ If all, we get the maximum sum (all the numbers except the excluded ones), which is $429$

• Asking the same question doesn't imply that the devil is thinking of the same number. "Can you guess my number?" is the same question both times. (Interestingly, this made me notice that the devil never asks a question. He just says guess my number or go to hell.) – Engineer Toast Apr 29 '15 at 13:27
• @EngineerToast In which case the number is always 6 – Vincent Apr 29 '15 at 13:32
• @VincentAdvocaat What? I don't see any connection between my comment and the number 6. – Engineer Toast Apr 29 '15 at 13:34
• @EngineerToast the devils number is 6 (or 666, the more well known variant) – Vincent Apr 29 '15 at 13:36
• @VincentAdvocaat Ah, ok. I see the joke now. – Engineer Toast Apr 29 '15 at 13:39