View the board position as a string of the characters S,O,-. Call the players Alice and Bob.

We prove a series of lemmas to prove that Bob will win if both players play optimally.

Lemma 1: Bob can make sure that there is some turn of his where the board has a substring S--S.

Proof of Lemma 1: If Alice opens with placing an S somewhere, then Bob simply places another S to get the substring S--S somewhere. We're not done yet since it is now Alice's turn. But if she plays in one of the two blanks in the S--S, it is easy to see that Bob wins, so Alice must play outside the --. Therefore, it is Bob's turn, and the substring S--S exists.

Now, assume she instead opens with playing an O somewhere. Bob should then place an S far from the O and the edges of the board (fifty squares from the O and the edges should suffice). Alice won't play so that Bob can complete an SOS, since she is playing optimally, so she plays something else. Now, on Bob's second move, he has two ways to make the S--S, but at most one of them could lead to a winning position for Alice because of her second move. So he just plays the one that won't lead to a winning position for Alice, so Alice's third turn is not a win, so Bob's third turn arrives with the substring S--S existing somewhere on the board.

An important consequence of this lemma is that the game will now not draw - eventually someone must play in the blanks in S--S, and then they lose.

Lemma 2: Once Bob has S--S somewhere, Bob can have the ends of the board to be filled on one of his turns.

Proof of Lemma 2: Suppose Bob has S--S and it is his turn, and WLOG Bob can't immedeatly win (else game over). If an edge square is empty, by putting an O on the edge, Bob adds no winning positions, so Alice makes a move that doesn't finish, so its Bob's turn again. Thus, Bob can fill up the edges.

Lemma 3: If Bob can't win on a turn, then he can play so that he will be around to play another turn.

Proof of Lemma 3: Suppose there is a substring of the form -O or O-. Certainly if Bob adds an O to make them OO, then he could not have added any new winning substring (a winning substring is SO-, S-S, or -OS). Thus, WLOG assume that there are no substrings of the form -O or O-.

Thus, the board looks like
where is a string of S and Os that starts and ends with S (except maybe and that could start and end with O respectively), and has no substring of the form SOS, and for all . If any of the , then Bob should simply put an S in the first - in . It is easy to see that this adds no winning substrings, so it suffices to examine the case . But this means that the number of squares placed so far is , which is even, so it can't even be Bob's turn! Therefore, we are done.

Lemma 1 implies that there is no draw, and lemma 3 implies that Bob won't lose, so Bob must win.

QED

We claim that wins except for where the game draws.

The right way to think about this problem is the following. Players and are placing tokens on an grid ('s tokens and 's tokens are distinguishable). A player cannot play a token next to a token they played before. A player loses if they cannot play on their turn, and its a draw if all the squares get filled up.

WLOG, assume doesn't play square (if she does, then flip the board). We have the following wondrous lemma.

Lemma: If plays square on his first turn, then she is guaranteed to not lose (it may draw however).

Proof of Lemma: On the th turn of player , there are tokens on the board, and there is one token all the way to the left of everything. These tokens create so called "holes" - basically the region between two consecutive s. Since the s can't be next to each other, these holes have nonzero size (they might be filled with s). But there are only s potentially in these holes (because one is at - the point was to safeguard this ), so there is some hole with no s in it. Therefore, has some place to play, so doesn't lose. Note that does not have to play in that hole - all we're saying is that worst case, always has somewhere to play.

From this we can resolve almost all cases for .

Claim 1: If is odd, then wins.

Proof of Claim 1: Assume that does not win. Again, we assume does not play . should now play , and by the lemma, the game must draw. But this means played all squares, so to not have any adjacent ones, she must have played on all the odds. But played on an odd, so we have the desired contradiction.

Claim 2: If is even, then wins. The idea is the same as Claim 1, but the details are a bit more involved.

If doesn't open with playing or , then plays on or to match the parity of 's move. By the same argument as in claim 1, wins. Therefore, WLOG plays . Now, should play . By the lemma, the game draws (we're going by contradiction I suppose). If plays something less than , then the squares are accessible to , and one of them has got to be even. should play that and then win by the same logic as in claim 1.

Therefore, s second move must be . Now, if , then the squares have an even number, and can play there, and win by the same argument as in claim 1.

It suffices to resolve the cases . We see that are obviously draws. It is not too much harder to do a brute force check (check the relatively small tree of game outcomes) that are also draws. So we're done.

The idea in both goes like the following:
Player 2 sets up stuff in the beginning. Then we show that player 2 can always live another turn without losing. Finally, the set up in the beginning plus parity shows that Player 1 actually can't win, so player 2 must win.

Note that in the C4 its even better - player 2 can make a move to in fact not lose no matter what she does. In the USAMO problem, player 2 still has to be careful to live another turn.