The game is as follow:
Two players have a 1xN grid with empty spots with N bigger than 2. They, alternately, put a stone on a empty spot. The first one to complete a sequence of three or more stones on consecutives positons of the grid wins the game.
Given a N, I have to decide which player is going to win. In this case, I want to know if the first to play can win the game.
So, this is what I've thought so far:
I decided to create cases to N=0, N=1, N=2. I know that $N \geq 3$, but that made sense.
Case N = 0: In this case, the first one loses, because he can't do anything. So G(0) = 0
Case N = 1: In this case, the first one win, because the other one can't play. G(1) = Mex(0) = 1
Case N = 2: If I have the 1x2 grid like _ _ I can only put X _ . So, the only position I can go is to 1, then G(2) = Mex(1) = 0
And now comes the problem.
Case N = 3: I have the grid like _ _ _ . There is two possible ways I can put the stone:
X _ _ : That reduces the problem to 2. So Mex(G(2)) = Mex(0).
_ X _ : That is the moment I don't know what to do. Because I have two positions 1 now.
I thought to do XOR on G(1) and G(1): that would give me Mex(1 XOR 1) = Mex(0). So, G(3) = Mex(0) = 1. What makes sense, because the first player can win if N = 3.
However when I analyse N = 4 it doesn't work. Because, we would have
X _ _ _ $\rightarrow$ Mex(G(3)) = Mex(1)
_ X _ _ $\rightarrow$ Mex(G(1) XOR G(2)) = Mex(1 XOR 0) = Mex(1).
So, G(4) = Mex(1) = 0. That's wrong because the first player can win when N = 4.
I thought the Grundy Numbers theory kind confusing, so I might have made some assumptions that I shouldn't have made.
It seems like you're somewhat confused about Grundy Numbers (also called nimbers, for brevity) - you're defining them for objects that don't make sense (the game isn't really defined for $N=0,1,2$, so computing a Grundy number doesn't work), and saying that a move like X__ "reduces the problem to $2$" and then taking the Mex of $2$ is rather non-sensical - so let me begin by reviewing the moves that one is allowed to do with Grundy numbers. If we let $G$ be an impartial game (remembering that an impartial game is really just a set of legal moves - the elements of which are themselves games - and that a player loses upon having no legal move), and $f(G)$ be its Grundy number, the basic recursive calculation for $f$ is the following
So, if you have no better way to go about it, you can calculate the number by looking at every possible move. For instance, for the first interesting case $N=4$, there are only a few positions reachable from the start, where I use an O to indicate an empty spot and X to indicate a filled one and where I only list one of each pair of positions related by reflectional symmetry and I mark each with its Grundy number, which I will justify below by a full calculation:
We could start by noting that positions (10) and (8), by definition, have no further moves because the player receiving that position just lost. So their Grundy numbers are $\operatorname{mex}\{\} = 0$. Then (9) has Grundy number $\operatorname{mex}\{0\}=1$ since it can only move to (10) which has Grundy number $0$ and since (7) can only move to (8), it also has Grundy number $1$. (6) can only move to (9) so its nimber is $\operatorname{mex}\{1\}=0$. Both (4) and (5) can move to (8) or (9), which have nimbers $0$ and $1$ so nimber $\operatorname{mex}\{0,1\}=2$. Then (3) can move to (4) or (5) or (7), so has nimber $\operatorname{mex}\{1,2\}=0$ and (2) can move to (4) or (5) or (6) so has nimber $\operatorname{mex}\{0,2\}=1$ and finally (1) can move to (2) or (3) so has nimber $\operatorname{mex}\{0,1\}=2$, which tells you that this game can be won by the first player by always playing a move whose nimber is $0$ (i.e. OXOO then, regardless of what their opponent does, they'll win at XXXO).
Note that the things inside the mex are themselves Grundy numbers of a game! Just because you see an integer in a position doesn't mean that that's the thing that goes inside the mex.
Then, the other tool you have at your disposal is the following theorem
where $G\oplus G'$ is a game in which you can either make a move in $G$ or $G'$ at each turn. This does not seem immediately useful, since the game you give cannot obviously be split up this way - it is somewhat inevitable that, if you try to split the board, there is some three-in-a-row that hits empty spaces on both sides of the partition, which dooms this approach naively. Note that you can only use this once you've established that the game is truly a sum of two others - not when it looks like something split.
However, if we're only trying to determine who wins this game and not the exact Grundy number, there is hope - we can apply a reduction, then start using Grundy numbers on the reduced problems. In particular, note the following:
This is true since whenever this happens, their opponent can immediately make $3$ in a row. Thus, the game is equivalent to the following one:
Where a player loses once they are out of moves - meaning that in the original game, they would need to play in a way that causes them to lose.
This game does break down. In particular, if you label the cells as $\{1,\ldots,n\}$, then playing in the $m^{th}$ cell means that all further moves will either be in the interval $\{1,\ldots,m-3\}$ or $\{m+3,\ldots,n\}$ and the rules are identical to the original game in this interval. So, if we name the game with $n$ cells as $H_n$, we see that the position achieved after playing at the $m^{th}$ cell is equivalent to the game $H_{m-3} \oplus H_{n-m-2}$ where we should interpret non-positive indices as the empty game (which has nimber $0$). But this gets us somewhere! We can make a table of nimbers. First, note that if $n \leq 3$, then every move leads to a sum of two empty games, so $f(H_n) = 1$ for $1 \leq n \leq 3$. Then, for further cases, we get: $$f(H_n) = \operatorname{mex}\{f(H_{m-3}\oplus H_{n-m-2}) : m \in \{1,\ldots,n\}\}$$ which allows for quick recursive computation. Note that until $n=7$, only one of these games in the sum will be non-empty, so we easily get $$f(H_4) = \operatorname{mex}\{f(H_0), f(H_1)\} = 2$$ $$f(H_5) = \operatorname{mex}\{f(H_0), f(H_1), f(H_2)\} = 2$$ $$f(H_6) = \operatorname{mex}\{f(H_1), f(H_2), f(H_3)\} = 0$$ where the intuitive interpretation here is that, until $5$, playing in the center of the board leaves your opponent without a move, but at $6$, no matter what you do, you leave your opponent with a smaller non-empty set of legal moves - from which they will win.
The first real interesting case is $H_7$ where you get $$f(H_7) = \operatorname{mex}\{f(H_1\oplus H_1), f(H_2), f(H_3), f(H_4)\} = 3$$ which tells you, essentially, to play in the center, splitting the board into two segments of length $1$ - since you know that $f(H_1\oplus H_1) = 1\text{ XOR }1 = 0$. Then $H_8$ and $H_9$ are similar, except that the small pieces get bigger, but still have nimber $1$, so their sum has nimber $0$: $$f(H_8) = \operatorname{mex}\{f(H_1\oplus H_2), f(H_3), f(H_4), f(H_5)\} = 3$$ $$f(H_9) = \operatorname{mex}\{f(H_1\oplus H_3), f(H_2\oplus H_2), f(H_4), f(H_5), f(H_6)\} = 1$$ Then, $H_{10}$ is interesting again as we get the first time a nim-sum is not zero: $$f(H_10) = \operatorname{mex}\{f(H_1\oplus H_4), f(H_2\oplus H_3), f(H_5), f(H_6), f(H_7)\} = 1$$ where $f(H_1\oplus H_4)=1\text{ XOR }2 = 3$. You can continue on indefinitely in this manner, noting that now the particular Grundy numbers do matter because, eventually, you will need to compute properties of sums of games. I'm not sure if there is some pattern that emerges, but this does at least tell you that the first player wins for every $n\leq 10$ except $n=6$. Using a computer, the pattern in who wins seems pretty erratic; for instance, up to $n=10000$, the second player can win for exactly the following sizes: $$6, 12, 22, 30, 32, 44, 54, 64, 76, 86, 98, 110, 118, 130, 132, 162, 170, 184, 194, 202, 282, 290,$$ $$302, 356, 1046, 2502, 2752, 2912, 3052, 3076, 7250, 7356, 7866$$