Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

EDIT: I'll give this another try, trying to be clearer.

The game is played like this: Player A roles two-twenty-sided dice and multiplies the two integers together to get some integer, say x, with $ 0\lt x\leq 400$. Player B is then given six questions and a final guess to determine the integer x. Furthermore, three of these questions must be "Over/Under" questions (e.g. Is x over/under 200?) and the other three must be yes/no questions (e.g. Is x even?). From these six questions player B will have eliminated $alot$ of numbers and then can take one final guess at the number. My question to $Math.StackExchange$ is, can you solve this game to have one number remaining after the six questions, so that you would be correct on your final guess $every$ time?

My work on the game:

First, all primes greater than 20 are eliminated since their prime factorization is $p*1$ where $p>20$. Similarly, all multiples of these primes are eliminated since they are of the form $m*p$ where $p>20$. Further eliminations leave us with only $152$ possible integers that can occur. By looking at the distribution of numbers then you can determine that 60 is the most common integer, at about 2.5% of time. Also, 1 is the least common integer since the $\underline{only}$ way to "get" 1 is $1*1$.

So I have determined through a binary search tree, given the nature of over/under questions, you can eliminate numbers by half each time, or more than half if the guessing number is odd. That is, you start with $152 \rightarrow 76 \rightarrow 38 \rightarrow 19 \rightarrow 10 \rightarrow 5 \rightarrow 2$. Leaving us with 2 options $every$ time. Is there any better solutions?

share|improve this question
    
theoretically speaking if you could eliminate half the numbers each question you asked, you would get to no greater than 5 numbers left but it's easy to see that you can get less than this if you ask certain questions that eliminate more than half. –  Jonathan Mckibbin Apr 23 at 0:46
    
When you go from $5$ you might have $3$ left, so you can't guarantee to end with $2$ unless your question has three possible answers. Usually you are only allowed "is it above $n$" so a no answer includes exactly $n$. No, there isn't a better answer for the worst case. Your work on probability is correct, but not useful if you are interested in the minimum number of remaining possibilities. I showed in my answer a way to improve the chance of a unique answer at the price of having many left if you are unlucky. –  Ross Millikan May 7 at 14:06
    
That's the beauty of the over/under questions, if you guess on the number, it is a push, and you win. So for example if you have the numbers 1,2,3,4,5 left and guess over/under on 3, if its under you have 1,2; if its over you have 4,5; if its 3, you get a push and win. –  Jonathan Mckibbin May 7 at 15:25
    
Then you could also go $19 \to 9 \to 4 \to 2$ but you still don't get to $1$ –  Ross Millikan May 7 at 15:27
    
Yup, so we can conclude that there is no way to end with 1 answer every single time. –  Jonathan Mckibbin May 7 at 15:28

2 Answers 2

You have to decide whether you want the best chance to get a unique value, or the worst case number of possibilities. There are $152$ unique products that can be produced. As $2^6=64$, in the worst case you can guarantee getting down to $2$ or $3$ numbers after $6$ questions. For a reasonable shot at finding a unique number, ask first if it is less than or equal to $35$ (as it can't be $23,29,31$). If so, binary search will win for you. If not, ask if it is less than or equal to $57$ and four more questions will get you there. Then $72, 78, 81, 84$. This gets you a unique result $\frac {201}{400}$ of the time.

share|improve this answer

The best you can hope for is $\left\lceil\operatorname{lg}(152)\right\rceil=8$ guesses in the worst case. If you are limited to 6 questions, you won't be able to guarantee a correct answer, in which case the game becomes maximizing your chance of winning.

You could, for example, split off the 32 most likely cases (accounting for 161 of the 400 possible rolls). If it's one of them, do a binary search. Otherwise, ask if it's one of the next most likely 16 (44 cases) or failing that one of the next 8 most likely (16 cases). Probably by carefully picking which cases you took you could use over/under to get 3 or 4 more with those, for a total of about 225-226 out of 400.

share|improve this answer

Your Answer

 
discard

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

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