Maths Olympiad Prep

Library / /573 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Find the number of triples of sets (A,B,C)(A, B, C) such that: (a) A,B,C{1,2,3,,8}A, B, C \subseteq\{1,2,3, \ldots, 8\}. (b) AB=BC=CA=2|A \cap B|=|B \cap C|=|C \cap A|=2. (c) A=B=C=4|A|=|B|=|C|=4. Here, S|S| denotes the number of elements in the set SS.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We consider the sets drawn in a Venn diagram. Note that each element that is in at least one of the subsets lies in these seven possible spaces. We split by casework, with the cases based on N=R7=ABCN=\left|R_{7}\right|=|A \cap B \cap C|. Case 1: N=2N=2 Because we are given that R4+N=R5+N=R6+N=2\left|R_{4}\right|+N=\left|R_{5}\right|+N=\left|R_{6}\right|+N=2, we must have R4=R5=R6=0\left|R_{4}\right|=\left|R_{5}\right|=\left|R_{6}\right|=0. But we also know that R1+R5+R6+N=4\left|R_{1}\right|+\left|R_{5}\right|+\left|R_{6}\right|+N=4, so R1=2\left|R_{1}\right|=2. Similarly, R2=R3=2\left|R_{2}\right|=\left|R_{3}\right|=2. Since these regions are distinguishable, we multiply through and obtain (82)(62)(42)(22)=2520\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}=2520 ways. Case 2: N=1N=1 In this case, we can immediately deduce R4=R5=R6=1\left|R_{4}\right|=\left|R_{5}\right|=\left|R_{6}\right|=1. From this, it follows that R1=4111=1\left|R_{1}\right|=4-1-1-1=1, and similarly, R2=R3=1\left|R_{2}\right|=\left|R_{3}\right|=1. All seven regions each contain one integer, so there are a total of (8)(7)(2)=40320(8)(7) \ldots(2)=40320 ways. Case 3: N=0N=0 Because R4+N=R5+N=R6+N=2\left|R_{4}\right|+N=\left|R_{5}\right|+N=\left|R_{6}\right|+N=2, we must have R4=R5=R6=2\left|R_{4}\right|=\left|R_{5}\right|=\left|R_{6}\right|=2. Since R1+R5+R6+N=4\left|R_{1}\right|+\left|R_{5}\right|+\left|R_{6}\right|+N=4, we immediately see that R1=0\left|R_{1}\right|=0. Similarly, R2=R3=0\left|R_{2}\right|=\left|R_{3}\right|=0. The number of ways to fill R4,R5,R6R_{4}, R_{5}, R_{6} is (82)(62)(42)=2520\binom{8}{2}\binom{6}{2}\binom{4}{2}=2520. This clearly exhausts all the possibilities, so adding gives us 40320+2520+2520=4536040320+2520+2520=45360 ways.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.