crossword puzzle with four words

The Problem:
	Consider a 4 by 4 grid of squares to be viewed as a crossword puzzle with four words across and four words down. In alphabetical order, seven of the eight words are MPMM, OMPM, OMPP, OOMO, OOMP, POOM, and POPM. What is the eighth word?

The solution:

The eighth word is POOP. Of the many ways to determine the solution, the quickest came from Fuzesy and Jakobsson. Here is a composite of their arguments.
We focus on the two words that have three occurrences of the same letter: MPMM and OOMO. It is clear that these will force considerable structure on the grid. Because of the symmetry in the roles of horizontal and vertical, it makes no difference whether we put our first word in a row or in a column, so let us place MPMM in a column. Among the other six words we are given, there are exactly three that have M in the final position, so these are good candidates for horizontal words with MPMM in the final column. Thus,
we will try OMPM, POOM, and POPM in some order in the 1st, 3rd, and 4th rows.
The only possibilities for the remaining horizontal word are then OMPP and OOMP (in row 2); consequently, OOMO would have to be a vertical word. Because of our choices in rows 1, 3, and 4, OOMO would necessarily go in the second column and, therefore, OOMP must go in row 2, and OMPM must go in row 3. That gives us

	O		M
O	O	M	P
O	M	P	M
	O		M

and it remains only to determine which of POOM and POPM goes in row 1 and which in row 4. We still have one further word to work with: OMPP. This last word fits uniquely in the third column, leaving us with no further choice — POOM must go in the first row and POPM in the last:

P	O	O	M
O	O	M	P
O	M	P	M
P	O	P	M

POOP, in the first column, must therefore be the missing word, as claimed.
There remains the question of whether or not our solution is unique (up to our choice of which group of words is vertical). The only point in our argument where we might have had an option was in deciding which column MPMM should go in. The word could not go in the first column, since we do not have two other words beginning with an M; nor could it go in the second, because there is no word left with the second letter P. Since there are two other words with M in the third position, it is plausible that MPMM might go in the third column with our mystery word having the letter M as its third letter; but that also is not possible: then OOMO and OOMP would have to be in the first, third, or fourth rows, and there are no words left (to be entries in the first and second column) with the letter O in place one and three, or in place one and four, or in place three and four. Hence MPMM must be the fourth column, whence our solution is unique.

math central