Maths Olympiad Prep

Library / /622 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Given a set AA with 10 elements, find the number of consistent 2-configurations of AA of order 2 with exactly 2 cells.

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

Solution

Notice that if we look only at the pairs contained within any fixed cell, each element of that cell still lies in 2 such pairs, since all the pairs it belongs to are contained within that cell. Thus we have an induced consistent 2-configuration of order 2 of each cell. Now, each cell must have at least 3 elements for the configuration to be 2-consistent. So we can have either two 5-element cells, a 4-element cell and a 6-element cell, or a 3-element cell and a 7-element cell. If there are two 5-element cells, we can choose the members of the first cell in (105) \binom{10}{5} ways, and then (by the reasoning in the previous problem) we have 4!/2 4!/2 ways to build a consistent 2-configuration of order 2 of each cell. However, choosing 5 elements for the first cell is equivalent to choosing the other 5 elements for the first cell, since the two cells are indistinguishable; thus, we have overcounted by a factor of 2. So we have (105)(4!/2)2/2=252144/2=18144 \binom{10}{5} \cdot (4!/2)^{2}/2 = 252 \cdot 144/2 = 18144 ways to form our configuration if we require it to have two cells of 5 elements each. If we have one 4-element cell and one 6-element cell, then there are (104) \binom{10}{4} ways to determine which 4 elements go in the smaller cell, and then 3!/2 3!/2 ways and 5!/2 5!/2 ways, respectively, to construct the 2-configurations of the two cells, for a total of (104)(3!/2)(5!/2)=210360=37800 \binom{10}{4} \cdot (3!/2) \cdot (5!/2) = 210 \cdot 3 \cdot 60 = 37800 configurations (no overcounting here), and by similar reasoning, we have (103)(2!/2)(6!/2)=1201360=43200 \binom{10}{3} \cdot (2!/2) \cdot (6!/2) = 120 \cdot 1 \cdot 360 = 43200 configurations with one 3-element cell and one 7-element cell. Thus, altogether, we have a total of 18144+37800+43200=99144 18144 + 37800 + 43200 = 99144 consistent 2-configurations of order 2 with exactly 2 cells.

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.