Difference between revisions of "2018 AIME I Problems/Problem 9"
m (→Sol. 2 (C++)) |
|||
| Line 19: | Line 19: | ||
-expiLnCalc | -expiLnCalc | ||
| − | == | + | == Solution 0 == |
This code works: | This code works: | ||
Revision as of 21:42, 26 March 2018
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.
Contents
Solutions
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, 16, 4, 20\}, \{5, 11, 5, 19\},\]](http://latex.artofproblemsolving.com/4/a/9/4a935e4e076d965e072e64cc0dac959487372318.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! We can subtract 1 from all pairs of sets that have two elements in common, because those can give us identical sets. There are 3 pairs about and 3 pairs about , meaning we lose 
. That's 
for Case 2.
Total gives 
.
-expiLnCalc
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
| 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. 
