Maths Olympiad Prep

Library / /279 of 299

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Iran

There are 27 cards, each has some amount of (1 or 2 or 3) shapes (a circle, a square or a triangle) with some color (white, grey or black) on them. We call a triple of cards a match such that all of them have the same amount of shapes or mutually distinct amount of shapes, have the same shape or mutually distinct shapes and have the same color or mutually distinct colors. For instance, three cards shown in the figure are a match because they have distinct amount of shapes, distinct shapes but the same color of shapes.

What is the maximum number of cards that we can choose such that
none of the triples make a match?
Figure 1

Solution

We will prove that the answer of the problem is 99.

Each card can be corresponded with a point in Z33\mathbb{Z}_3^3. A line in Z33\mathbb{Z}_3^3 is defined to be a subset of the form {P,P+V,P+2V}\{P, P+V, P+2V\} where PP and VV are two elements in Z33\mathbb{Z}_3^3, such that V0V \neq 0 (in Z33\mathbb{Z}_3^3). It is easy to see that three elements of Z33\mathbb{Z}_3^3 form a line, if and only if their sum (in Z33\mathbb{Z}_3^3) is equal to 00. For instance, in the following figure we can see three different lines. In this new language, the problem is to find the maximum number of points in Z33\mathbb{Z}_3^3 such that no three of them are collinear.
Figure 2

The following lemma is the statement of the problem in Z32\mathbb{Z}_3^2, and proof that the answer is not greater than 44.

Lemma. There are no 55 points in Z32\mathbb{Z}_3^2 such that no three of them are collinear (definition of line in Z32\mathbb{Z}_3^2 is similar).

Proof. Assume to the contrary that SS is a set in Z32\mathbb{Z}_3^2 with more than 44 elements such that no three points of SS are collinear. Let PP be one point in Z32\mathbb{Z}_3^2. There are exactly 44 lines (in Z32\mathbb{Z}_3^2) passing through PP. For example, if PP is a point in the corner, these are the lines containing PP.
Figure 3
Since no three points of SS are collinear, each line passing through PSP \in S contains at most one other point in this set. So there are at most five points in SS (Note that for any point in Z32\mathbb{Z}_3^2 like QPQ \neq P, there is a unique line containing both PP and QQ).
Now assume that SS has exactly 55 elements. Consider PSP \in S. Again, since there are only four lines passing through PP, and there are exactly four other points in SS, every line passing through PP will contain another point of SS.
It means that every line in Z32\mathbb{Z}_3^2, intersects SS in exactly zero or two points. So there are (52)=10\binom{5}{2} = 10 lines in Z32\mathbb{Z}_3^2 containing two points of SS. On the other hand, the total number of lines in Z32\mathbb{Z}_3^2 is 1212 (for each of 99 points in Z32\mathbb{Z}_3^2, there are 44 lines containing that point, and every line consists of 33 different points). Therefore there are two lines l1l_1 and l2l_2 in Z32\mathbb{Z}_3^2 having empty intersection with SS. But the union of l1l_1 and l2l_2 contains at least 55 points. This contradicts S=5|S| = 5.

We call a subset P\mathcal{P} of Z33\mathbb{Z}_3^3 a plane, if there exist a,b,c,dZ3a, b, c, d \in \mathbb{Z}_3 with at least one of a,ba, b and cc is non-zero (in Z3\mathbb{Z}_3) and such that
P=Pd(a,b,c)={(x,y,z):ax+by+cz=d(mod3)}. \mathcal{P} = \mathcal{P}_d(a, b, c) = \{ (x, y, z) : ax + by + cz = d \pmod{3} \}.
It is easy to see that every plane consists of exactly 99 points and for every three points A,BA, B and CC in Z33\mathbb{Z}_3^3, either there exists a unique plane passing through them, or they are collinear. In the latter case there are exactly four different planes containing them.
We call two planes parallel, if they have no common points. Again, it is easy to check that if two planes P1\mathcal{P}_1 and P2\mathcal{P}_2 are parallel, there exist two different numbers i,jZ3i, j \in \mathbb{Z}_3 and (a,b,c)0(a, b, c) \neq \vec{0} in Z33\mathbb{Z}_3^3 such that
P1=Pi(a,b,c),P2=Pj(a,b,c). \mathcal{P}_1 = \mathcal{P}_i(a, b, c), \quad \mathcal{P}_2 = \mathcal{P}_j(a, b, c).
For any (a,b,c)0(a, b, c) \neq \vec{0} (in Z33\mathbb{Z}_3^3), all 2727 points in Z33\mathbb{Z}_3^3 can be partitioned into three parallel planes P0(a,b,c)\mathcal{P}_0(a, b, c), P1(a,b,c)\mathcal{P}_1(a, b, c) and P2(a,b,c)\mathcal{P}_2(a, b, c). But since Pi(a,b,c)=Pi(a,b,c)\mathcal{P}_i(a, b, c) = \mathcal{P}_{-i}(-a, -b, -c), two points (a,b,c)(a, b, c) and (a,b,c)(-a, -b, -c) give the same partition. Therefore, there are exactly 262=13\frac{26}{2} = 13 ways to partition Z33\mathbb{Z}_3^3 into three parallel planes. Note that if we consider all these 1313 partitions, every plane in Z33\mathbb{Z}_3^3 will appear exactly in one of the partitions.
Now assume that there exist a set SS with 1010 elements satisfying the desired properties. Consider one of above partitions. According to the lemma, each plane in this partition contains at most 44 points of SS. Since there are 1010 points in total, there are two different type of partitions.
(1) Partitions such that two planes contain 44 points of SS, and the third one contains 22.
(2) Partitions such that two planes contain 33 points of SS, and the third one contains 44.
Let mm and nn be the total number of partitions of types (1) and (2), respectively. There are totally 1313 ways to partition the points. So we obtain the following equation.
m+n=13. m + n = 13.
We are going to find another equation for m,nm, n.
For this reason, we count the number of elements of the following set in two different ways.
W={({A,B},P):P is a plane, A,BPS} W = \{ (\{A, B\}, \mathcal{P}) : \mathcal{P} \text{ is a plane, } A, B \in \mathcal{P} \cap S \}
On one hand, if we count the number of pairs of points of S\mathcal{S} in each plane of partitions of type (1), we get a total of
(42)+(42)+(22)=13 \binom{4}{2} + \binom{4}{2} + \binom{2}{2} = 13
pairs of points for each partition of this type. And for the type (2), this number is
(42)+(32)+(32)=12. \binom{4}{2} + \binom{3}{2} + \binom{3}{2} = 12.
So the cardinality of WW is
13m+12n. 13m + 12n.
On the other hand, for any two points A,BSA, B \in \mathcal{S}, the total amount of planes containing both AA and BB is 44. Since there are totally (102)=45\binom{10}{2} = 45 pairs, the cardinality of WW is 4×45=1804 \times 45 = 180, so we obtain 13m+12n=18013m+12n = 180. But this equation is clearly impossible when m+n=13m+n=13 because
169=13m+13n13m+12n=180, 169 = 13m + 13n \geq 13m + 12n = 180,
Contradiction. So there are at most 99 points with the desired properties. Also the following set of points is a valid example for 99 points (look at the figure below).
Figure 4
Translating the solution into the main problem, the total number of cards we can choose is 99. ■

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.