Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that $f$:$Z\rightarrow N$ is a surjection and $|f^{-1}(n)|=2$ for every $n\in N$. I found that there is $n\in Z$ such that $f(n)$, $f(n+1)$, $f(n+4)$, and $f(n+5)$ differ from each other. "Unavoidable structures" in title means pairs like (1,4,5). I want to know how to find all this kind of pairs.

I proved this when I was thinking about a game generalized based on Tic-tac toe. Differences from the original game are as follows:

  • This game is played on $1\times \infty $board.
  • The player who succeeds in placing respective marks in the given figure wins the game but the goal figure is not limited to be continuous.

When the goal figure is "X,X,(),(),X,X", paring strategy cannot prove that the first player cannot win. (Paring strategy is a second player's strategy. Divide the board into pairs.When the first player marks one part of a pair, then the second player mark the other one.)

My question is whether there is a method to find all the unavoidable structures.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.