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?
Solution
We will prove that the answer of the problem is 9.
Each card can be corresponded with a point in Z33. A line in Z33 is defined to be a subset of the form {P,P+V,P+2V} where P and V are two elements in Z33, such that V=0 (in Z33). It is easy to see that three elements of Z33 form a line, if and only if their sum (in Z33) is equal to 0. 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 such that no three of them are collinear.
The following lemma is the statement of the problem in Z32, and proof that the answer is not greater than 4.
Lemma. There are no 5 points in Z32 such that no three of them are collinear (definition of line in Z32 is similar).
Proof. Assume to the contrary that S is a set in Z32 with more than 4 elements such that no three points of S are collinear. Let P be one point in Z32. There are exactly 4 lines (in Z32) passing through P. For example, if P is a point in the corner, these are the lines containing P. Since no three points of S are collinear, each line passing through P∈S contains at most one other point in this set. So there are at most five points in S (Note that for any point in Z32 like Q=P, there is a unique line containing both P and Q). Now assume that S has exactly 5 elements. Consider P∈S. Again, since there are only four lines passing through P, and there are exactly four other points in S, every line passing through P will contain another point of S. It means that every line in Z32, intersects S in exactly zero or two points. So there are (25)=10 lines in Z32 containing two points of S. On the other hand, the total number of lines in Z32 is 12 (for each of 9 points in Z32, there are 4 lines containing that point, and every line consists of 3 different points). Therefore there are two lines l1 and l2 in Z32 having empty intersection with S. But the union of l1 and l2 contains at least 5 points. This contradicts ∣S∣=5.
We call a subset P of Z33 a plane, if there exist a,b,c,d∈Z3 with at least one of a,b and c is non-zero (in Z3) and such that P=Pd(a,b,c)={(x,y,z):ax+by+cz=d(mod3)}. It is easy to see that every plane consists of exactly 9 points and for every three points A,B and C in Z33, 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 and P2 are parallel, there exist two different numbers i,j∈Z3 and (a,b,c)=0 in Z33 such that P1=Pi(a,b,c),P2=Pj(a,b,c). For any (a,b,c)=0 (in Z33), all 27 points in Z33 can be partitioned into three parallel planes P0(a,b,c), P1(a,b,c) and P2(a,b,c). But since Pi(a,b,c)=P−i(−a,−b,−c), two points (a,b,c) and (−a,−b,−c) give the same partition. Therefore, there are exactly 226=13 ways to partition Z33 into three parallel planes. Note that if we consider all these 13 partitions, every plane in Z33 will appear exactly in one of the partitions. Now assume that there exist a set S with 10 elements satisfying the desired properties. Consider one of above partitions. According to the lemma, each plane in this partition contains at most 4 points of S. Since there are 10 points in total, there are two different type of partitions. (1) Partitions such that two planes contain 4 points of S, and the third one contains 2. (2) Partitions such that two planes contain 3 points of S, and the third one contains 4. Let m and n be the total number of partitions of types (1) and (2), respectively. There are totally 13 ways to partition the points. So we obtain the following equation. m+n=13. We are going to find another equation for m,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,B∈P∩S} On one hand, if we count the number of pairs of points of S in each plane of partitions of type (1), we get a total of (24)+(24)+(22)=13 pairs of points for each partition of this type. And for the type (2), this number is (24)+(23)+(23)=12. So the cardinality of W is 13m+12n. On the other hand, for any two points A,B∈S, the total amount of planes containing both A and B is 4. Since there are totally (210)=45 pairs, the cardinality of W is 4×45=180, so we obtain 13m+12n=180. But this equation is clearly impossible when m+n=13 because 169=13m+13n≥13m+12n=180, Contradiction. So there are at most 9 points with the desired properties. Also the following set of points is a valid example for 9 points (look at the figure below). Translating the solution into the main problem, the total number of cards we can choose is 9. ■
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.