2018 AIME I Problems/Problem 9
Problem
Find the number of four-element subsets of 
with the property that two distinct elements of a subset have a sum of 
, and two distinct elements of a subset have a sum of 
. For example, 
and 
are two such subsets.
Solution 1
This problem is tricky because it is the capital of a few "bashy" calculations. Nevertheless, the process is straightforward. Call the set 
.
Note that there are only two cases: 1 where 
and 
or 2 where and 
. Also note that there is no overlap between the two situations! This is because if they overlapped, adding the two equations of both cases and canceling out gives you 
, which cannot be true.
Case 1.
This is probably the simplest: just make a list of possible combinations for 
and 
. We get 
for the first and 
for the second. That appears to give us 
solutions, right? NO. Because elements can't repeat, take out the supposed sets
![\[\{1, 15, 9, 15\}, \{2, 14, 10, 14\}, \{3, 13, 11, 13\}, \{4, 12, 4, 20\}, \{5, 11, 5, 19\},\]](http://latex.artofproblemsolving.com/e/2/0/e201f55cba01bb1a58df9e58dfad0d6f4555d38b.png)
![\[\{5, 11, 11, 13\}, \{6, 10, 6, 18\}, \{6, 10, 10, 14\}, \{7, 9, 9, 15\}, \{7, 9, 7, 17\}\]](http://latex.artofproblemsolving.com/6/1/f/61f420cd5557117b1cf09fabdd4b4c4952fb3ab9.png)
That's ten cases gone. So 
for Case 1.
Case 2.
We can look for solutions by listing possible 
values and filling in the blanks. Start with 
, as that is the minimum. We find 
, and likewise up to 
. But we can't have 
or 
because 
or 
, respectively! Now, it would seem like there are 
values for and 
unique values for each 
, giving a total of 
, but that is once again not true because there are some repeated values!
There are two cases of overcounting:
case 1) (5,11,13,19) & (5.11.19.13)
The same is for (6,10,14,18) and (7,9,15,17)
case 2) those that have the same b and c values
this case includes:
(1,15,9,7) and (7,9,15,1)
(2,14,10,6) and (6,10,14,2)
(3,13,11,5) and (5,11,13,3)
So we need to subtract 6 overcounts.
So, that's 
for Case 2.
Total gives 
.
-expiLnCalc
Solution 2
Let's say our four elements in our subset are 
. We have two cases. Note that the order of the elements / the element letters themselves don't matter since they are all on equal grounds at the start.
and 
.
List out possibilities for 
but don't list 
because those are the same elements and that is restricted.
Then list out the possibilities for 
but don't list 
because they are the same elements.
This will give you 
elements, which is 
. However, as stated above, we have overlap. Just count starting from . 
all overlap once, which is , thus 
cases in this case. Note that 
wasn't included because again, if , 
and 
cannot be .
and 
.
Here, 
is included in both equations. We can easily see that 
will never equal each other.
Furthermore, there are 17 choices for (
included elements) for each . Listing out the possible s, we go from . Do not include 
or because if they are included, then 
will be the same as , which is restricted.
There are options there, and thus 
. But, note that if 
, 
, and so we have a double-counted set. Starting with 
, we have 
(where is 
. That means there are 
double-counted cases. Thus 
cases in this case.
Adding these up, we get 
~IronicNinja
~
by AlcBoy1729
~Formatted by ojaswupadhyay and phoenixfire
Solution 3 (Official MAA)
There are two types of 
that have the needed property. There is either an assignment of distinct values for 
and such that 
and 
or an assignment such that and 
These two types are mutually exclusive because and 
imply that 
For the first type, there are 
choices for 
namely 
and 
and there are choices for 
namely 
and 
Thus a four-element subset of the first type can be formed by taking the union of one of two-element subsets with one of two-element subsets as long as these two subsets are disjoint. There are such pairings that are not disjoint out of the 
pairings, so there are 
subsets of the first type.
For subsets of the second type, there are choices for the value of 
such that 
and 
can be two other elements of the subset. Note that in each of these cases, 
For each of these, there are 
other values that can be chosen for the element in the subset. But 
counts some subsets more than once. In particular, a subset is counted twice if 
or 
. In such cases either 
or 
. There are exactly subsets where the role of can be played by two different elements of the set. They are 
and 
. Thus there are 
subsets of the second type.
In all, there are 
subsets with the required property.
| 2018 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 8 |
Followed by Problem 10 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
