6
$\begingroup$

Here is the problem. There is a number randomly chosen between 1~100. The player tries to guess that. If the guess is larger than true value, the player is punished by 'a' dollar. If the guess is smaller than true value, the player is punished by 'b' dollar. How much money the play should prepare in order to hit the number in the worst case? 1) a = 1, b = 1; 2) a = 2, b = 1; 3) a = 1.5, b = 1;

Here is where I am so far. For the first sub-question, the player would use binary tree and the worst case would be 7 guessing times (6 wrong and 1 right). Hence, the punish money would be 6*1 = 6 dollars. For the second sub-question, instead of separating the range by half, the player will separate the range according to the weight given by a and b, i.e. in this case the player would choose 33 for the first guess instead of 50. In this strategy, the worst case would cost the player 11 dollars(according to my calculation), while the binary method would cost the player 12 dollars. For the third question, the methodology is the same as second one.

My doubt is: is there another method which is better? The doubt comes from this fact: my method applied same to sub-question 2 and sub-question 3, which means the existence of sub-question 3 is meaningless. Clearly an author of a problem would not put that kind of sub-question.

appendix: I am not sure the problem in the link below would provide some hint, but they have something in common. http://datagenetics.com/blog/july22012/index.html

$\endgroup$
1
  • $\begingroup$ I want to express thanks to the two persons below who kindly provided their thought and explained them in detail. Just to express my opinion which is probably a reference for others, I would prefer the answer using recurrences since the logic is more universal and the solution is mathematically rigorous. The key point of the other answer is the thought "you would like to have the same range remaining after you spend $2, whether that comes from one high guess or two low ones", which is a great idea but it's difficult to apply what you learn here to other questions. Again, thanks to both of you. $\endgroup$ – Jason_Kim Dec 22 '17 at 3:01
3
$\begingroup$

Given $n$ dollars, we can solve an interval only if we can make a guess such that the interval less than the guess is solvable with $n - a$ dollars and the interval greater than the guess is solvable with $n - b$ dollars. So, let $f(n)$ be the size of the largest interval solvable with $n$ dollars. Then we have

$$ f(n) = f(n - a) + f(n - b) + 1 $$

and the interval from $1$ to $f(n)$ can be solved with a guess of $f(n - a) + 1$. The base case is $f(n) = 0$ for $n < 0$. This can easily be solved by hand for the numbers in question, or a general technique for solving recurrences can be applied. In case 2, each $f(n)$ is one less than a Fibonacci number.

$\endgroup$
6
  • $\begingroup$ Thank you for your reply. I got some question hoping for your answer. According to your reply, if a = 1 b = 1, f(6) = 63 and f(7) = 127. If f(n) means the size of the largest interval solvable with n dollars, n = 100 requires 7 dollars to solve, while binary tree gives the answer of 6 dollars. Please correct me if I am wrong or misunderstanding. $\endgroup$ – Jason_Kim Dec 19 '17 at 6:45
  • $\begingroup$ @Jason_Kim: $f(-1)=0$ (base case), $f(0)=1$, $f(1)=3$, $f(2)=7$, $f(3)=15$, $f(4)=31$, $f(5)=63$, $f(6)=127$. With $0$ dollars we can always solve $1$ because the first guess is correct and no penalty is paid. I gave the base case as $f(n)=0$ for $n < 0$ which is a little weird because $f$ is perhaps not well defined on this domain, but it means that the recurrence will never allow any path that would lead to a (strictly) negative dollar amount. $\endgroup$ – tehtmi Dec 19 '17 at 7:14
  • $\begingroup$ Thank you for your reply. I mistook f(0) as 0,which should be 1. So you are right and I've understand your point. I met another question. When a = 2 and b = 1, f(8) = 88 and f(9) = 143 according to your formula. Therefore n is equal to 9 if the sequence length is 100. Your first guess would be f(9-2)+1 = 55. Am I right? Please correct me if not. $\endgroup$ – Jason_Kim Dec 19 '17 at 8:28
  • $\begingroup$ @Jason_Kim That is correct, but there is flexibility in the first guess. It will work as long as the part lesser than the guess is less or equal to than $f(7)=54$ numbers and the greater part is less than or equal to $f(8)=88$ numbers. So you can guess between $100-f(8)=12$ and $f(7)+1=55$. $\endgroup$ – tehtmi Dec 19 '17 at 18:49
  • $\begingroup$ Thank you for your reply. So you mean it is the same to guess any number between 12 and 55 for first time? I would try that later. Also, would you like to give some comment for the first answer? It's quite benefitial to learn from some discussion in different view. $\endgroup$ – Jason_Kim Dec 20 '17 at 4:39
5
$\begingroup$

The strategy for large ranges must be to guess a number that is some proportion $p$ down from the top of the current range. For case $2,$ you would like to have the same range remaining after you spend $\$2,$ whether that comes from one high guess or two low ones. You guess low with probability $p$ and high with probability $1-p$. The chance of two low guesses in a row is $p^2.$ That means $p^2=1-p$, which says $p=\frac12(\sqrt 5-1) \approx 0.618$ so your first guess should be $100-0.618*99$ or $39$. I would have to think some more about how the granularity of the numbers impacts this, but if $39$ is too high the second guess seems like it should be $ 38 - 0.618\cdot 37$ which is close to $15$. Then $6, 3, 1$ gets you there for $\$9$ if the target is $2$. I leave the other cases to you to verify you don't spend more. For case $3$, the same logic says you shouldn't care if you get three lows or two highs, so $p^3=(1-p)^2$. Alpha solves this exactly, giving a mess that is about $0.57$, so your first guess should be $100-0.57*99$ or $44$

$\endgroup$
9
  • $\begingroup$ Thank you for your timely answer. I roughly understand your meaning after a glance and gonna have a careful check on it. Just to eliminate our information difference, what I meant is that higher guess results in larger punishment, while you understand it in the contrast way. $\endgroup$ – Jason_Kim Dec 19 '17 at 4:35
  • $\begingroup$ I think there might be some typo in your answer. Maybe they are not important for people who know this question but for a learner they are a bit misleading. For example, in third line it should be "whether that comes from two low guesses or one high" instead of "whether that comes from one low guess or two high ones".In sixth line, it should be "62+0.618*38" instead of "62+0.618*34". And your example gives 62 86 95 99 as guess, but I can figure out how does this cost $9. I would be appreciated it if you could correct them if I am right. Or correct me if I am wrong. $\endgroup$ – Jason_Kim Dec 19 '17 at 8:57
  • $\begingroup$ @Jason_Kim: you are right. I got high and low backwards. I have updated it with a few more details. See if this is clearer $\endgroup$ – Ross Millikan Dec 19 '17 at 15:53
  • $\begingroup$ Thank you for your reply. But I think there are still some unclear part in your answer. In the third line, it should be ''You guess low with probability p and high with probability 1−p''. Also, according to your meaning, shouldn't it be (1-p)^2 = p ? $\endgroup$ – Jason_Kim Dec 20 '17 at 2:41
  • $\begingroup$ You guess low with probability $p$ is what I said. It is correct because your guess is below $p$ of the numbers. Then I mistakenly said the chance of two lows in a row was $(1-p)^2$. It should be $p^2.$ That makes the equation $p^2=p-1$ correct. Intuitively your guess should be below halfway so you guess low more often than high and that is what comes out of the calculation. $\endgroup$ – Ross Millikan Dec 20 '17 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.