Problem Solved!

Congratulations to the winner of the problem of the month for October, Nathan Beck!

For those interested, a solution follows.  For the original problem, see here.

(i) First consider the case of a 2×2 grid of penguins.  In this case, it’s easier to count what’s not being asked for than what’s being asked for.  Without any restrictions, there are 4 penguins, each of which can be in 4 positions making for 4^4=256 possible positions without the subgrid condition.  The condition that at least 1 penguin must be facing one of the other penguins is violated exactly when all of the penguins are facing outside of the grid.  In this case each penguin has 2 possible positions, making for 2^4=16 unallowed positions.  Thus the total number of positions with the subgrid restriction is 256-16=240.

(ii) Now consider the case of a 2×3 grid.  Again, we want to count what’s not being asked for.  There are 4^6=4096 possible unrestricted positions.  There are 2 2×2 subgrids giving restricted conditions here, the left subgrid and the right subgrid.  By (i), we know there are 16 unallowable positions for each subgrid.  So the number of positions which violate the left subgrid condition is 16*4^2=256 (the unallowed positions on the left times the possible positions for the 2 penguins on the right).  Similarly, the number of positions which violates the right subgrid condition is also 256.

At this point, you might like to say this means there are 256+256=512 unallowed positions, but that’s not quite right as we will have double counted some unallowed positions, namely those configurations which violate both the left and right subgrid conditions.  Well, how many of these are there?  Violating both the left and right subgrid conditions means the top middle penguin must be facing up and the bottom middle penguin must be facing down, and each of the 4 outside penguins can be facing 1 of 2 outward directions.  Hence there are 2^4=16 positions which violate the both the left and right subgrid conditions, and our final answer is 4096-256-256+16=3600 possible penguin positions.

This basic counting technique is called the inclusion-exclusion principle, and is useful in lots of combinatorial problems.

(iii) Once you know how to do (ii), you can figure out (iii), which is the case of a 3×3 grid, similarly, though the double counting gets a little more complicated (hint: think of it as overlapping 2×3 subgrids).  I’ll leave this for you to think about.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s