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"
m (→‎Solution 7 (Slightly Slower))
 
(44 intermediate revisions by 25 users not shown)
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 of integers <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 interesting ordered quadruples are there?
  
−
----
+
==Solution 1==
−
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 integer parts. Via a standard stars and bars 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 are 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:
 +
* two parts equal to zero, <math>\binom82 = 28</math> ways,
 +
* two parts equal to one, <math>\binom62 = 15</math> ways,
 +
* two parts equal to two, <math>\binom42 = 6</math> ways,
 +
* 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{080}</math>
 +
 
 +
==Solution 2==
 +
Let us consider our quadruple <math>(a,b,c,d)</math> as the following image <math>xaxbcxxdxx</math>. The location of the letter <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> represents its value and <math>x</math> is a place holder. Clearly the quadruple is interesting if there are more place holders between <math>c</math> and <math>d</math> than there are between <math>a</math> and <math>b</math>.
 +
 
 +
<math>0</math> holders between <math>a</math> and <math>b</math> means we consider <math>a</math> and <math>b</math> as one unit <math>ab</math> and <math>c</math> as <math>cx</math> yielding <math>\binom83 = 56</math> ways;
 +
 
 +
<math>1</math> holder between <math>a</math> and <math>b</math> means we consider <math>a</math> and <math>b</math> as one unit <math>axb</math> and <math>c</math> as <math>cxx</math> yielding <math>\binom 63 = 20</math> ways;
 +
 
 +
<math>2</math> holders between <math>a</math> and <math>b</math> means we consider <math>a</math> and <math>b</math> as one unit <math>axxb</math> and <math>c</math> as <math>cxxx</math> yielding <math>\binom43 = 4</math> ways.
 +
 
 +
Since there cannot be <math>3</math> holders between <math>a</math> and <math>b</math> so our total is <math>56+20+4=\fbox{080}</math>.
 +
 
 +
==Solution 3 (<i>Slightly</i> bashy)==
 +
We first start out when the value of <math>a=1</math>.
 +
 
 +
Doing casework, we discover that <math>d=5,6,7,8,9,10</math>. We quickly find a pattern.
 +
 
 +
Now, doing this for the rest of the values of <math>a</math> and <math>d</math>, we see that the answer is simply:
 +
 
 +
 
 +
<math>(1)+(2)+(1+3)+(2+4)+(1+3+5)+(2+4+6)+(1)+(2)+(1+3)+(2+4)</math>
 +
<math>+(1+3+5)+(1)+(2)+(1+3)+(2+4)+(1)+(2)+(1+3)+(1)+(2)+(1)=\boxed{080}</math>
 +
 
 +
==Solution 4 (quick)==
 +
 
 +
Notice that if <math>a+d>b+c</math>, then <math>(11-a)+(11-d)<(11-b)+(11-c)</math>, so there is a [[bijection]] between the number of ordered quadruples with <math>a+d>b+c</math> and the number of ordered quadruples with <math>a+d<b+c</math>.
 +
 
 +
Quick counting gives that the number of ordered quadruples with <math>a+d=b+c</math> is 50. To count this, consider our numbers <math>1, 2, 3, 4, 5, 6, 7, 8, 9, 10</math>. Notice that if, for example, <math>a+d=b+c=8</math>, that the average of <math>a,d</math> and <math>b,c</math> must both be <math>4</math>. In this way, there is a symmetry for this case, centered at <math>4</math>. If instead, say, <math>a+d=b+c=7</math>, an odd number, then there is symmetry with <math>(a,d);(b,c)</math> about <math>3.5</math>. Further, the number of cases for each of these centers of symmetry correspond to a triangular number. Eg centered at <math>2.5,3,8,8.5</math>, there is <math>1</math> case for each and so on, until centered at <math>5.5</math>, there are <math>10</math> possible cases. Adding these all, we have <math>2(1+3+6)+10=50</math>.
 +
 
 +
Thus the answer is <math>\frac{\binom{10}{4}-50}{2} = \boxed{080}.</math>
 +
 
 +
==Solution 5==
 +
 
 +
Think about a,b,c,and d as distinct objects, that we must place in 4 of 10 spaces. However, in only 1 of 24 of these combinations, will the placement of these objects satisfy the condition in the problem. So we know the total number of ordered quadruples is <math>(10*9*8*7/24)=210</math>
 +
 
 +
