On an Erdős-Szekeres Game

This paper analyzes a two-player permutation game inspired by the Erdős-Szekeres Theorem, determining the winner and providing a winning strategy for cases where the parameter $a$ is greater than or equal to $b$ and $b$ is an integer between 2 and 5.

The Gist

Imagine you are playing a game with a friend involving a deck of cards, but instead of just shuffling and dealing, you are building a story one number at a time. This is the heart of the paper "On an Erdős-Szekeres Game" by Lara Pudwell.

Here is the story of the game, the math behind it, and the winning strategies, explained without the heavy jargon.

The Setup: The "Forbidden Pattern" Game

Imagine you and a friend are taking turns picking numbers from a hat. You write them down in a line, creating a sequence like: 3, 1, 5, 2, 4...

The rules are simple but tricky:

1. The Goal: You want to avoid creating a specific "forbidden pattern" for as long as possible.
2. The Patterns:
   • The "Up" Pattern: A sequence of numbers that keep getting bigger (e.g., 1, 3, 5). Let's say you are forbidden from making a line of 3 numbers that go up.
   • The "Down" Pattern: A sequence of numbers that keep getting smaller (e.g., 5, 2, 1). Let's say you are forbidden from making a line of 2 numbers that go down.
3. The Loser: The first person who is forced to complete one of these forbidden patterns loses. (This is called a misère game, like in the game of Nim where the person who takes the last match loses).

