Maths Olympiad Prep

Library / /232 of 520

Combinatorics Difficulty 5.2 AIME, harder Find the answer

5. For sets A,B,CA, B, C (not necessarily distinct), the union ABC={1,2,3,4,5,6,7,8,9,10}A \cup B \cup C=\{1,2,3,4,5,6,7,8,9,10\}, then under this condition, the number of possible triples (A,B,C)(A, B, C) is (write the answer in the form aba^{b}).

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

Solution

5. 7107^{10}.

As shown in the figure, ABCA \cup B \cup C is divided into seven non-overlapping parts X,Y,Z,WX, Y, Z, W, U,V,TU, V, T (where Y=ABC,T=ABC,X=ABCY = A \cap B \cap C, T = A - B - C, X = A \cap B - C, etc.). Thus, each of the elements 1,2,,9,101, 2, \cdots, 9, 10 has 7 possible allocation places in ABCA \cup B \cup C, so the total number of allocation schemes for these elements is 7107^{10}. Any two different allocation schemes will result in different ordered triples (A,B,C)(A, B, C) (since X,Y,Z,WX, Y, Z, W, U,V,TU, V, T are uniquely determined by the ordered triple (A,B,C)(A, B, C)), therefore, the number of ordered triples (A,B,C)(A, B, C) is equal to the total number of allocation schemes for 1,2,,9,101, 2, \cdots, 9, 10, which is 7107^{10}.

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