Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Problem 6)
m
Line 4: Line 4:
  
 
==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:
+
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 integer parts. Via a standard balls and urns argument, the number of ways to partition 6 into 5 non-negative parts is <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>.
+
<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 integer parts. Via a standard balls and urns argument, the number of ways to partition 6 into 5 non-negative parts is <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>.
  
 
We find <math>N</math> as a sum of 4 cases:
 
We find <math>N</math> as a sum of 4 cases:
Line 13: Line 13:
 
* two parts equal to three, <math>\binom22 = 1</math> way.
 
* two parts equal to three, <math>\binom22 = 1</math> way.
 
Therefore, <math>N = 28 + 15 + 6 + 1 = 50</math> and our answer is <math>(210 - 50)/2 = \fbox{80.}</math>
 
Therefore, <math>N = 28 + 15 + 6 + 1 = 50</math> and our answer is <math>(210 - 50)/2 = \fbox{80.}</math>
 +
 +
==See also==
 +
{{AIME box|year=2011|n=II|num-b=5|num-a=7}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 10:36, 23 August 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 interesting 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 integer parts. Via a standard balls and urns argument, the number of ways to partition 6 into 5 non-negative parts is $\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.}$

See also

2011 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 5 		Followed by
Problem 7
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_6&oldid=41880"