The Big Question: If you play perfectly, who wins? Does it depend on how long the "Up" pattern needs to be (let's call this number $a$) versus how long the "Down" pattern needs to be (number $b$)?

The Secret Weapon: The "Shaded Grid"

The paper's author, Lara Pudwell, realized that trying to track the actual numbers (like 3, 1, 5) is like trying to navigate a maze while blindfolded. Instead, she invented a visual map: The Grid Board.

Imagine a rectangular grid of empty boxes.

• The width of the grid is determined by how long the "Up" pattern can be.
• The height is determined by how long the "Down" pattern can be.

Every time you pick a number in the game, you don't just write the number; you shade in a specific box on this grid.

• If you pick a number that starts a new "Up" streak, you move right.
• If you pick a number that starts a new "Down" streak, you move down.

The Magic Rule: Once a box is shaded, all the boxes to its left and above are also considered "taken" (or eliminated). You can only shade a box that is right next to the edge of the shaded area.

The Winning Condition: The game ends when the grid is completely full. The person who shades the very last box (the bottom-right corner) wins, because that means the next player has no legal move left and is forced to break the rules.

Think of it like Chomp (a classic chocolate bar game) or Tetris, where you are slowly filling up a container. The person who is forced to take the last bite loses.

The Strategies: How to Win

The paper solves the game for specific scenarios. Here is the "everyday" translation of the winning strategies found in the paper:

1. The "Down" Pattern is Tiny ($b=2$)

If you are forbidden from making even a tiny "Down" pattern (just 2 numbers going down), the game is very rigid.

• The Strategy: You are forced to pick numbers that keep going up.
• The Winner: It depends entirely on whether the total number of moves is odd or even. It's like a coin flip based on the length of the game. If the "Up" limit is odd, Player 2 wins. If it's even, Player 1 wins.

2. The "Down" Pattern is Small ($b=3$)

Now you can have a tiny "Down" pattern of 3 numbers.

• The Strategy: Player 1 (the first player) has a guaranteed win.
• The Analogy: Imagine a two-lane highway. Player 1 acts like a traffic cop, ensuring that no matter what Player 2 does, Player 1 can always mirror the move to keep the lanes balanced. Player 1 forces Player 2 to eventually run out of safe spots.

3. The "Down" Pattern is Medium ($b=4$)

Now the "Down" pattern can be 4 numbers long. The grid is 3 rows high.

• The Strategy: Player 1 still wins, but the dance is more complex.
• The Analogy: Think of this as a game of "keep the balance." Player 1 maintains a specific shape of shaded boxes (like a staircase). No matter how Player 2 tries to disrupt the shape, Player 1 has a counter-move that restores the perfect staircase shape. Eventually, Player 2 runs out of moves.

4. The "Down" Pattern is Larger ($b=5$)

This is the big breakthrough of the paper. The grid is now 4 rows high.

• The Strategy: Player 1 still wins!
• The Discovery: This was the hardest part. The author used a computer to simulate thousands of games to find a "safe zone." She identified seven specific shapes (patterns of shaded boxes) that Player 1 should aim for.
• The Analogy: Imagine Player 1 is a shepherd guiding a flock of sheep (the game state). No matter which way Player 2 tries to scatter the sheep, Player 1 has a specific "herding technique" to bring them back into one of the seven safe shapes. Once the game gets to the very end, Player 1 uses a "tit-for-tat" strategy (copying the opponent's move in a different lane) to force the win.

Why Does This Matter?

You might ask, "Who cares about a number game?"

1. It's a Puzzle Solver: This game is a fancy way of testing the limits of order and chaos. The famous Erdős-Szekeres Theorem (from 1935) says that if you have enough numbers, you must eventually find an "Up" or "Down" pattern. This paper asks: "How long can we delay that inevitable moment if we play perfectly?"
2. It's a New Way to Think: The author showed that instead of thinking about complex numbers, you can think about shading boxes on a grid. This visual approach makes it much easier to see the winning moves.
3. It's a Teaching Tool: This game helps students understand deep mathematical concepts (like permutations and patterns) by turning them into a fun, strategic board game.

The Bottom Line

The paper proves that if you are playing this game and the "Down" pattern limit is between 2 and 5, the first player (Player 1) can always win if they know the secret grid-shading strategy.

• For small limits ($b=2$), it's a coin flip based on length.
• For medium limits ($b=3, 4, 5$), the first player is the master of the board, using a "mirror and balance" technique to trap the second player.

The author essentially turned a scary math theorem into a solvable board game, showing that even in a world of chaos, there is always a winning path if you know how to look at the grid.

Technical Summary

Here is a detailed technical summary of the paper "On an Erdős-Szekeres Game" by Lara Pudwell.

1. Problem Statement

The paper investigates a two-player combinatorial game inspired by the classic Erdős-Szekeres Theorem.

• The Theorem: Any permutation of length $n \ge (a-1)(b-1) + 1$ contains either an increasing subsequence of length $a$ ($I_a$) or a decreasing subsequence of length $b$ ($J_b$).
• The Game: Two players take turns selecting numbers from the set $\{1, \dots, n\}$ to build a permutation.
  • Misère Play (Primary Focus): The first player to complete an $I_a$ or $J_b$ pattern loses.
  • Normal Play (Secondary Focus): The first player to complete an $I_a$ or $J_b$ pattern wins.
• Parameters: The game is defined by integers $a$ and $b$ (where $a \ge b$). The game ends when the permutation length reaches $(a-1)(b-1) + 1$ or a pattern is formed earlier.
• Context: Previous work by Harary, Sagan, and West (1983) and Albert et al. (2009) analyzed this game using computer-aided state analysis and ternary word representations. However, their analysis was limited by computational resources for larger $b$, and they primarily focused on normal play or small parameters.

2. Methodology

The author introduces a novel geometric grid-shading model to represent game states, moving away from the permutation notation or ternary words used in prior literature.

• The Board Representation:

  • The game is modeled on a grid of size $(b-1) \times (a-1)$.
  • Cells are indexed by $(c, r)$, where $c$ is the column (related to the length of the longest increasing subsequence ending at the current element) and $r$ is the row (related to the longest decreasing subsequence).
  • Shading Rule: When a player adds an element to the permutation, they shade a specific cell $(c, r)$.
  • Elimination Rule: If cell $(c, r)$ is shaded, all cells $(c', r')$ where $c' \le c$ and $r' \le r$ are considered "eliminated" (hatched). These cells cannot be shaded in future turns.
  • Winning Condition (Misère): The player who shades the bottom-right cell $(a-1, b-1)$ loses because shading this cell implies the board is fully eliminated, forcing the next player to create a forbidden pattern. Conversely, the player who forces the opponent to shade the final cell wins.
  • Connection to Chomp: The game is identified as a variant of the combinatorial game Chomp, where players remove cells from a grid.

• Strategic Approach:

  • The paper analyzes the game by defining specific sets of board configurations (states) that constitute winning positions (Class $N$) or losing positions (Class $P$).
  • For $b \in \{2, 3, 4, 5\}$, the author constructs explicit winning strategies for Player 1 (the first player) for the misère version when $a \ge b$.
  • The strategy involves maintaining the board in a specific "safe" set of states ($\mathcal{S}$) after every turn, ensuring that no matter what Player 2 does, Player 1 can return the board to $\mathcal{S}$ or force a transition to a winning endgame state ($\mathcal{E}$).

3. Key Contributions and Results

A. Visual Model and Equivalence

The paper establishes that the grid-shading model is equivalent to the ternary word model used by Albert et al. (based on Schensted's bumping algorithm). The grid model offers a more intuitive, geometric way to visualize the constraints of the Erdős-Szekeres theorem during gameplay.

B. Winning Strategies for Misère Play ($a \ge b$)

The author provides explicit winning strategies for Player 1 for $b \in \{2, 3, 4, 5\}$:

1. Case $b=2$:

   • The board is a $1 \times (a-1)$ strip.
   • Result: Player 1 wins if $a$ is even; Player 2 wins if $a$ is odd. The game is purely determined by the parity of $a$.

2. Case $b=3$:

   • The board is $2 \times (a-1)$.
   • Result: Player 1 has a winning strategy for all $a \ge 3$.
   • Strategy: Player 1 mirrors Player 2's moves to maintain a specific diagonal structure of shaded cells, forcing Player 2 into a position where they must complete the pattern.

3. Case $b=4$:

   • The board is $3 \times (a-1)$.
   • Result: Player 1 has a winning strategy for all $a \ge 4$.
   • Strategy: Player 1 maintains the board in one of two specific "forms" (defined by the number of eliminated cells in rows 1, 2, and 3) after every turn. The strategy involves specific responses to Player 2's moves to preserve these forms.

4. Case $b=5$ (Major Contribution):

   • The board is $4 \times (a-1)$.
   • Result: Player 1 has a winning strategy for all $a \ge 5$.
   • Novelty: This extends the known results beyond $b=4$. The strategy is complex and was derived via computer-assisted search.
   • Mechanism: The author defines a set of 7 "safe" states ($\mathcal{S}$) and 3 "endgame" states ($\mathcal{E}$).
     • Lemma 1: Player 1 can reach a state in $\mathcal{S}$ within the first 4 moves.
     • Lemma 2: If the board is in $\mathcal{S}$, Player 1 can always respond to Player 2's move to return to $\mathcal{S}$.
     • Lemma 3: Player 1 can transition from $\mathcal{S}$ to $\mathcal{E}$ (a state with open cells only in the final columns/rows) to force a win.
   • Complexity: The proof involves extensive case analysis based on the parity of open cells in specific rows, demonstrating that the strategy holds regardless of $a$.

C. Normal Play Analysis

The paper briefly addresses the normal play version (completing the pattern wins):

• The strategy is isomorphic to the misère strategy but played on a reduced board of size $(b-2) \times (a-2)$.
• Result: Player 1 wins for $4 \le b \le 6$. Player 2 wins for$b=2$. Parity determines the winner for$b=3$. This supports the conjecture in Albert et al. that Player 1 wins for$a \ge b \ge 4$.

D. Game Length and Position Counts

• Move Count: The paper analyzes the number of moves required. While the theoretical maximum is $(a-1)(b-1)+1$, the strategies employed often result in shorter games (e.g., for $b=5$, the game length is roughly between $2a$and$4a$).
• Class P Positions: Table 2 provides data on the percentage of board configurations that are losing positions (Class $P$). The data suggests that as $a$ increases (with fixed $b$), the percentage of losing positions decreases, though parity effects remain significant.

4. Significance

• Theoretical Advancement: This paper resolves the winning strategy for the misère Erdős-Szekeres game for $b=5$, a case previously considered computationally prohibitive to solve analytically.
• Methodological Shift: By introducing the grid-shading model, the author provides a powerful visual and geometric tool for analyzing permutation pattern games, simplifying the complex logic of subsequence tracking.
• Extension of Combinatorial Game Theory: The work bridges the gap between classical combinatorial theorems (Erdős-Szekeres) and modern combinatorial game theory (Chomp variants), offering a framework that could be extended to higher $b$ values, although the complexity of the state sets grows rapidly.
• Pedagogical Value: The visual representation makes the abstract concepts of increasing/decreasing subsequences and the pigeonhole principle more accessible for teaching and intuition building.

In conclusion, Pudwell successfully generalizes the winning strategies for a significant class of Erdős-Szekeres games, proving that Player 1 holds a winning advantage for $a \ge b$ and $b \in \{3, 4, 5\}$ in the misère setting, utilizing a novel geometric approach to manage the exponential growth of game states.