Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. In particular, I am interested in analytic results about the cost function in the problem. Thus far, this question has been highly resistant to any analytic results on my part. Notice that I am NOT asking for an algorithm that solves this question. Let me first establish some terminology.

First let's generalize the game to an interval $[a,b]$ instead of just $[1,n]$. Define $C(a,b)$ to be the best-worst-case cost of searching through interval [a,b]. The most obvious recursive approach to the problem would be to notice that if the first guess is $p$, then:

$C(a,b) = \min_{p\in [a,b]} ( p + \max${ $C(a,p-1),C(a,p+1)$ } $)$

From here on, i'll refer to the first guess $p$ as the "pivot." Notice that any strategy of guesses can be defined as a binary tree $T$ where a leftward branch represents "your guess is higher than the hidden number" and the rightward represents "your guess is lower than the hidden number." In this way we can catalog the best-worst-case strategies, $T_1,\ldots,T_k$.

Question 1: can it be shown that the pivots of $T_i$ are all the same?

While the answer to question 1 is likely "no" without further assumptions, let me add this: I think that it may be possible to say "yes" if we allow reorganization of the sub-trees of $T_i$, by moving the desired pivot to the top of the tree. That leaves the question of what is the asymptotic number of pivots is for $C(1,n)$ for large $n$?

In my current algorithm I have observed the following behavior of pivots for $C(1,n)$:

alt text

Basically, the pivot for each successive $n$ goes up by 1 most of the time, except when an unbalancing occurs causing a drop. I suspect that the max function above tends to pick the right interval cost except at the drop points. For those interested, the drop points occur at 4,19,51 and so on, with the interval between drops growing exponentially.

Question 2: Can one show that compared to a previous pivot either $p$ must increase exactly by 1 most of the time or otherwise drop? Can these drop points be predicted asymptotically as $n$ grows?

Finally, it's easy enough to show right-sided monotonicity: $C(a,b) \leq C(a,b+1)$. What interests me is how $C(a,b)$ relates to $C(a+1,b)$. This would be related to question 2 as sudden switches of inequality here would likely signify a drop.

share|improve this question
    
What is $k$? (just above question 1) –  Ricky Demer Nov 7 '11 at 4:04
1  
I've seen Project Euler before, I would prefer, and I think they would as well, that consideration of their problems go through their site. –  Will Jagy Nov 7 '11 at 4:54
    
@Ricky Demur $k$ is just the number of best-worst case solutions for a particular interval [a,b] –  Alex R. Nov 7 '11 at 5:04
1  
@Will Jagy: I've seen the forum on this problem there but, there were no concrete replies to questions concerning research on this problem. Moreover, since I'm interested in more analytic results, I figured mathoverflow might be a better place. –  Alex R. Nov 7 '11 at 16:09
    
Alex, the OEIS returns a single "hit" for the sequence 4,19,51, with 106 as its next term. What is the next term in your sequence of drop points? –  Barry Cipra Nov 7 '11 at 19:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.