Colour $2$ or $3$ numbers that total $15$

Question

So my friend comes up and confidently says that he can defeat me in this game:

• The integers $1$ to $14$ are written down on a blackboard (paper in our case).
• Players take turns colouring (striking out in our case) $2$ or $3$ numbers that total $15$. They can only colour the uncoloured numbers
• The last player to colour a pair or a triplet wins the game

Since I don't want to lose, I figured I'll ask it here. Is there any strategy a player (which, first or second?) can employ to win the game? I have thought about it for a lot of time, but to no avail. So, I present a few sample games:
$(1,14),(2,5,8), (4,11), (9,6), (3,12)$. So, the first player wins.
$(4,5,6), (7,8), (10,3,2), (1,14)$ so second player wins.
I also calculated the number of solutions to $a+b+c = 15$, where $0 \le a < b<c\le 14$. There are $19$ such $(a,b,c)$.

Verified $19$ solutions using python. If they can be of any help:

1,14
2,13
3,12
4,11
5,10
6,9
7,8
1,2,12
1,3,11
1,4,10
1,5,9
1,6,8
2,3,10
2,4,9
2,5,8
2,6,7
3,4,8
3,5,7
4,5,6

PS: I see that the tag description about game theory matches my question, so I've used it. But please do not use complicated notation employed in game theory since I don't know much about it.

Answer 1

Theoretical background

For a game like this, there is only one theoretical idea from Combinatorial Game Theory we really need: The concept of "N-positions" and "P-positions". An N-position is a state where the Next player to move has a winning strategy. And a P-position is a state where instead the Previous player to move has one.

Two key facts:

1. Note that at the end of the game when there are no moves available, the previous player had a winning strategy of "make the move that ends the game like this", so it's a P-position.
2. In general, a position is a P-position when all of the moves are to N-positions. That is, any move (if one exists) would hand your opponent a win if they play perfectly. And, otherwise, the position is an N-position since a good move to make would be a move to a P-position.

If you prefer video, this idea is discussed at P-positions and N-positions: Introduction to Combinatorial Game Theory #2 by Knop's Course on YouTube.

---

Solution

(I will use "take" to mean "strike out".)

This game is probably just simple enough that it could reasonably be solved by hand with a decent amount of paper and time - just write out some branches of play, building up which states are N-positions or P-positions from below, until a promising line of play is found. But I used a program very similar to the Python mentioned below to analyze it.

The game is a win for the first player, who can win by taking any pair, or one of the triples $(1,6,8)$ or $(2,6,7)$.

It suffices to show that one of those moves is part of a winning strategy. For simplicity, consider the move of taking $(1,6,8)$, leaving $(2,3,4,5,7,9,10,11,12,13,14)$. Then there are seven things the opponent can take: $(2,13)$, $(3,12)$, $(4,11)$, $(5,10)$, $(2,3,10)$, $(2,4,9)$, and $(3,5,7)$.

• If they take $(2,13)$, the winning moves are $(3,12)$ and $(5,10)$. Either way, after one of those moves the remaining two moves are independent: $(4,11)$ and whichever is remaining of $(3,12)$ and $(5,10)$.
• If they take $(3,12)$ or $(5,10)$ one winning move is $(2,13)$ by the above. (Aside: $(4,11)$ is also a winning move.)
• If they take $(2,3,10)$, the only available move is $(4,11)$, leaving $(5,7,9,12,13,14)$, from which there are no more moves.
• If they take $(4,11)$, one winning move is $(2,3,10)$ by the above. (Aside: $(3,12)$ and $(5,10)$ are also winning moves.)
• If they take $(2,4,9)$ or $(3,5,7)$, the only winning move it to take the other of those triples, leaving $(10,\ldots,14)$ from which there are no more moves.

---

Python code

Since you mentioned Python, we can turn this idea of N and P positions into Python code. If moves gives a list of reachable states starting from the state s, then we can use #2 above to test if a state is an N-position:

def isNPosition(s): return not(all(map(isNPosition,moves(s))))

One way to define moves is to use a set of numbers (so that striking out is easy), as in:

import itertools
def moves(s): return [s-set(x)\
 for x in list(itertools.combinations(s,2))+list(itertools.combinations(s,3))\
 if sum(x)==15]

Since the game is so short with not too much branching, this can evaluate whether any state (including the starting state) is an N-position very quickly.

import itertools

def moves(s): return [s-set(x)\
 for x in list(itertools.combinations(s,2))+list(itertools.combinations(s,3))\
 if sum(x)==15]

def isNPosition(s): return not(all(map(isNPosition,moves(s))))

print("The game is a win for the first player:",isNPosition(set(range(1,15))))

print("(1,6,8) would be a bad first move:",isNPosition(set(range(1,15))-set([1,6,8])))

#list which first moves are good/bad with "False"/"True"
for x in map(lambda s : ("The first move of:"\
,sorted(list(set(range(1,15))-s)),\
"leads to an N-position?",\
isNPosition(s)),\
moves(set(range(1,15)))): print(x)

Try it online!

Answer 2

Sorry for my previous wrong answer. Now, I believe this one is correct, although ugly and seems not generalizable.

Player 1 can always win. He does that by coloring 1,6,8 first. Now, the possible moves for player 2 are coloring:

2,13
3,12
4,11
5,10
2,3,10
2,4,9
3,5,7

Suppose that player 2 chooses 2,3,10. Now, player 1 chooses 4,11 and wins.

Suppose that player 2 chooses 2,4,9 (3,5,7 resp). Now player 1 chooses 3,5,7 (2,4,9 resp) and wins.

Suppose that player 2 chooses 2,13. Now, player 1 chooses 3,12. Now, player 2 chooses 4,11 (5,10 resp). Now, player 1 chooses 5,10 (4,11 resp) and wins.

Suppose that player 2 chooses 3,12. Now, player 1 chooses 2,13. And the remaining game is analogous to the previous case.

Suppose that player 2 chooses 4,11. Now, player 1 chooses 2,3,10 and wins.

Suppose that player 2 chooses 5,10. Now, player 1 chooses 4,11. Now, player 2 chooses 3,12 (2, 13 resp). Now, player 1 chooses 2, 13 (3, 12 resp) and wins.

Answer 3

I think this approach works as well:

The first player takes $(5,10).$

Now, all the possible remaining pairs or triples can be listed as follows:

$$\ \{ (1,14), (9,2,4)\} \\\{ (2,13), (8,3,4)\}\\\{ (3,12), (7,2,6)\}\\\{ (4,11), (8,1,6)\}\\\{ (6,9), (11,1,3)\}\\\{ (7,8), (12,2,1)\}.$$

Whatever the second player takes, the first player needs to take the other element of the same set. For example, if the second player takes $(6,9)$, the first player should take $(11,1,3)$. In this way, in each case, only two possible pairs remain, which implies that the first player wins.

---

For example, if $(12,2,1)$ is taken by the second player, then the first player takes $(7,8)$, and $(6,9)$ and $(4,11)$ are possible available pairs.

Answer 4

This cries out for generalization. Consider the game with $15$ replaced by $n$, i.e. we start with the numbers $1$ to $n-1$ and each player removes $2$ or $3$ numbers summing to $n$. Unless I've made a mistake, the first player has a winning strategy for $n = 3, 4, 6, 7, 8, 10, 11, 12, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 40 \ldots$, while the second player has a winning strategy for $n = 1, 2, 5, 9, 13, 18, 22, 25, 31, 32, 39, 41 \ldots$. These sequences don't seem to be in the OEIS (yet).

EDIT: The sequence of $n$ where the first player wins is now in OEIS as sequence A361457.