This evening, while I was about to wash the dishes, I heard my elders starting a game (call them Him and Her)
Him: "I have picked - in my head - a number, lower than 50. Try to guess..."
Her: "No way, too difficult..."
Him: "You can try five different numbers..."
Her: ".,. um ... No, no way..."
Me: "Wait... each time we suggest a number, you tell us if yours is either above, or below ?"
You can see me coming clearly, can't you ? Using a simple subdivision rule, we have a fast algorithm (and indeed, if I have to choose between washing the dishes and playing with the kids...)
Him: "um.... ok"
Her: "Daddy, are you sure we will win ?"
Me: "Well... I cannot promise that we will win... but I am rather sure [sic] that we will win quite frequently: more gains than losses..." (I guess).
Her: "Great ! I am playing with daddy..."
Him: "um.... wait, is it one of you trick, again ? I don't to play anymore... Do you want to see the books we've chosen at the library ?"
Her: "Sure..."
Me: "What ? no one wants to see if I was right ? that we have indeed more than 50% chances to win..."
Him and her: "No !
The point of that story ? If we listen to kids, science will not go forward, trust me. But I am curious... I want to see if my intuition was correct. Actually, the intuition was based on the fact that
```> 2^5
[1] 32
> 2^6
[1] 64```
so in 5 or 6 steps the algorithm of subdivision should converge. I guess... I mean, I do not know for sure, since 50 is not a power of 2, so it might be difficult, each time, to split in two: we have to deal only with integers here...
To be sure, let us substitute my laptop to my son... to pick up numbers, randomly (yes, sometimes I feel like I am Doctor Tenma, 天馬博士). The algorithm is simple: there are bounds, and at each stop I should suggest the middle of the interval. If the middle is not an integer, I suggest either the integer below or the integer above (with equal probabilities).
```cutinhalf=function(a,b){
m=(a+b)/2
if(m %% 1 == 0){m=m}
if(m %% 1 != 0){m=sample(c(m-.5,m+.5),size=1)}
return(round(m))}```
The following functions runs 10,000 simulations, and tells us how many times, out of 5 numbers suggested, we got the good one.
```winning=function(lower=1,upper=50,tries=5,NS=100000){
SIM=rep(NA,NS)
for(simul in 1:NS){
interval=c(lower,upper)
(unknownnumber=sample(lower:upper,size=1))
success=FALSE
for(i in 1:tries){
picknumber=cutinhalf(interval[1],interval[2])
if(picknumber==unknownnumber){success=TRUE}
if(picknumber>unknownnumber){interval[2]=picknumber}
if(picknumber<unknownnumber){interval[1]=picknumber}
#print(c(unknownnumber,picknumber,success,interval))
};SIM[simul]=success};return(mean(SIM))}```
It looks like the probability that we got the good number is higher than 60%,
```> winning()
[1] 0.61801```
Which is not bad. And if the upper limit was not 50, but something else, the probability of winning would have been the following.
```VWN=function(n){winning(upper=n)}
V=Vectorize(VWN)(seq(25,100,by=5))
plot(seq(25,100,by=5),V,type="b",col="red",ylim=c(0,1))```

Actually, after losing a couple of times, I am rather sure that my son would have to us that we can suggest only four numbers. In that case, the probability would have been close to 30%, as shown on the blue curve below (where four numbers only can be suggested)
Anyway, as intuited, with five possible suggestions, we were quite likely to win frequently. Actually with a probability of almost 2 out of 3...and 1 out of 3 if my son had decided to pick an number between 1 and 100, or only 4 possible suggestions... Those are quite large actually, when we think about it. It reminds me that McGyver story I mentioned a few months ago... Anyway, calculating probabilities is nice, but I still have to wash the dishes...