Maths Olympiad Prep

Library / /47 of 61

Combinatorics Difficulty 6.7 National Olympiad Prove it Greece

Let QnQ_n be the set of nn-tuples x=(x1,...,xn)x = (x_1, ..., x_n), xi{0,1,2}x_i \in \{0, 1, 2\}, i=1,2,...,ni = 1, 2, ..., n. A triad (x,y,z)(x, y, z), where x=(x1,x2,...,xn)x = (x_1, x_2, ..., x_n), y=(y1,y2,...,yn)y = (y_1, y_2, ..., y_n), z=(z1,z2,...,zn)z = (z_1, z_2, ..., z_n), of distinguished elements of QnQ_n is called good, if there exists at least one i{1,2,...,n}i \in \{1, 2, ..., n\} for which the sets {xi,yi,zi}\{x_i, y_i, z_i\} and {0,1,2}\{0, 1, 2\} are equal. A subset AA of QnQ_n is called good, if every three elements of AA form a good triad. Prove that every good subset of QnQ_n has at most 2(32)n2\left(\frac{3}{2}\right)^n elements.

Solution

We will use induction with respect to nn. The case for n=1n = 1 is obvious. We suppose that every good subset of Qn1Q_{n-1} has at most 2(32)n12\left(\frac{3}{2}\right)^{n-1} elements.

Let A0={(x1,...,xn)A:xn0}A_0 = \{(x_1, ..., x_n) \in A : x_n \neq 0\}. We define the subsets A1,A2A_1, A_2 similarly, that is
A1={(x1,...,xn)A:xn1},A2={(x1,...,xn)A:xn2}. A_1 = \{(x_1, ..., x_n) \in A : x_n \neq 1\}, \quad A_2 = \{(x_1, ..., x_n) \in A : x_n \neq 2\}.
Since AA is a good set and A0A_0 is its subset, it follows that A0A_0 is also good. It means that for every three elements of A0A_0 there exists a coordinate which is different for every two of them. This coordinate cannot be the last one because 00 cannot be there. Therefore the set A0A_0' produced from the elements of A0A_0 by deleting the last coordinate is a good subset of Qn1Q_{n-1}.

Moreover, we observe that, if A03|A_0| \geq 3, then A0=A0|A_0'| = |A_0|.
In fact, if A0A0|A_0'| \neq |A_0|, then there would exist an element aA0a \in A_0' such that x,yA0x, y \in A_0, where x,yx, y arise from aa by adding 11 and 22, respectively, as last coordinate. However, if then zz is any other element of A0A_0, it cannot have as last coordinate 00, and so x,y,zx, y, z will not form a good triad, absurd. Hence, from the induction hypothesis we have
A0max{2,A0}2(32)n1. |A_0| \leq \max\{2, |A_0'|\} \leq 2\left(\frac{3}{2}\right)^{n-1}.
Similarly, we get that: A1,A22(32)n1|A_1|, |A_2| \leq 2\left(\frac{3}{2}\right)^{n-1}. Since every element of AA appears exactly in two of the sets A0,A1,A2A_0, A_1, A_2, we conclude:
A=12(A0+A1+A2)2(32)n. |A| = \frac{1}{2}(|A_0| + |A_1| + |A_2|) \leq 2\left(\frac{3}{2}\right)^n.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.