Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Addition Hangman is a game for two players. The rules are

  • The first player (the Chooser) chooses an addition problem $x+y=z$, where $x$, $y$, and $z$ are positive integers. He writes the addition $x+y=z$ in base $10$, replaces each digit by a blank space ($\underline{\hspace{8mm}}$), and shows the result to the second player.

  • The second player (the Guesser) starts off with some number of tokens. She may risk a token in order to guess a digit. If the guessed digit appears anywhere in the addition, the Chooser fills in the appropriate blank space(s), and the Guesser keeps her token. If the guessed digit does not appear, the Guesser loses her token.

  • The Guesser wins if all of the blank spaces are filled in. The Chooser wins if the Guesser runs out of tokens.

Question: The Guesser receives the addition problem $$ \begin{array}{cc} &\underline{\hspace{8mm}}\\ +&\underline{\hspace{8mm}}\\\hline &\underline{\hspace{8mm}} \end{array} $$ Each blank represents a (not necessarily distinct) digit between $1$ and $9$. What is the smallest number of tokens the Guesser needs in order to be certain she can win?

$\newcommand{\bl}{\underline{\hspace{8mm}}}$

share|improve this question
    
Is that one blank on each line? – f'' Mar 8 at 1:28
    
Yes............ – Julian Rosen Mar 8 at 1:29
    
So they're each 1 digit? – Z. Dailey Mar 8 at 1:41
    
a number with 3 digits + a number with 3 digits = a number with 3 digits – Varon Mar 8 at 1:44
1  
A one digit number + a one digit number = a one digit number – Julian Rosen Mar 8 at 1:51
up vote 17 down vote accepted

The Guesser can guarantee a win with 4 tokens.

  1. Guess $1$. If it's a match, but the solution is still ambiguous, the problem must contain a $3$, $5$, $7$, or $9$ so those can be guessed in order, losing at most three tokens.
  2. If the first guess was a miss, guess $3$. If it's a match, but the solution is still ambiguous, the problem must contain a $5$, $7$, or $9$, so those can be guessed in order, losing at most two additional tokens (for three lost total).
  3. If the first two guesses were misses, guess $2$. If it's a match, but the solution is still ambiguous, the problem must contain $6$ or $7$, so those can be guessed in order, losing at most one additional token (for three lost total).
  4. If the first three guesses were all misses, we're down to our last token. But the problem must contain $4$, so we can guess that, which will reveal the solution (either $4 + 4 = 8$ or $4 + 5 = 9$).

There are some variations possible (for example, $3$ can be guessed before $1$, or the follow-up guesses after a $3$ match could be $4$, $5$, $6$). There's no way to guarantee a win with 3 tokens, because there's no set of three digits such that every possible solution contains at least one digit from the set.

Here's a flowchart representation of the guessing strategy, with all possible solutions to the $\_ + \_ = \_$ problem:

Flowchart representation of guesses and all possible solutions

Italicized numbers represent blanks that have only one possible way to fill them. Green rightward lines lead to possible outcomes for matching guesses, and red downward lines are taken when there's no match. Note that every solution is reachable with at most three incorrect guesses.

share|improve this answer
    
I like your answer, better than mine :) – Oray Mar 8 at 9:53
1  
It would be nice if you could explain a little more why "the problem must contain a <insert digits here>". – GentlePurpleRain Mar 9 at 20:07
1  
@GentlePurpleRain I didn't really have a concise way to explain why without listing out every possible solution, so I've added an image that does that. – Miles Mar 10 at 3:35

I can do it with five tokens.
Guess $4$. If you find $4+\_=\_$, guess $5,6,7$ until you find one.
Guess $6$. If you find one, guess $3,2,1$.
Guess $2$. If you find $\_+2=\_$ guess $5,1$
Guess $8$ and you are guaranteed to find one, so do not lose a token. If you find $\_+8=\_$ it is $1+8=9$. Otherwise, it is $1+7=8$ or $3+5=8$ One more guess

share|improve this answer
    
