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...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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.

Log in to reply