# Dice-Game with two-twenty sided dice.

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?

-
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. – User011123521 Apr 23 '14 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 '14 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. – User011123521 May 7 '14 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 '14 at 15:27
Yup, so we can conclude that there is no way to end with 1 answer every single time. – User011123521 May 7 '14 at 15:28

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.
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.