Problem

Source: BMO Shortlist 2021

Tags: Balkan, shortlist, 2021, combinatorics, Sets, counting



Let $\mathcal{A}_n$ be the set of $n$-tuples $x = (x_1, ..., x_n)$ with $x_i \in \{0, 1, 2\}$. A triple $x, y, z$ of distinct elements of $\mathcal{A}_n$ is called good if there is some $i$ such that $\{x_i, y_i, z_i\} = \{0, 1, 2\}$. A subset $A$ of $\mathcal{A}_n$ is called good if every three distinct elements of $A$ form a good triple. Prove that every good subset of $\mathcal{A}_n$ has at most $2(\frac{3}{2})^n$ elements.