In this week's post, we learn about Winning Positions for Combinatorial Games.

How would you use Winning Positions to solve the following problem? >

In Worked Example 2, how many winning positions are there on a \( k \times n \) grid?

In this week's post, we learn about Winning Positions for Combinatorial Games.

How would you use Winning Positions to solve the following problem? >

In Worked Example 2, how many winning positions are there on a \( k \times n \) grid?

No vote yet

16 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestLet \(T(k,n)\) denote the number of winning positions on a \(k \times n\) grid. The top row always ends in … W W L W W L W W L, and whether this row starts with a W or with an L depends on \(n\).

\[ T(k,n) = \frac{2}{3} \cdot k \cdot n \quad \left( \text{if }n \equiv 0 \pmod{3} \right). \]

\[ T(k,n) = k\left(\frac{2(n-2)}{3}+ 1 \right) \quad \left( \text{if }n \equiv 2 \pmod{3} \right). \]

\[ \text{the }t\text{-th row is} \begin{cases} \begin{align*} \text{L W W L W W L […] W W L}&\quad \left( \text{ if }t\text{ is odd}\right) ,\\ \text{W W W W W W […] W W W}&\quad \left( \text{ if }t\text{ is even}\right) . \end{align*} \end{cases} \]

In all even rows, there are \(n\) winning positions. In all odd rows, there are \(\frac{2}{3}\cdot(n-1)\) winning positions. So,

\[ T(k,n) = \left \lfloor \frac{k}{2} \right \rfloor \cdot n + \left \lceil \frac{k}{2} \right \rceil \cdot \frac{2(n-1)}{3} \quad \left( \text{if }n \equiv 1 \pmod{3} \right). \]

Whew. – Tim Vermeulen · 4 years, 1 month ago

Log in to reply