A friend of mine is attempting to make a webpage that has a game for a 2x2 grid that is similar to the old North, South, East, West game. I cannot for the life of me figure this out.

Essentially, the game would do this. A player starts on coordinate (0,0) and moves around the grid. This grid coordinate would be white while the rest are black. Here is a diagram:

$$ \begin{align} &WB \\ &BB \end{align} $$

Once a the player moves, things change. When a player moves from a square, that square becomes yellow. Here is a new diagram to illustrate this (moving from (0,0) to (0,1)):

$$ \begin{align} &YW \\ &BB \end{align} $$

Once a player uncovers a square, the square cannot be black again. Also, the coordinate (0,0) can never be black (since the player starts there). There can only be one white square at any given time.

My friend (and now I) wants to know how the number of permutations/combinations of outcomes of the colors of the squares. I have tried, but I just cannot seem to understand how this would work. The best I could come up with was:

$$ \begin{align} &4^2-1 = 15 \end{align} $$

I derived this from the fact that each box can only be one of two colors at any given time and the first box cannot be one of those colors (black). Is there a better way to approach this? Is there a more general way that will work for different sized grids (3x3, 4x4, and etc)?

  • $\begingroup$ ignoring the rules of movement for the time being, as I understand, only one square is white, every other square has the ability to be black except the first, all others that aren't black or white will be yellow. Apply a case argument: either the first square is the white one or it isn't. If first square is white, going clockwise pick the color of the square (black or yellow) for each. $2\cdot 2\cdot 2=8$. If first square is not white, pick which one is (3 options). Then, first square must be yellow, determine the remaining two squares. $3\cdot 2\cdot 2 = 12$ for a total of $8+12=20$. $\endgroup$ – JMoravitz Apr 18 '15 at 22:25

If I have understood the rules of your game, the configuration of the board, depends on the particular movements that make the player. I'll number the squares like this:

$$\begin{align} &12 \\ &34 \end{align}$$

The following paths yield different color configurations of the board: 1, 12, 13, 121, 124, 131, 134, 1213, 1242, 1312, 1343. That makes $11$. These paths don't cover the whole board, that is, there are black squares left.

If you pass through every square, every square is yellow, except one that is white. There are $4$ possibilities for the square that is white. So there are $15$ possibilities.

I have assumed that diagonal movements are not allowed.

For a $n\times n$ board, the problem seems very difficult, because the yellow squares must form a connected set. I don't know how to count connected sets in a board.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.