Problem

Source: 2019 Irish Mathematical Olympiad paper 2 p10

Tags: combinatorics



Island Hopping Holidays offer short holidays to $64$ islands, labeled Island $i, 1 \le i \le 64$. A guest chooses any Island $a$ for the first night of the holiday, moves to Island $b$ for the second night, and finally moves to Island $c$ for the third night. Due to the limited number of boats, we must have $b \in T_a$ and $c \in T_b$, where the sets $T_i$ are chosen so that (a) each $T_i$ is non-empty, and $i \notin T_i$, (b) $\sum^{64}_{i=1} |T_i| = 128$, where $|T_i|$ is the number of elements of $T_i$. Exhibit a choice of sets $T_i$ giving at least $63\cdot 64 + 6 = 4038$ possible holidays. Note that c = a is allowed, and holiday choices $(a, b, c)$ and $(a',b',c')$ are considered distinct if $a \ne a'$ or $b \ne b'$ or $c \ne c'$.