Next, intuitively, the number of quadruples where <math>a+d>b+c</math> is equal to the number of quadruples where <math>a+d<b+c</math>. So we need to find the number of quadruples where the two quantities are equal. To do this, all we have to do is consider the cases when <math>a-d</math> ranges from 3 to 9. It would seem natural that a range of 3 would produce 1 option, and a range of 4 would produce 2 options. However, since b and c cannot be equal, a range of 3 or 4 produces 1 option each, a range of 5 or 6 produces 2 options each, a range of 7 or 8 produces 3 options each, and a range of 9 will produce 4 options. In addition, a range of n has 10-n options for combinations of a and d. Multiplying the number of combinations of a and d by the corresponding number of options for b and c gives us 50 total quadruplets where <math>a+d=b+c</math>.
 +
 
 +
So the answer will be <math>\frac{210-50}{2} = \boxed{080}.</math>
 +
 
 +
 
 +
 
 +
== Solution 6 ==
 +
 
 +
 
 +
Let <math>b = a+x</math> and <math>c = a+x+y</math> and <math>d = a+x+y+z</math> for positive integers <math>x,y,z.</math> In order to satisfy the other condition we need <math>z > x</math> so we let <math>z = x+k.</math> Now the only other condition we need to satisfy so <math>a+2x+y+k \le 10.</math> This condition can be transformed into <math>a+2x+y+k+b  = 11</math> for positive <math>a,x,y,k,b.</math> Now we use generating functions to finish. We find the generating function of the whole expression is <math>(x + x^2 + \cdots)^4 \cdot (x^2+x^4 + \cdots)</math> and we are looking for the <math>x^{11}</math> coefficient. This simplifies to finding the <math>x^5</math> coefficient of <math>(1+x+\cdots)^4 \cdot (1+x^2+\cdots) =\frac{1}{(1-x)^4} \cdot\frac{1}{1+x}.</math> Now this expression simplifies to <cmath>\left(\binom{4}{4}+\binom{5}{4} + \cdots +\binom{4+k}{4}x^k\right)(1-x+x^2-x^3 \cdots).</cmath> The <math>x^5</math> coefficient ends up to be <math>\binom{9}{4} -\binom{8}{4} +\binom{7}{4} -\binom{6}{4} +\binom{5}{4} -\binom{4}{4} = 126 - 70 + 35 - 15 + 5 - 1 = \boxed{080}.</math>
 +
 
 +
== Solution 7 (<i>Slightly Slower</i>)==
 +
 
 +
First, let <math>a=1</math> and <math>d=10</math>. If <math>b=2</math>, then <math>c</math> can be from <math>3</math> to <math>8</math>. If <math>b=3</math>, then <math>4</math> to <math>7</math>. If <math>b=4</math>, then <math>c</math> is between <math>5</math> and <math>6</math>. We find a pattern that whenever <math>b</math> increases by <math>1</math>, when <math>a</math> and <math>d</math> are stationary, then the possible values of <math>c</math> decrease by 2, unless it gets to zero or negative, in which case that case ends. Counting up, we have <math>6+4+2=12</math> different possibilities when <math>a=1</math> and <math>d=10</math>. For <math>a=1</math> and <math>d=9</math>, <math>b=2</math>, then <math>c</math> can be from <math>3</math> to <math>7</math>. If <math>b=3</math>, then <math>c</math> can be from <math>4</math> to <math>6</math>, and so on. Notice that the possible values for each case of <math>b</math> gets one less than if <math>d</math> were one greater, unless that number is zero, in which it stays zero. We then use this pattern to find all the values: <math>12+9+6+4+2+1+9+6+4+2+1+6+4+2+1+4+2+1+2+1+1 \Rightarrow  \\ 12\cdot1+9\cdot2+6\cdot3+4\cdot4+2\cdot5+1\cdot6= \\ 12+18+18+16+10+6=\boxed{\textbf{080}}.</math>
 +
 
 +
~[[User:Sweetmango77|SweetMango77]]
 +
 
 +
=== Note ===
 +
Note that the first value of each of the rows, if we arrange them based on values of <math>a</math>, is deleted after each row.
 +
 
 +
== Solution 8 ==
 +
