Solution for November 2009

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? November's problem comes from the collection of Joe Konhauser (1924-1992), a long-time Mathematics professor at Macalester College.

Correct responses:

Correct solutions were submitted this month by Halima  Abdalla  Bashier (Regina) Magnus Jakobsson (Sweden) Bojan Basic (Serbia) Omran Kouba (Syria) Luigi Bernardini (Italy) Remo Mantovanelli (Italy) José Borges (Portugal) Jomel Matalog Lou Cairoli (USA) Milan Pavic (Serbia) Bernard Carpentier (France) John T. Robinson (USA) Bernard Collignon (France) Albert Stadler (Switzerland) Philippe Fondanaiche (France) Jerry Vicars (USA) Tom Fuzzesy (Regina) Claudio Baiocchi (Italy) Allen Druze (USA)

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

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:

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.

Further comments.  Konhauser's problem was a recent offering of Stan Wagon's Problem of the Week (http://mathforum.org/wagon/).  Wagon found it in a box of Konhauser's problems that had long been missing.  We suspect that Konhauser chose the letters that make up his words from the initials of Problem Ofthe Month.  You should note also the subtlety of his humour — the only English word among the eight is the missing word poop.  On the other hand, there is at least one other English 4-letter word composed of these letters: pomp.  It must have taken quite a while to devise a combination of words that leads to a solution that is unique and, at the same time, a proper word.