10
$\begingroup$

This is a game inspired by other recent questions.

It is a 2-player game.

  • The game is played with 10 cards numbered 1 to 10 and 2 positions or stacks.
  • The game starts with all cards in stack 1.
  • The goal is to bring the total of stack 2 to 42.
  • Each player in turn takes one card from stack 1 and places it in stack 2.
  • If after a player's move the total in stack 2 is 42, that player wins.
  • If instead the total exceeds 42, then that player loses.
  • Since the total of the card values is 55, the game must eventually end.

Alice starts, followed by Bob. Who wins and what is the strategy?

It is not too difficult to work it out with a computer. But I am asking for a clear strategy, one that you could learn and apply mentally.

For example, if the target were 44, Bob could win by always playing (11-n) after Alice plays n. This way his moves would bring the total to multiples of 11 until it reaches 44.

But we want to reach 42.

I added the no-computer tag. You can use a computer to analyze the game, but I won't accept a program or computer-generated decision tree as a solution.

$\endgroup$
4
  • 1
    $\begingroup$ Are we guaranteed that such a clean strategy exists? $\endgroup$
    – Fluorine
    Apr 20 at 1:37
  • 1
    $\begingroup$ I know of one I could explain in less than a minute. $\endgroup$
    – Florian F
    Apr 20 at 8:59
  • $\begingroup$ where I'm from there is only one way to take a card from a stack, and that's to take the card that's on top. But surely that's not what is meant here? $\endgroup$
    – njzk2
    Apr 21 at 11:48
  • $\begingroup$ No, indeed, the players can take any card they like. You can call it a heap if you want. $\endgroup$
    – Florian F
    Apr 21 at 14:39

2 Answers 2

8
$\begingroup$

Alice

wins by

starting with 6 and then complementing Bob's cards to 12 as closely as possible. For example, if Bob plays 9, Alice responds with 12-9 = 3. If Bob never plays 1 then the game ends after Alice's 4th move at 42 exactly. Bob can force cards 1, 1 and 2 or 1 and 2 and 3 to be played at some point. Alice's strategy will land the score at 41, 40 or 39 points after her 4th move in these cases. Because small numbers have already been used Bob's next move will end at 43 or higher.

Examples:

A6,B1,A10,B2,A9,B3,A8 sum 39, leftover cards 4,5,7

A6,B10,A2,B9,A3,B1,A8 sum 39, leftover cards 4,5,7

A6,B7,A5,B4,A8,B1,A10 sum 41, leftover cards 2,3,9

$\endgroup$
2
  • $\begingroup$ Just curious, can it be proven (or if needed, shown by computer) that Alice's first move has to be the one you let her take to inevitably succeed with? $\endgroup$ Apr 21 at 0:44
  • $\begingroup$ @FirstNameLastName If Alice starts with a lower card, then Bob can fill in all of 1-5 and will win with his 4th move. If she starts with a higher card it's more messy, but Bob can force a win there. $\endgroup$ Apr 21 at 11:32
3
$\begingroup$

In complement to the very neat answer by Albert, I wanted to show the graph of the game (open in a separate tab, it is big):

enter image description here

A state of the game is defined by the cards in stack 2, and is represented by a node in the graph. Arcs indicate you can go from one state to another with a legal move. On each node I've put the sum of stack 2, I would've added the set of cards in stack 2 if it was not unreadable. Since Alice starts, she has the nodes in the odd layers and Bob in the even layers (at layer 0 it is just the start of the game). This is not the full graph of the game, but rather one that shows the winning strategy for Alice. A winning state is a state where the sum is 42 if it is in the Alice layer or where the sum is greater than 42 if it is in the Bob layer. Then we propagate following the rules:

  1. If a node has all its successors losing, then it is a winning state
  2. If a node has one of its successors winning, then it is a losing state

Then if the first state is losing then Alice can win all the time, and if it is winning then it is Bob that will win all the time.

In the graph, since the first state is losing, from it I left all the successors of a node if it was winning, and only the winning successors if it was losing. We can see the strategy Albert gave easily on this graph, with for example the starting point being picking 6.

All in all, props to Albert.Lang for having it solved!

$\endgroup$
4
  • $\begingroup$ A winning state only needs to have one of its successors losing. $\endgroup$
    – Bass
    Apr 20 at 16:53
  • 2
    $\begingroup$ @Bass If there is at least one successor not losing opponent can choose such successor and win. $\endgroup$ Apr 21 at 0:50
  • $\begingroup$ @FirstNameLastName but it's not the opponent's turn, so they don't get to choose. (To clarify, positions are usually considered from the perspective of the player whose turn it is.) $\endgroup$
    – Bass
    Apr 23 at 10:57
  • $\begingroup$ @Bass Then the states at 42 should also be losing. Here I considered the state resulting of your choice to be yours, clearly marking the states where you reach 42 as winning $\endgroup$
    – Fluorine
    Apr 23 at 11:26

Your Answer

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

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