For first scenario, you still have to account for 1+8=9 (but I think you're still fine if you simply get the 8 out of the way in the beginning, since you'll know where the 8 is) – Dennis Meng Mar 8 at 2:32
    
Yes, but if I don't find $4,6,2$ I won't lose a coin on the $8$, then if the $8$ is an addend I am set, so I only lose three coins. If the $8$ is the sum I can lose one more, but am still home with five coins. I added that in. – Ross Millikan Mar 8 at 2:35
    
Do you mind spelling out that half of the proof? Just to make it easier for everybody reading later. You still technically have to spell out the 4 and 6 cases too (but given your history in math.stackexchange I assume you already know those and just need to write it out) – Dennis Meng Mar 8 at 2:41
    
After guessing 2 (third token), guessing 5 and 1 may be incorrect if it's 2+7=9. It would be better if you guess with 3 (for 2+3=5 or 2+1=3). If 3 is incorrect, then guess with 7 (for 2+5=7 or 2+7=9) – lenwe Mar 8 at 3:29
    
@lenwe: my approach succeeds, as I don't lose a token for $2$. You are right that yours reduces the maximum loss in this branch to $3$ – Ross Millikan Mar 8 at 3:44

I think it can be done with 4 5.

Guess 1 first. If you hit ($1+1$) you're done, if you hit ($1+\_$) the remaining options for $(z,y)$ are:

$(9,8)$ $(8,7)$

$(7,6)$ $(6,5)$

$(5,4)$ $(4,3)$

$(3,2)$

Then, guess $8,6,4$ and you will know the answer with certainty.

If $1$ yields $(\_+\_)$ guess $2$, again $(2+2)$ and you're done, $(2+\_)$ means

$(9,7)$ $(7,5)$

$(8,6)$ $(6,4)$

$(5,3)$

Then guess $7,6$ and you're done.

If 2 yields $(\_+\_)$ then guess $4$. If you get $(4+4)$ you're done. If you get $(4+\_)$ then the options are

$(7,3)$ $(9,5)$

Guess $7$ and you're done.

If $4$ yields $(\_+\_)$ the answer must be $(3+\_)$ with options

$(9,6)$ $(8,5)$ $(6,3)$

Guess 6 and you will know the answer with certainty.

share|improve this answer
    
actually he covered that... 1 yeilds 1 + _ then guess 8,6,4 up to that point he would lose 3 and still not have the answer but the only remaining option is 2 and 3... – Z. Dailey Mar 8 at 3:11
    
Mine too. He's got the most efficient. – Z. Dailey Mar 8 at 3:14
1  
In the case $3+5=8$, it seems like you lose four tokens, on the guesses 1, 2, 4, and 6. – Julian Rosen Mar 8 at 3:23
1  
I intended the rule to be that the guesser loses as soon as they lose their last token, even if at that point they know what the missing digits are – Julian Rosen Mar 8 at 3:45
1  
@JulianRosen: I think that was clear in your question. I think this answer uses fewer tokens than mine on average, but we tie on the worst case. – Ross Millikan Mar 8 at 3:47

From what I can tell there is a worst possible outcome of 6 coins.

Guess 2, 4, 6, and 9 and you will either get it or get nothing... if you get nothing you know it is 1 + 7 = 8 or 3 + 5 = 8, if you get 2, you can obviously figure it out. If you get 1, you know it is either 1 + 2 = 3, 1 + 3 = 4, 1 + 4 = 5, 1 + 8 = 9, 2 + 3 = 5, 2 + 5 = 7, 3 + 4 = 7.

therefore

it depends on what you picked up, but either way you guess the one that occurs the most for your respective situation you've landed in and you can't possibly get more than 2 more wrong. Therefore you can lose 5 coins and stay in the game.

share|improve this answer

My answer is 8.

The question states that the least number of tries by the Guesser but doesn't not factor in the intelligence of the said Guesser. So take for example if the solution was

1+1=2

and the Guesser guessed 9,8,7,6,5,4,3 he would need at least 8 tokens to be guaranteed a win. This I believe is the worst case scenario.

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.