Problem

Source: Greece National Olympiad 2022, Problem 4

Tags: combinatorics



Let $Q_n$ be the set of all $n$-tuples $x=(x_1,\ldots,x_n)$ with $x_i \in \{0,1,2 \}$, $i=1,2,\ldots,n$. A triple $(x,y,z)$ (where $x=(x_1,x_2,\ldots,x_n)$, $y=(y_1,y_2,\ldots,y_n)$, $z=(z_1,z_2,\ldots,z_n)$) of distinct elements of $Q_n$ is called a good triple, if there exists at least one $i \in \{1,2, \ldots, n \}$, for which $\{x_i,y_i,z_i \}=\{0,1,2 \}$. A subset $A$ of $Q_n$ will be called a good subset, if any three elements of $A$ form a good triple. Prove that every good subset of $Q_n$ contains at most $2 \cdot \left(\frac{3}{2}\right)^n$ elements.