Problem

Source: Baltic Way 2020, Problem 8

Tags: combinatorics, combinatorics proposed



Let $n$ be a given positive integer. A restaurant offers a choice of $n$ starters, $n$ main dishes, $n$ desserts and $n$ wines. A merry company dines at the restaurant, with each guest choosing a starter, a main dish, a dessert and a wine. No two people place exactly the same order. It turns out that there is no collection of $n$ guests such that their orders coincide in three of these aspects, but in the fourth one they all differ. (For example, there are no $n$ people that order exactly the same three courses of food, but $n$ different wines.) What is the maximal number of guests?