15
$\begingroup$

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}}}$

$\endgroup$
7
  • $\begingroup$ Is that one blank on each line? $\endgroup$
    – f''
    Mar 8, 2016 at 1:28
  • $\begingroup$ Yes............ $\endgroup$ Mar 8, 2016 at 1:29
  • $\begingroup$ So they're each 1 digit? $\endgroup$
    – Z. Dailey
    Mar 8, 2016 at 1:41
  • $\begingroup$ a number with 3 digits + a number with 3 digits = a number with 3 digits $\endgroup$
    – Varon
    Mar 8, 2016 at 1:44
  • 1
    $\begingroup$ A one digit number + a one digit number = a one digit number $\endgroup$ Mar 8, 2016 at 1:51

5 Answers 5

17
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I like your answer, better than mine :) $\endgroup$
    – Oray
    Mar 8, 2016 at 9:53
  • 1
    $\begingroup$ It would be nice if you could explain a little more why "the problem must contain a <insert digits here>". $\endgroup$ Mar 9, 2016 at 20:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Miles
    Mar 10, 2016 at 3:35
5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$ Mar 8, 2016 at 2:32
  • $\begingroup$ 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. $\endgroup$ Mar 8, 2016 at 2:35
  • $\begingroup$ 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) $\endgroup$ Mar 8, 2016 at 2:41
  • $\begingroup$ 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) $\endgroup$
    – lenwe
    Mar 8, 2016 at 3:29
  • $\begingroup$ @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$ $\endgroup$ Mar 8, 2016 at 3:44
3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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... $\endgroup$
    – Z. Dailey
    Mar 8, 2016 at 3:11
  • $\begingroup$ Mine too. He's got the most efficient. $\endgroup$
    – Z. Dailey
    Mar 8, 2016 at 3:14
  • 1
    $\begingroup$ In the case $3+5=8$, it seems like you lose four tokens, on the guesses 1, 2, 4, and 6. $\endgroup$ Mar 8, 2016 at 3:23
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 8, 2016 at 3:45
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 8, 2016 at 3:47
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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