This was the last USAMO that I took as a high school student. I remember being very frustrated with this problem - I wasn't very well-educated about inequalities, so I was able to do #4 only after a couple of hours of effort. That would have left only an hour or so for this problem. Also, I think I misinterpreted the problem as saying that the first player is only allowed to write the letter S and the second player can only write the letter O. I recently worked on this problem some more (ahh, nostalgia!), this time using the correct interpretation of the problem. Here is the solution I came up with. I don't know if the out-of-high-school-for-well-nigh-a-decade crowd is allowed to post here. If not, feel free to remove this post. But I felt a deep sense of joy when I found this solution and I hope I can share that with the interested reader. [redacted - I will repost this tomorrow]

Let's call the first player A, the second player B. B's strategy is as follows: On his first turn, place an S in a square far away from both ends of the board and A's first counter. On his second turn (unless he can finish an SOS somewhere), place an S three squares to one side of his first S, and if A has put his second counter 'near' B's first, make sure it is on the other side from this one. After this, B follows the following algorithm: If he can finish an SOS somewhere, do so. Otherwise, if there is an empty square with a square each side empty, put an O in it. Otherwise, where there is an empty square with neither adjacent square empty, put an O in it. [Whenever B plays, there are an odd number of empty squares, so at least one of the above is always possible]. If I have got it right, it should be fairly apparent that A cannot win with B following this. To ensure that B actually wins- At the beginning, B created a sequence of four squares that went S-empty-empty-S. At some point, A must place an O or S in one of these squares: then B just has to put the other one in the other empty square and he wins.

Is there also a winning stategy for the first player, player A? gr, C

By the definition of winning strategy (a strategy that one player can follow such that she can win regardless of the actions of all other players), the number of players who can have winning strategies is at most the number of possible simultaneous winners. Since at most one player wins this game, at most one player can have a winning strategy.

The second player wins. The strategy is to place an S on his first turn far enough away from the ends of the board and the first player's first move, and play an S three boxes down on the next move. Note that if anyone is ever forced to play in one in a pair of boxes between two S's (S/_/_/S), let this be a domino of death, the other player will automatically win on the next turn, and furthermore it is impossible that the original player can win. We will prove that the only way for anybody to play such that the other player wins on the next turn is if he is forced to play in a domino of death. We claim that if there is an empty box that is not in a domino of death, the person whose turn it is can either (a) win or (b) play in such an empty box such that the other player can't win on the next turn. If the player P has the chance to win, then he can just win. Thus, if he can't win and furthermore has to play such that the other player Q wins on the next turn, the Q's SOS must include the letter that the P played. We have 3!=6 cases. For example, P plays the first S, Q plays the O. We seek all situations such that if P played O instead, Q still could have won. Basically, the board is going to look like _/_/S before P plays, and O/_/S in the alternative strategy. If this still allows Q to win, then it must be because there's an S in the middle and an S to the left of an O; we have a domino of death. The other five cases work the same way, we find that we need Q to have played in a domino of death. Note that the second player in our game can always avoid playing in a domino of death because he always plays with an odd number of boxes available (as 2000 is even), and dominoes of death contain two boxes each, with one box only being a member of at most one domino of death. Thus, there's at least one un-paired empty box and thus at least one box not part of a domino of death for the second player to play in.

Nothing new here, but I love this problem

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. $\blacksquare$ 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. $\blacksquare$ 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 \[X_1(-)^{a_1}X_2(-)^{a_2}\cdots (-)^{a_n}X_{n+1}\]where $X_i$ is a string of S and Os that starts and ends with S (except maybe $X_1$ and $X_{n+1}$ that could start and end with O respectively), and has no substring of the form SOS, and $a_i\ge 2$ for all $i$. If any of the $a_i\ge 3$, then Bob should simply put an S in the first - in $(-)^{a_i}$. It is easy to see that this adds no winning substrings, so it suffices to examine the case $a_1=\cdots=a_n=2$. But this means that the number of squares placed so far is $2000-2n$, which is even, so it can't even be Bob's turn! Therefore, we are done. $\blacksquare$ Lemma 1 implies that there is no draw, and lemma 3 implies that Bob won't lose, so Bob must win. QED

If we generalize $2000$ to $n$, the first player wins for all odd $n(\geq7)$ and the second player wins for all even $n(\geq14)$ The rest becomes a tie, checking the remaining cases.

My second combinatorics solution here Let the players be X and Y. In Y's first move, place an S far from the boards corners and X's move. Remember, whenever SOS possible, do it. In second move create a S[][]S next to the first move, in case X played something near the first move, play the second S in the opposite side. Now do either: 1) If x[]x (x=S or O) then put O. 2) If [][][] then put O in middle. This is possible because there are odd squares after X plays. Continuing like this X must once put a S or O in the S[][]S, then Y wins.

OH YEAHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH I GET IT NOW NOOOOOWWWWWWWW IT MAKES SENSSEEEEEEEEEEEEEEEEE whatever A plays, B plays >3 squares away from all sides and >5 squares away from A a letter S. Obviously if A threatens to win then B wins, so henceforth assume A is never one move from winning when it's B's turn. Next move B can guarantee to place another S three spots away from the first S. Now he can just fill up the rest of the board accordingly by spamming Os wherever there are three empty spots (he places it in the middle), or wherever both spots are occupied. Note that if he runs out of moves in this algorithm, he can just place an O next to another O, and if he runs out of these moves, the config is made up of some blocks of [block]xx[block=SOO...OOS]... etc., so everything is filled except for some areas of SxxS. However, in each one of these, there are an even number of unfilled, so actually, it must be 1's move. Now wherever 1 moves in one of these blocks player 2 just moves the opposite type in the other x, and wins.

Call a nuke a set of two squares filled with $S$ that have exactly two squares between them. We call a square exposed if there exists a neighbor of that square which is not yet filled. Claim: The second player can always construct a nuke. Proof: No matter what the first player plays on his turn, the second player can pick an empty square and fill it with $S$, such that the two squares a distance of $3$ from that square are both unoccupied. On the first player's next turn, he can only fill one of those squares, so the second player can fill the other square, hence building a nuke. $\blacksquare$ Now the second player plays detente and just makes sure he doesn't die. In particular, he adopts the following strategy: If there exists an exposed $O$ square, he fills a square adjacent to it with $O$; If there exists an exposed $S$ square that is not part of a nuke, he fills a square adjacent to it with $S$. Claim: The second player can always make such a move or win on his turn. Proof: If he cannot make a move, this means that all remaining exposed $S$ squares are part of nukes, and no $O$ is exposed. In particular, adjacent unfilled squares must come in groups of $1$ or $2$. But if there exists an isolated unfilled square, it must be surrounded by two $S$ squares, so the second player can win by playing $O$ in the middle. If all adjacent unfilled squares come in groups of $2$, then there are an even number of unfilled squares remaining, so it can't be the second player's turn! $\blacksquare$ Claim: The second player never enters a losing position by playing either move. Proof: This is easy to check: the second player never creates an adjacent pair of $O$ and $S$ squaers or two $S$ squares with one square in between. If such a pair existed on his turn, he can win immediately; thus he never enters a losing position. $\blacksquare$ It follows that when the second player can no longer make one of the two moves, the first player will get nuked on his next turn because there is at least one nuke. GG. Remark: I apologize for the existential flavortext; I was inspired by the problem statement.