Rearranging the equation obtains <math>b-a<d-c</math>. Let <math>a-0=e_0</math>, <math>b-a=e_3+e_1</math>, <math>c-b=e_2</math>, <math>d-c=e_3</math>, <math>11-d=e_4</math>. Add up all of these newly defined equations to obtain <math>e_0+e_1+e_2+2e_3+e_4=11</math>. Note that since all <math>e_n</math> were defined to be <math>e_n\ge1</math>, to form our stars and bars argument we can let <math>d_n+1=e_n</math> for all <math>n</math>. Then we obtain <math>d_0+d_1+d_2+2d_3+d_4=5</math> where <math>d_n</math> is nonnegative. Now, we can move the <math>2d_3</math> term to the other side and perform casework.
 +
 
 +
If <math>2d_3=0</math>: 5 objects for 4 variables -> <math>\binom{8}{3}</math>
 +
 
 +
If <math>2d_3=2</math>: 3 objects for 4 variables -> <math>\binom{6}{3}</math>
 +
 
 +
If <math>2d_3=4</math>: 1 object for 4 variables -> <math>\binom{4}{3}</math>
 +
 
 +
Adding all of these cases up, we get <math>56+20+4=\boxed{080}</math> as our requested answer.  
 +
 
 +
~sigma
 +
 
 +
 
 +
==See also==
 +
{{AIME box|year=2011|n=II|num-b=5|num-a=7}}
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 00:28, 16 January 2023

Problem 6

