Difference between revisions of "2006 AIME II Problems/Problem 4"

Latest revision as of 13:12, 20 April 2024

Problem

Let $(a_1,a_2,a_3,\ldots,a_{12})$ be a permutation of $(1,2,3,\ldots,12)$ for which

$a_1>a_2>a_3>a_4>a_5>a_6 \mathrm{\ and \ } a_6<a_7<a_8<a_9<a_{10}<a_{11}<a_{12}.$

An example of such a permutation is $(6,5,4,3,2,1,7,8,9,10,11,12).$ Find the number of such permutations.

Solution

Clearly, $a_6=1$ . Now, consider selecting $5$ of the remaining $11$ values. Sort these values in descending order, and sort the other $6$ values in ascending order. Now, let the $5$ selected values be $a_1$ through $a_5$ , and let the remaining $6$ be $a_7$ through ${a_{12}}$ . It is now clear that there is a bijection between the number of ways to select $5$ values from $11$ and ordered 12-tuples $(a_1,\ldots,a_{12})$ . Thus, there will be ${11 \choose 5}=\boxed{462}$ such ordered 12-tuples.

Solution 2

There are $\binom{12}{6}$ ways to choose 6 numbers from $(1,2,3,\ldots,12)$ , and then there will only be one way to order them. And since that $a_6<a_7$ , only half of the choices will work, so the answer is $\frac{\binom{12}{6}}{2}=462$ 12-tuples - mathleticguyyy

Solution 3

Clearly, $a_6=1$ , and either $a_1$ or $a_{12}$ is 12.

Case 1: $a_1 = 12$

In this case, there are 4 empty spaces between $a_1$ and $a_6$ , and 6 empty spaces between $a_6$ and $a_{12}$ . $\binom{10}{4}$ is 210. This splits the remaining 10 numbers into two distinct sets that are automatically ordered. For this reason, there is no need to multiply by two to count doubles or treat as a permutation.

Case 2: $a_{12} = 12$

In this case, there are 5 empty spaces between $a_1$ and $a_6$ , and 5 empty spaces between $a_6$ and $a_{12}$ . $\binom{10}{5}$ is 252. Like last time, this splits the remaining 10 numbers into two distinct sets that are automatically ordered. It is important to realize that the two sets are distinct because one side has 12 and the other does not. There is no need to multiply by two.

$210 + 252 = \boxed{462}$ ordered 12-tuples.

-jackshi2006

@@ Line 1: / Line 1: @@
-#REDIRECT [[2006 AIME A Problems/Problem 4]]
+== Problem ==
+Let <math> (a_1,a_2,a_3,\ldots,a_{12}) </math> be a permutation of <math> (1,2,3,\ldots,12) </math> for which
+<center><math> a_1>a_2>a_3>a_4>a_5>a_6 \mathrm{\  and \ } a_6<a_7<a_8<a_9<a_{10}<a_{11}<a_{12}. </math></center>
+An example of such a permutation is <math> (6,5,4,3,2,1,7,8,9,10,11,12). </math> Find the number of such permutations.
+== Solution ==
+Clearly, <math>a_6=1</math>.  Now, consider selecting <math>5</math> of the remaining <math>11</math> values.  Sort these values in descending order, and sort the other <math>6</math> values in ascending order.  Now, let the <math>5</math> selected values be <math>a_1</math> through <math>a_5</math>, and let the remaining <math>6</math> be <math>a_7</math> through <math>{a_{12}}</math>.  It is now clear that there is a [[bijection]] between the number of ways to select <math>5</math> values from <math>11</math> and ordered 12-tuples <math>(a_1,\ldots,a_{12})</math>.  Thus, there will be <math>{11 \choose 5}=\boxed{462}</math> such ordered 12-tuples.
+== Solution 2 ==
+There are <math>\binom{12}{6}</math> ways to choose 6 numbers from <math> (1,2,3,\ldots,12) </math>, and then there will only be one way to order them. And since that <math>a_6<a_7</math>, only half of the choices will work, so the answer is <math>\frac{\binom{12}{6}}{2}=462</math> 12-tuples - mathleticguyyy
+==Solution 3==
+Clearly, <math>a_6=1</math>, and either <math>a_1</math> or <math>a_{12}</math> is 12.
+Case 1: <math>a_1 = 12</math>
+In this case, there are 4 empty spaces between <math>a_1</math> and <math>a_6</math>, and 6 empty spaces between <math>a_6</math> and <math>a_{12}</math>. <math>\binom{10}{4}</math> is 210. This splits the remaining 10 numbers into two distinct sets that are automatically ordered. For this reason, there is no need to multiply by two to count doubles or treat as a permutation.
+Case 2: <math>a_{12} = 12</math>
+In this case, there are 5 empty spaces between <math>a_1</math> and <math>a_6</math>, and 5 empty spaces between <math>a_6</math> and <math>a_{12}</math>. <math>\binom{10}{5}</math> is 252. Like last time, this splits the remaining 10 numbers into two distinct sets that are automatically ordered. It is important to realize that the two sets are distinct because one side has 12 and the other does not. There is no need to multiply by two.
+<math>210 + 252 = \boxed{462}</math> ordered 12-tuples.
+-jackshi2006
+== See also ==
+{{AIME box|year=2006|n=II|num-b=3|num-a=5}}
+[[Category:Intermediate Combinatorics Problems]]
+{{MAA Notice}}

2006 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search