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 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! We can subtract 1 from all pairs of sets that have two elements in common, because those can give us identical sets. Write out all the sets and we get . That's for Case 2.

Total gives .

-expiLnCalc

Solution 2

This is gonna be real quick. I considered making this an extension to solution one, but I've decided to make it a separate solution. (Disclaimer: I'm not formatting this properly. If anyone wants to format it correctly using Latex feel free.)

Let's say our four elements in our subset are . We have two cases. First, we can have where two distinct elements sum to and two other distinct elements sum to . Basically, one way of representing this is having and . The order of the elements/the element letters themselves don't matter since they are all on equal grounds at the start. List out possibilities for but don't include because those are the same elements and that is restricted. Then list out the possibilities for but again 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 first case. Note that wasn't included because again, if , and cannot be .

Our second case is when and . Here, one element is included twice 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 since , you would think there are cases and we are done.

That's the tricky part about this problem - not the computation itself, but how easily sillies can be made. This is because, if and , notice that . That means that if is also , then we have a double-counted set. Starting with , we have where is . That means there are double-counted cases.

Adding these up, we get

~IronicNinja ~ by AlcBoy1729 Again if anyone wants to format this better feel free, I was just lazy.

Solution 0

This code works:

 int num = 0;
 for(int i = 1; i <= 20; i++){
   for(int j = i+1; j <= 20; j++){
     for(int k = j+1; k <= 20; k++){
       for(int m = k+1; m <= 20; m++){
         if(i+j==16 || i + k == 16 || i + m == 16 || j + k == 16
         || j + m == 16 || k + m == 16){
           if(i+j==24 || i+k==24 || i+m==24 || j+k==24 || j+m == 24 || k+m==24){
             num++; 
           }
         }
       }
     }
   }
 }
 cout << num << endl;

See Also

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.