Define an ordered quadruple of integers $(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 1

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 stars and bars 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 are 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{080}$

Solution 2

Let us consider our quadruple $(a,b,c,d)$ as the following image $xaxbcxxdxx$. The location of the letter $a$, $b$, $c$, $d$ represents its value and $x$ is a place holder. Clearly the quadruple is interesting if there are more place holders between $c$ and $d$ than there are between $a$ and $b$.

$0$ holders between $a$ and $b$ means we consider $a$ and $b$ as one unit $ab$ and $c$ as $cx$ yielding $\binom83 = 56$ ways;

$1$ holder between $a$ and $b$ means we consider $a$ and $b$ as one unit $axb$ and $c$ as $cxx$ yielding $\binom 63 = 20$ ways;

$2$ holders between $a$ and $b$ means we consider $a$ and $b$ as one unit $axxb$ and $c$ as $cxxx$ yielding $\binom43 = 4$ ways.

Since there cannot be $3$ holders between $a$ and $b$ so our total is $56+20+4=\fbox{080}$.

Solution 3 (Slightly bashy)

We first start out when the value of $a=1$.

Doing casework, we discover that $d=5,6,7,8,9,10$. We quickly find a pattern.

Now, doing this for the rest of the values of $a$ and $d$, we see that the answer is simply:


$(1)+(2)+(1+3)+(2+4)+(1+3+5)+(2+4+6)+(1)+(2)+(1+3)+(2+4)$ $+(1+3+5)+(1)+(2)+(1+3)+(2+4)+(1)+(2)+(1+3)+(1)+(2)+(1)=\boxed{080}$

Solution 4 (quick)

Notice that if $a+d>b+c$, then $(11-a)+(11-d)<(11-b)+(11-c)$, so there is a bijection between the number of ordered quadruples with $a+d>b+c$ and the number of ordered quadruples with $a+d<b+c$.

Quick counting gives that the number of ordered quadruples with $a+d=b+c$ is 50. To count this, consider our numbers $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$. Notice that if, for example, $a+d=b+c=8$, that the average of $a,d$ and $b,c$ must both be $4$. In this way, there is a symmetry for this case, centered at $4$. If instead, say, $a+d=b+c=7$, an odd number, then there is symmetry with $(a,d);(b,c)$ about $3.5$. Further, the number of cases for each of these centers of symmetry correspond to a triangular number. Eg centered at $2.5,3,8,8.5$, there is $1$ case for each and so on, until centered at $5.5$, there are $10$ possible cases. Adding these all, we have $2(1+3+6)+10=50$.

Thus the answer is $\frac{\binom{10}{4}-50}{2} = \boxed{080}.$

Solution 5

Think about a,b,c,and d as distinct objects, that we must place in 4 of 10 spaces. However, in only 1 of 24 of these combinations, will the placement of these objects satisfy the condition in the problem. So we know the total number of ordered quadruples is $(10*9*8*7/24)=210$

Next, intuitively, the number of quadruples where $a+d>b+c$ is equal to the number of quadruples where $a+d<b+c$. So we need to find the number of quadruples where the two quantities are equal. To do this, all we have to do is consider the cases when $a-d$ ranges from 3 to 9. It would seem natural that a range of 3 would produce 1 option, and a range of 4 would produce 2 options. However, since b and c cannot be equal, a range of 3 or 4 produces 1 option each, a range of 5 or 6 produces 2 options each, a range of 7 or 8 produces 3 options each, and a range of 9 will produce 4 options. In addition, a range of n has 10-n options for combinations of a and d. Multiplying the number of combinations of a and d by the corresponding number of options for b and c gives us 50 total quadruplets where $a+d=b+c$.

So the answer will be $\frac{210-50}{2} = \boxed{080}.$


Solution 6

Let $b = a+x$ and $c = a+x+y$ and $d = a+x+y+z$ for positive integers $x,y,z.$ In order to satisfy the other condition we need $z > x$ so we let $z = x+k.$ Now the only other condition we need to satisfy so $a+2x+y+k \le 10.$ This condition can be transformed into $a+2x+y+k+b = 11$ for positive $a,x,y,k,b.$ Now we use generating functions to finish. We find the generating function of the whole expression is $(x + x^2 + \cdots)^4 \cdot (x^2+x^4 + \cdots)$ and we are looking for the $x^{11}$ coefficient. This simplifies to finding the $x^5$ coefficient of $(1+x+\cdots)^4 \cdot (1+x^2+\cdots) =\frac{1}{(1-x)^4} \cdot\frac{1}{1+x}.$ Now this expression simplifies to \[\left(\binom{4}{4}+\binom{5}{4} + \cdots +\binom{4+k}{4}x^k\right)(1-x+x^2-x^3 \cdots).\] The $x^5$ coefficient ends up to be $\binom{9}{4} -\binom{8}{4} +\binom{7}{4} -\binom{6}{4} +\binom{5}{4} -\binom{4}{4} = 126 - 70 + 35 - 15 + 5 - 1 = \boxed{080}.$

Solution 7 (Slightly Slower)

First, let $a=1$ and $d=10$. If $b=2$, then $c$ can be from $3$ to $8$. If $b=3$, then $4$ to $7$. If $b=4$, then $c$ is between $5$ and $6$. We find a pattern that whenever $b$ increases by $1$, when $a$ and $d$ are stationary, then the possible values of $c$ decrease by 2, unless it gets to zero or negative, in which case that case ends. Counting up, we have $6+4+2=12$ different possibilities when $a=1$ and $d=10$. For $a=1$ and $d=9$, $b=2$, then $c$ can be from $3$ to $7$. If $b=3$, then $c$ can be from $4$ to $6$, and so on. Notice that the possible values for each case of $b$ gets one less than if $d$ were one greater, unless that number is zero, in which it stays zero. We then use this pattern to find all the values: $12+9+6+4+2+1+9+6+4+2+1+6+4+2+1+4+2+1+2+1+1 \Rightarrow \\ 12\cdot1+9\cdot2+6\cdot3+4\cdot4+2\cdot5+1\cdot6= \\ 12+18+18+16+10+6=\boxed{\textbf{080}}.$

~SweetMango77

Note

Note that the first value of each of the rows, if we arrange them based on values of $a$, is deleted after each row.

Solution 8

Rearranging the equation obtains $b-a<d-c$. Let $a-0=e_0$, $b-a=e_3+e_1$, $c-b=e_2$, $d-c=e_3$, $11-d=e_4$. Add up all of these newly defined equations to obtain $e_0+e_1+e_2+2e_3+e_4=11$. Note that since all $e_n$ were defined to be $e_n\ge1$, to form our stars and bars argument we can let $d_n+1=e_n$ for all $n$. Then we obtain $d_0+d_1+d_2+2d_3+d_4=5$ where $d_n$ is nonnegative. Now, we can move the $2d_3$ term to the other side and perform casework.

If $2d_3=0$: 5 objects for 4 variables -> $\binom{8}{3}$

If $2d_3=2$: 3 objects for 4 variables -> $\binom{6}{3}$

If $2d_3=4$: 1 object for 4 variables -> $\binom{4}{3}$

Adding all of these cases up, we get $56+20+4=\boxed{080}$ as our requested answer.

~sigma


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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_6&oldid=186710"