# October Problem of the Month

Congratulations to last month’s winner: Karl Schattle!  (There were several good solutions, but Shankar could only pick one.)  Now here’s this month’s problem:

Mr. Petrov’s Penguins

Mr. Petrov has mn penguins, and they all huddle around in a m x n rectangular grid. (1 penguin per grid square, and the borders of the grid run north-south and east-west).  At all times, each penguin faces one of four directions: north, south, east or west.   Further, these penguins are very social so that in any 2 x 2 subgrid, at least one of the penguins is facing one of the other penguins in this subgrid.

Despite this rigid social structure, and the fact that Mr. Petrov doesn’t have that many penguins, the grid of penguins seems to be in a different position every time Mr. Petrov goes out to feed them.  So he asks you the questions:

• (i) How many possible positions are there if m=n=2?
• (ii) How many possible positions are there if m=2, n=3?
• (iii) How many possible positions are there if m=n=3?

Submitted solutions should answer at least (i) and (ii) with explanations, and (iii) if possible.

[See the rules in the display case for more information.]