Is Einstein's riddle an example of a combinatorial design?

Question

I have just learned a bit about combinatorial designs (BIBDs, constructing a ($b,v,r,k, \lambda$)-design, necessary conditions for a design, cyclic designs) and it reminded me a lot of Einstein's riddle (aka: Zebra Puzzle)

Is Einstein's riddle an example of a combinatorial design?

If not, can it be made into a design?

Answer 1

The phrase "combinatorial design" can mean many things, but most commonly it refers to block designs.

More broadly it might be interpreted in the context of incidence structures. The Einstein riddle could be viewed as involving a multipartite graph which frames the connections between:

• five houses "in a row"
• five nationalities
• five kinds of pets
• five beverages drunk
• five colors for houses
• five brands of cigarettes

Thus one might relate the potential solution space to a complete multipartite graph $K_{5,5,5,5,5,5}$ with six parts, each of size five. The solution amounts to a matching from one part (say, the houses) to each of the other parts, consistent with various "facts" espoused or implied by the puzzle.