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.
Problem
Source: Greece National Olympiad 2022, Problem 4
Tags: combinatorics
CANBANKAN
26.02.2022 22:17
We proceed by induction on $n$, with the base case, $n=1$ being clear.
For $t=0,1,2$, let $J_t$ be the set of sequences with $x_n=t$. We know that any three sequences in $J_t\cup J_u$ must have $x_j,y_j,z_j$ distinct, but $j\ne n$. First observe $(x_1,\cdots,x_{n-1})$ cannot appear in $J_t$ and $J_u$ simultaneously. By inductive hypothesis, there are at most $2\cdot (\frac 32)^{n-1}$ possibilities for the first $n-1$ elements in $J_t\cup J_u$. Since each of the possibilities can only appear in at most one of $J_t$, $J_u$, $|J_t|+|J_u|\le 2\cdot (\frac 32)^{n-1}$ sequences by inductive hypothesis. Thus, $2(|J_0|+|J_1|+|J_2|) \le 6\cdot (\frac 32)^{n-1}$, completing the induction
MatBoy-123
27.02.2022 09:37
Note that total number of unordered triplets $(x,y,z) \in Q^3 _{n} = \frac{6! ^n}{6!} = 2^{n-1}3^{n-1}$ , suppose for the sake of contradiction assume that there exist a good subset with $ > 2 \cdot (\frac{3}{2})^n$ , then note that $\binom{|A|}{3} \le 2^{n-1}3^{n-1}$ , which yields $$(3^n -2^{n-1}) (3^n -2^n) \le 2^{4n-3}$$which is not true for $n \ge 2$. Hence we are done.
CANBANKAN
27.02.2022 09:53
The final inequality doesn't hold for large $n$ because LHS tends to $9^n$ while RHS tends to $16^n$. I don't understand your argument. Can you write it in more detail