Difference between revisions of "2011 AIME II Problems/Problem 6"

Revision as of 01:05, 2 April 2011

Problem 6

Define an ordered quadruple $(a, b, c, d)$ as interesting if $1 \le a<b<c<d \le 10$ , and $a+d>b+c$ . How many ordered quadruples are there?

Solution

Rearranging the inequality we get $d-c > b-a$ . Let $e = 11$ , then $(a, b-a, c-b, d-c, e-d)$ is a partition of 11 into 5 positive integers or equivalently: $(a-1, b-a-1, c-b-1, d-c-1, e-d-1)$ is a partition of 6 into 5 non-negative integers. The number of ways to partition 6 into 5 non-negative parts is (bals and urns) $\binom{6+4}4 = \binom{10}4 = 210$ . The interesting quadruples correspond to partitions where the second number is less than the fourth. By symmetry there as many partitions where the fourth is less than the second. So, if $N$ is the number of partitions where the second element is equal to the fourth, our answer is $(210-N)/2$ .

We find $N$ as a sum of 4 cases:

two parts equal to zero, $\binom82 = 28$ ways,
two parts equal to one, $\binom62 = 15$ ways,
two parts equal to two, $\binom42 = 6$ ways,
two parts equal to three, $\binom22 = 1$ way.

Therefore, $N = 28 + 15 + 6 + 1 = 50$ and our answer is $(210 - 50)/2 = \fbox{80.}$

@@ Line 1: / Line 1: @@
-Problem:
+==Problem 6==
-Define an ordered quadruple (a, b, c, d) as interesting if <math>1 \le a<b<c<d \le 10</math>, and a+d>b+c. How many ordered quadruples are there?
+Define an ordered quadruple <math>(a, b, c, d)</math> as interesting if <math>1 \le a<b<c<d \le 10</math>, and <math>a+d>b+c</math>. How many ordered quadruples are there?
-----
+==Solution==
-Solution:
+Rearranging the inequality we get <math>d-c > b-a</math>. Let <math>e = 11</math>, then <math>(a, b-a, c-b, d-c, e-d)</math> is a partition of 11 into 5 positive integers or equivalently:
+<math>(a-1, b-a-1, c-b-1, d-c-1, e-d-1)</math> is a partition of 6 into 5 non-negative integers. The number of ways to partition 6 into 5 non-negative parts is (bals and urns) <math>\binom{6+4}4 = \binom{10}4 = 210</math>. The interesting quadruples correspond to partitions where the second number is less than the fourth. By symmetry there as many partitions where the fourth is less than the second. So, if <math>N</math> is the number of partitions where the second element is equal to the fourth, our answer is <math>(210-N)/2</math>.
-There is probably some really complicated formula for this, but as I didnt know it and had 3 hours to "do my best", I listed all possible combinations out. The answer is 80.
+We find <math>N</math> as a sum of 4 cases:
-You can do casework with the value of a.  If a = 1, we can do casework on b.  If b = 2, we can do casework on c.  if c = 3, d = 5,6,7,8,9, or 10.  That's 6.  If c = 4, d can be 6,7,8,9,10.  That's 5.  Continuing this pattern, we get 21 options is b = 2.  if b=3 and c = 4, d = 7, 8, 9, or 10, c= 5 gets d = 8, 9, 10 and by quick inspection we get 10 options with b = 3.  With b = 4, c = 5 we get d = 9,10, c= 6 we get d = 10, that's 3, with b = 5 there are no solutions.
+* two parts equal to zero, <math>\binom82 = 28</math> ways,
+* two parts equal to one, <math>\binom62 = 15</math> ways,
-So if a = 1 there are 21+10+3 = 34 options
+* two parts equal to two, <math>\binom42 = 6</math> ways,
+* two parts equal to three, <math>\binom22 = 1</math> way.
-If a = 2, b = 3, c= 4, then d = 6,7,8,9,10 so 15 options with b = 3 (same pattern as above).  if b = 4, c=5 gives d = 8, 9, 10 so 6 options.  if b = 5, c=6 gives just one option, d = 10, and if b=6, there are no options.
+Therefore, <math>N = 28 + 15 + 6 + 1 = 50</math> and our answer is <math>(210 - 50)/2 = \fbox{80.}</math>
-So if a = 2 there are 15+6+1 = 22 options
-If a = 3, b = 4, c = 5, then d = 7, 8, 9, 10 so 10 options (keeping with the same pattern).  if b=5 and c = 6, d = 9,10 so 3 options.  If b = 6 and c = 7, there are no options.
-So if a = 3 there are 10+3 = 13 options
-If a=4, b=5, c= 6, then d = 8, 9, 10 so 6 options.  If b = 6, c= 7 there is just one option
-So if a = 4 there are 6+1 = 7 options.
-If a = 5, b = 6, c = 7, d can be 9, 10 so 3 options.  If b = 7, c = 8 there are no options
-So if a = 5 there are 3 options.
-Finally, If a = 6, b = 7, c =8, there is just one option, d = 10
-So if a = 6 there is just 1 option
-Summing, 34 + 22 + 13 + 7 + 3 + 1 = 080, answer
-'''Solution 2'''
-There are "10 choose 4" total ways to choose a, b, c, and d(210).
-Do casework to find that there are 50 cases where a+d=b+c.  The number of cases where a+d}c is equal to the number of cases where a+d{c.  Therefore the answer is (210-50)/2='''80'''
-I apologize for the lack of explanation; I don't have enough time.

Page

Toolbox

Search

Difference between revisions of "2011 AIME II Problems/Problem 6"

Revision as of 01:05, 2 April 2011

Problem 6

Solution