MathDB
How many elements can a good set contain?

Source: Greece National Olympiad 2022, Problem 4

February 26, 2022
combinatorics

Problem Statement

Let QnQ_n be the set of all nn-tuples x=(x1,…,xn)x=(x_1,\ldots,x_n) with xi∈{0,1,2}x_i \in \{0,1,2 \}, i=1,2,…,ni=1,2,\ldots,n. A triple (x,y,z)(x,y,z) (where x=(x1,x2,…,xn)x=(x_1,x_2,\ldots,x_n), y=(y1,y2,…,yn)y=(y_1,y_2,\ldots,y_n), z=(z1,z2,…,zn)z=(z_1,z_2,\ldots,z_n)) of distinct elements of QnQ_n is called a good triple, if there exists at least one i∈{1,2,…,n}i \in \{1,2, \ldots, n \}, for which {xi,yi,zi}={0,1,2}\{x_i,y_i,z_i \}=\{0,1,2 \}. A subset AA of QnQ_n will be called a good subset, if any three elements of AA form a good triple. Prove that every good subset of QnQ_n contains at most 2⋅(32)n2 \cdot \left(\frac{3}{2}\right)^n elements.
Back to ProblemsView on AoPS