9
$\begingroup$

Alice and Bob are playing a game. They take an integer $n>1$, and partition the set $\{1,2,...n\}$ into two non-empty subsets $A,B$. Alice takes the set $A$ and Bob takes the set $B$. They take a paper and write $0$ on it. Alice plays first, and the rules are:

Each turn, let $x$ be the number written on the paper. The player has two choices:

  • Erase $x$ and rewrite $0$ on the paper, or
  • Choose a number $y>x$ to remove from their set, then erase $x$ and write $y$ on the paper.

The game ends if a player's set becomes empty, and that player wins the game.

Question: For which subsets $A$ of $\{1,2,...n\}$ does Alice have a winning strategy, and what is the number of such sets?

I think the best strategy for both players is to choose the smallest element possible that can be played from their set, except if the other player's set has only $1$ element, in which case they choose the largest element in their set. But I can't prove it or describe the winning sets for Alice using that strategy.

Update: The above strategy doesn't work, as @aschepler points out: for $n=6$, $A=\{1,4,5\}$, $B=\{2,3,6\}$, Alice wins by initially choosing $4$ or $5$, but not $1$.

$\endgroup$
11
  • 3
    $\begingroup$ Given what you say in the last paragraph there seems to be something in the rules that are not currently stated. (Like they must have $y>x$?) $\endgroup$
    – Qise
    Sep 25, 2023 at 11:31
  • 1
    $\begingroup$ Just to clarify : For a given $n$ , we want to charaterize the subsets $A$ for which Alice has a winning strategy , right ? $\endgroup$
    – Peter
    Sep 25, 2023 at 11:36
  • 3
    $\begingroup$ Your strategy causes Alice to lose if $A = \{1,4,5\}, B = \{2,3,6\}$, but Alice can win by instead playing $4$ or $5$ first. $\endgroup$
    – aschepler
    Sep 25, 2023 at 12:58
  • 2
    $\begingroup$ Observation: Curiously, this is equivalent to the simplest form of Climbing game, with no multi-card combos, for $2$ players. I.e. you must play a card which beats the previous card, or pass (write $0$). If you pass, your opponent can lead any card. Whoever plays all cards first wins. This family of games is very common in China. One version popular in the west is Tichu. $\endgroup$
    – antkam
    Sep 29, 2023 at 0:41
  • 4
    $\begingroup$ I've written a fairly simple Python script to calculate the winner... of the initial $2^n-2$ partitions where neither $A$ nor $B$ is empty, I find that the first player wins in the following number of cases: $2,5,9,20,41,78,162,314,630,1254,2476,4971,9806,19670,38960,77907,\ldots$. (This is for $n=2$ through $n=17$.) The sequence doesn't appear to be in the OEIS. The fraction of cases won by the first player seems to converge to about $3/5$. $\endgroup$
    – mjqxxxx
    Oct 3, 2023 at 3:45

1 Answer 1

2
+25
$\begingroup$

Not a complete answer, but here are some thoughts. For two players, the hands are open as we know the starting sets and we can track what's remaining at each point. With 3 or more players, the game could have unknown information, making the strategies less deterministic. As an aside, this game is similar in mechanics to 6 nimmt! / Take 6!.

Winning States for Alice

  1. a) It is Alice's turn, b) Alice has one number left, and c) the current number is less than Alice's number. The basic case.
  2. a) All of Alice's remaining numbers are greater than Bob's, and b) Bob is not in a winning state. Alice can simply play in any order, and Bob is forced to do 0 everytime
  3. a) Alice has $n$ and one other number, and b) Bob is not in a winning state. Alice plays $n$, Bob is forced to 0, Alice plays her final number.

So one approach is to try to end up in a winning state like the above, and avoid reaching a winning state for the opponent. For example, if you have only one number greater than your opponent's smallest, then don't spend it unless you're about to win. My hunch is the player with $n$ is more likely to have a guaranteed winning strategy.

When playing with humans, playing $1$ 'psychologically' forces the opponent to play a number (even though they could do 0, it's unlikely they'll pass on the freebie). Although I can't actually think up a situation where that is useful.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .