The specifics of my assignment are as follows:
The following simple game can be played by two players. First, mutually agree on a starting number and the player who will take the first turn. On your turn, "split" the number into three prime numbers. (That is, name three prime numbers that sum to your number.) Your opponent must then select one of the three named primes to be the next number, and they take the next turn. If, on your turn, you are unable to split your number into three primes, you lose.
Gameplay Example I take the first turn with 23 as my number. I can split it into five possible combinations: 2+2+19, 3+3+17, 3+7+13, 5+5+13, or 5+7+11. I choose 5+7+11. My opponent selects 11 as the next number and splits it into 3+3+5. I select 5, but I cannot split it into the sum of three primes and so I lose.
If we want to consider all possible paths of choices, there are exponentially many to keep track of. However, we can assume that both players are trying to win, so if player A has a choice between making a move that guarantees their loss and one which guarantees their win, we can safely assume they will choose to win.
For each starting number, determine which player wins the game under optimal play. Prove that your analysis is correct using induction. You will probably want to use structural induction for this problem.
I thought this would be very simple to solve, but I'm struggling with it. Without loss of generality, let's assume Person 1 (P1) always goes first. In order for P1 to win, they need to pick a "winning" number that can be divided into 3 "losing" numbers. For example, let's consider the first few primes as starting numbers and see if P1 wins:
2:L (NA)
3:L (NA)
5:L (NA)
7:W (2+2+3)
11:W (3+3+5)
13:W (5+5+3)
17:L (2+2+13)
19:L (3+3+13)
23:W (3+3+17)
29:W (5+5+19)
31:L (7+7+17) (Two winning primes and 1 losing prime)
37:W (3+3+31)
41:W (19+19+3)
43:W (19+19+5)
47:L (17+17+13)
53:W (3+3+47)
There is no discernable pattern that I can see in the wins/losses or in the numbers themselves. If someone could provide insight into this I would be very thankful.