Guessing game with guess cost - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T09:59:32Z http://mathoverflow.net/feeds/question/80267 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80267/guessing-game-with-guess-cost Guessing game with guess cost Alex R. 2011-11-07T03:54:06Z 2011-11-07T03:59:59Z <p>This is a question about <a href="http://projecteuler.net/problem=328BlockquoteBlockquote" rel="nofollow">Problem 328</a> 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 <em>analytic</em> 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.</p> <p>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:</p> <p>$C(a,b) = \min_{p\in [a,b]} ( p + \max${ $C(a,p-1),C(a,p+1)$ } $)$</p> <p>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$.</p> <blockquote> <p>Question 1: can it be shown that the pivots of $T_i$ are all the same? </p> </blockquote> <p>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$?</p> <p>In my current algorithm I have observed the following behavior of pivots for $C(1,n)$:</p> <p><img src="http://i.imgur.com/BL68Z.jpg" alt="alt text"></p> <p>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. </p> <blockquote> <p>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?</p> </blockquote> <p>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. </p>