PROBLEM OF THE MONTH

February 2004




A Littlewood-Richardson crossword puzzle is a rectangular grid of black and white squares. The "clues" to the puzzle are a set of positive integers. The objective is to fill the white squares with these numbers in such a way that the following three conditions are satisfied:

  1. On each row, every number is greater than or equal to each number to the left of it.
  2. In each column, every number is strictly greater than each number above it.
  3. As you read off the numbers in the grid from right to left and from top to bottom, the number of "1"s read is always at least as large as the number of "2"s, which is always at least as large at the number of "3"s, which is at least as large as ... and so on.

For example, given the following Littlewood-Richardson puzzle,

"Clues":
1,1,1,
2,2,2,
3,3
consider the following two arrangements:
The arrangement on the left is a solution to the puzzle. The arrangement on the right satisfies the first two conditions, but not the third. Notice that as you read from the top right corner to the rightmost square on the third row, you have encountered two "3"s, but only one "2".

PROBLEM:

  1. Find a second solution to the Littlewood-Richardson crossword puzzle given above. Prove that there are only two solutions.
  2. How many distinct solutions are there to the following Littlewood-Richardson crossword puzzle:
    "Clues":
    1,1,1,1,
    2,2,
    3
  3. If you use the same grid as in the previous question, what other sets of clues have at least one solution? (Hint: There are nine of them, four of which have a unique solution and five of which have multiple solutions.)

Submit your solution to the Mathematics Undergraduate Office (Math P-142) or electronically to Prof. Kudzin at problem@math.sunysb.edu by the due date. Acceptable electronic formats are: PDF, Postscript, DVI, (La)TeX, or just plain text. Please include your name and phone number, or preferably your email address.

Closing date: March 1st at 12 pm.