2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What is $k$? (just above question 1) $\endgroup$
    – user5810
    Nov 7, 2011 at 4:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Nov 7, 2011 at 4:54
  • $\begingroup$ @Ricky Demur $k$ is just the number of best-worst case solutions for a particular interval [a,b] $\endgroup$
    – Alex R.
    Nov 7, 2011 at 5:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Alex R.
    Nov 7, 2011 at 16:09
  • $\begingroup$ 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? $\endgroup$ Nov 7, 2011 at 19:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.