Dtyjlui

Initially, the numbers $2,3,ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last number wins. Who has a winning strategy?

Note that this problem is different from a classical easy problem as $1$ is not initially on the board.

I don't know if this problem has a nice solution. I have checked all $nle25$ and found that Bob has a winning strategy only when $n=3$ or $n=7$. The following table lists all possible first steps in Alice's winning strategy when $nle20$. I have not found any patterns.

n=2: 2

n=4: 2

n=5: 4

n=6: 5 6

n=8: 2 5 7

n=9: 2 5 7

n=10: 4 6

n=11: 8 10

n=12: 2 5

n=13: 6

n=14: 10 11 12 13 14

n=15: 12

n=16: 14

n=17: 10

n=18: 5

n=19: 12 14

n=20: 4 5 6 9

“Graph theory” is included in the tags because this game can be reformulated on a graph where there is an edge from each number to all its divisors, and the players alternately remove a vertex together with all its neighbors.

You tried think its like a nim game? I hade this idea after tried to play this game. In a nim game you have a heap with a amount of items and each player in your turn must withdraw a amount of this items. Winning the game of nim traditional the player what have take the last item. So, the players can withdraw a amount of items per turn: 1, 2, 3, 4, ... In general a low number and this amount never changes during all game. But in your problem this amount changes each turn, because when the player A erase a number of the roll, others numbers, his divisors, is erase too. So, in the the turn of player B, he have less moves to do because the previous choice of A and, in the next turn of player A, he have less than player B hade, because of the previous choices. I called this games of limited nim Games.

Lets call the amount of items what each player can take per turn by k, that is: Per turn each player can withdraw k items of the heap. Soon k is constant in a normal nim game, but in a limited nim game k changes by a rule. In your complex problem the rule what changes k is: "When you erase a number of the roll, you must erase his divisors".

Lets take a example: Be n = 10. We have the following roll:

2, 3, 4, 5, 6 ,7 ,8 ,9 ,10

This is a heap with a amount of n-1 items and the fist player have the following choices:

1A) withdraw one number; it's happens when i is a prime, with i ∈ [2,n].

2A) withdraw two numbers; it's happens when i have three divisors, with i ∈ [2,n].

3A) withdraw three numbers; it's happens when i have four divisors, with i ∈ [2,n].

That is K=(1,2,3)

Lets see waht happens, when each choiceis made by the player A:
1A) is choicen: in this choice the player A withdraw one os the following numbers (2, 3, 5, 7), when he do it, depending on the number choicen the options 2) and 3) can changes.

I) choosing 2 implies all even number lost one divisor.

II) choosing 3 implies what all multiple of 3 have lost one divisor.

III) choosing 5 implies what all multiple of 5 have lost one divisor.

IV) choosing 7 not result in any alterations in this case.

So, elect 1A) leaves the next player with the following choices:

1B) withdraw one number; one of the following number (2,3,5), or (2,3,7), or (2,5,7), or (3,5,7).

2B) withdraw two numbers; one of the following numbers (4,9), or (4), or (9).

3B) withdraw three numbers; one of the following numbers (6,8,10), or no have this option in the case of A choose 1A) - I).

Look, what k has changed to B, due to a choice of A. This will happen for all A's choices, and this has many possibilities for different results. If you do this problems with trees, i think its can be more clear to see. As n grows, the possibilities in the game moves increase exponentially, as the number of divisors increases and the amount of numbers with the same number of divisors increases as well.

Because of this, this game is tough to solve, find the best strategy is not a easy work, but i think this like is a nim game, so if i can win a nim game, so i can win this game just replicating the best strategy of a normal nim game with some alteration.

Hope i have helped with this idea.