Task 5. At a fish market, there are 10 stalls all selling the same 10 types of fish. All the fish are caught in the North Sea or the Mediterranean Sea, and each stall has only one sea of origin per fish species. A number, $k$, of customers buy one fish from each stall so that they have one fish of each species. Furthermore, we know that each pair of customers has a fish species with different origins. We consider all possible ways to stock the stalls according to the above rules.

What is the maximum possible value of $k$?
Solution. The answer is $2^{10}-10$. First, we note that there are $2^{10}$ possible combinations for the origins of each fish species. We will show that there are always at least 10 exceptions (possibilities that are ruled out) and that there is a market setup where there are exactly 10 exceptions.

We order both the stalls and the fish from 1 to 10. For a stall $i$, we define the sequence $a_{i} \in\{M, N\}^{10}$ as the origins of the 10 fish species in this stall (for example, $a_{1}=(M, M, M, N, M, N, N, M, M, M)$). Let $c_{i}$ be the complement of this sequence: we replace all $M$ with $N$ and vice versa. Since every customer has bought a fish from stall $i$, no customer can have the sequence $c_{i}$. If the sequences $c_{i}$ with $1 \leq i \leq 10$ are all different, then we have 10 exceptions.

On the other hand, suppose that stalls $i$ and $j$ sell fish from exactly the same seas, i.e., $a_{i}=a_{j}$. Then also $c_{i}=c_{j}$. We define the sequences $d_{k}$ with $1 \leq k \leq 10$ by swapping the origin of fish $k$ in the sequence $c_{i}$. These are precisely the sequences that match the sequence $a_{i}=a_{j}$ in exactly one sea. If a customer has bought a sequence $d_{k}$, then there can be at most one fish from stall $i$ or $j$ in it. This contradicts the fact that the customer has bought a fish from both stalls. We conclude that in this case, we also have at least 10 exceptions $d_{k}$ (and in fact also $c_{i}$).

We construct a market as follows where you can buy $2^{10}-10$ different combinations of fish origins as described in the problem: stall $i$ sells only fish from the North Sea, with the exception of fish $i$ from the Mediterranean Sea. Let $b \in\{M, N\}^{10}$ be a sequence of origins such that it does not contain exactly one $N$. We will show that we can buy 10 different fish from 10 different stalls so that $b$ is the sequence of origins. We split the fish in $b$ into a set $A$ from the Mediterranean Sea and a set $B$ from the North Sea, that is, $A$ is the set of indices where an $M$ stands in $b$ and $B$ is the set of indices where an $N$ stands. For $i \in A$, we buy fish species $i$ from stall $i$, so we indeed get a fish from the Mediterranean Sea. If $B$ is empty, then we are done. Otherwise, $B$ has at least two elements, and we write $B=\left\{i_{1}, \ldots, i_{n}\right\} \subset\{1, \ldots, 10\}$. For $i_{k} \in B$, we buy fish species $i_{k}$ from stall $i_{k+1}$, where we compute the indices modulo $n$. Since $n \neq 1$, it holds that $i_{k+1} \neq i_{k}$, so this fish indeed comes from the North Sea.