Solution: ‘The Fabulously Fair Feast’

This month’s Insights puzzle featured a story about four finicky friends — Amar, Bob, Ching and Danica — who have rules to ensure that everyone enjoys their get-togethers and can bond with every other member of the group. At their get-togethers they have four “featured items” for the evening related to food, drink, activity or entertainment. The rules are:

1. Each person must like at least half of the featured items.
2. For exactly half of the items, each pair of friends must share either a like or dislike for those items.

At a particular get-together planned by Amar, it is clear that Amar liked all four items, but Bob disliked the first one.

Question 1:

Can you figure out the likes and dislikes of each friend? Write them out as a Sudoku square with the friends’ names alphabetically along the rows, and the items, in the order given, along the columns.

Readers Michael DeLyser and Ravi Kumar Meduri both came up with this solution:

A            1     1     1     1
B           -1   -1     1     1
C            1    -1     1    -1
D           -1     1     1    -1

where 1 represents likes and -1 represents dislikes.

Question 2:

Readers were asked to come up with the same kind of arrangement for eight people and eight items.

There are several solutions. Michael gave a valid one. And Ravi gave a method for generalizing from the 4×4 arrangement to an 8×8 one:

The solution for eight can be generated from (a solution for) four as:

S4     S4

-S4     S4

Once again, half the columns in every two rows match, and half do not match.

1     1     1     1     1     1     1     1

-1   -1     1     1    -1   -1     1     1

1    -1     1   -1     1    -1     1   -1

-1     1     1   -1    -1     1     1   -1

-1   -1    -1   -1     1     1     1     1

1     1    -1   -1    -1   -1     1     1

-1    1    -1     1     1    -1     1   -1

1   -1    -1     1    -1     1     1   -1

We might ask an interesting follow-up question: How many different solutions are there to Question 2? I’ll leave it to readers to figure out the answer.

Question 3:

For those of you who love word puzzles, here’s a treat for you:  The answers to this month’s puzzles are examples of mathematical structures that are known by a two-word name. The letters spelling out these two words are embedded in the text of today’s column. Can you find them?

The answer is “Hadamard matrices,” which Ravi found in the sentences “Had Amar decided …” and “… sat around the mat, rice soup …”

These matrices have very interesting mathematical properties. If you consider each row as an n-dimensional vector (which matrices are often used for), then each row in a Hadamard matrix is orthogonal, or at right angles to each other. Thus the following 2×2 Hadamard matrix (also called an “order 2” Hadamard matrix),

1     1

1    -1

represents the vectors (1,1) or a 45-degree line going up rightward and (1,-1) or a 45-degree line going up leftward, which are at right angles to each other. Another interesting property of Hadamard matrices is that if you multiply an order n Hadamard matrix by its transpose (the matrix you get when you swap its rows and columns), you get a specific diagonal matrix – one that has the number n repeated along its diagonal, with zeroes elsewhere. Mathematically, it is n times the identity matrix. So you can check whether your solution is correct by multiplying your matrix by its transpose at Wolfram Alpha (use braces) or an online matrix multiplication calculator. You should get only 4s along the diagonal for question 1 and only 8s for question 2.

The Hadamard conjecture states that Hadamard matrices exist for any number n that is a multiple of 4. Mathematicians have consequently been trying to find Hadamard matrices for all multiples of 4, or find a multiple for which one does not exist. Some numbers have easy-to-find Hadamard matrices built from lower-order matrices (as we saw above when we derived a matrix of order 8 from a matrix of order 4); other numbers are not so easy to find, but mathematicians have been steadily finding them to push the unknown ones ever higher. In suggesting this topic, the mathematician Terence Tao remarked, “Apparently, the first open case of Hadamard’s conjecture is 668 — that is, it’s not known if there is a Hadamard matrix of order 668. I don’t recommend this as a puzzle for your magazine.”

Question 4:

What do you think the fabulous rug represents?

The rug represents a possible arrangement that obeys the two rules mentioned, but not the specific instance asked for in Question 1. Here’s Michael, whose comment nails it:

The carpet represents a simple solution for everyone’s likes and dislikes to satisfy the rules if we hadn’t been told that Amar liked everything. The squares with lines going from bottom left to top right are likes. The squares with lines going from top left to bottom right are dislikes. The top row is Amar, the second row is Bob, etc. The first column is the first featured item, the second column is the second item, etc. The rules are satisfied because each person likes three of the four items, and each pair shares a like for two of the items.

There is another specific connection of the rug to Hadamard matrices. The rug is the artist’s rendition of a Hadamard matrix of order 428, which was the smallest unknown matrix order back in 2004. In June of that year, Hadi Kharaghani and Behruz Tayfeh-Rezaie built a Hadamard matrix of order 428. A beautiful rendition with two different colors for the 1s and -1s, using one pixel per matrix element, can be seen on this site. The drawing of the rug is based on this 428×428 Hadamard matrix.

I hope I have succeeded in piquing your curiosity about these fascinating matrices and perhaps encouraged you to explore them further. The Quanta T-shirt for this month goes to Michael DeLyser, just edging Ravi Kumar Meduri. Congratulations!

That’s it for our Insights column for 2015. I hope to see you in 2016 with a whole year of new puzzles. Happy holidays and a happy new year to all!