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