Difference between revisions of "2016 AIME II Problems/Problem 13"
Mathgeek2006 (talk | contribs) m |
5849206328x (talk | contribs) |
||
(9 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
Beatrix is going to place six rooks on a <math>6 \times 6</math> chessboard where both the rows and columns are labeled <math>1</math> to <math>6</math>; the rooks are placed so that no two rooks are in the same row or the same column. The <math>value</math> of a square is the sum of its row number and column number. The <math>score</math> of an arrangement of rooks is the least value of any occupied square.The average score over all valid configurations is <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>. | Beatrix is going to place six rooks on a <math>6 \times 6</math> chessboard where both the rows and columns are labeled <math>1</math> to <math>6</math>; the rooks are placed so that no two rooks are in the same row or the same column. The <math>value</math> of a square is the sum of its row number and column number. The <math>score</math> of an arrangement of rooks is the least value of any occupied square.The average score over all valid configurations is <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>. | ||
− | ==Solution== | + | ==Solution 1== |
− | We casework to find the number of ways to get each possible score. Note that the lowest possible score is <math>2</math> and the highest possible score is <math>7</math>. Let the bijective function <math>f(x)=\{1,2,3,4,5,6\} \to \{1,2,3,4,5,6\}</math> denote the row number of the rook for the corresponding column number. For a score of <math>2</math>, we must have <math>f(1)=1</math>, and we can arrange the rest of the function however we want, so there are <math>5!=120</math> ways. For a score of <math>3</math>, we must have either <math>f(1)=2</math> or <math>f(2)=1</math>, and we can arrange the rest of the rooks however we want, so by PIE the number of ways is <math>5!+5!-4!=216</math>. For a score of <math>4</math>, we must have <math>f(1)=3</math>, <math>f(2)=2</math>, or <math>f(3)=1</math>. If <math>f(1)=3</math>, we just don't want <math>f(2)=1</math>, if <math>f(2)=2</math>, we don't want <math>f(1)=1</math>, or if <math>f(3)=1</math>, we don't want <math>f(1)=2</math>, otherwise we can arrange the function however we like. If at least <math>2</math> of the values rooks have a value of <math>4</math>, we can arange the rest of the rooks however we like, so there are <math>3(5!-4!)-3(4!)+3!=222</math> by PIE. If the score is <math>5</math>, then we have either <math>f(4)=1</math>, <math>f(3)=2</math>, <math>f(2)=3</math>, or <math>f(1)=4</math>. If we have the first case, we don't want <math>f(2)=2</math>, <math>f(1)=2</math>, or <math>f(1)=3</math>, so by PIE the number of bad cases is <math>4!+4!-3!=42</math>. If we have the second case, then we don't want <math>f(2)=1</math>, <math>f(1)=1</math>, or <math>f(1)=3</math>, so similarly there are <math>42</math> bad cases. Therefore, there are a total of <math>54</math> good cases for each one. The number of ways to get <math>f(1)=1, f(1)=4</math> is <math>4!-3!</math> because we don't want <math>f(2)=2</math>, the number of ways to get <math>f(4)=1, f(2)=3</math> is <math>4!-3!</math> ways because we don't want <math>f(1)=2</math>, the number of ways to get <math>f(2)=3, f(3)=2</math> is <math>4!-3!</math> ways because we don't want <math>f(1)=1</math>, and the number of ways to get <math>f(1)=4, f(2)=3</math> is <math>4!-3!</math> ways because we don't want <math>f(3)=1</math>. The number of ways to get at least <math>3</math> cases satisfied is <math> | + | We casework to find the number of ways to get each possible score. Note that the lowest possible score is <math>2</math> and the highest possible score is <math>7</math>. Let the bijective function <math>f(x)=\{1,2,3,4,5,6\} \to \{1,2,3,4,5,6\}</math> denote the row number of the rook for the corresponding column number. |
+ | |||
+ | *For a score of <math>2</math>, we must have <math>f(1)=1</math>, and we can arrange the rest of the function however we want, so there are <math>5!=120</math> ways. | ||
+ | |||
+ | *For a score of <math>3</math>, we must have either <math>f(1)=2</math> or <math>f(2)=1</math>, and we can arrange the rest of the rooks however we want, so by PIE the number of ways is <math>5!+5!-4!=216</math>. | ||
+ | |||
+ | *For a score of <math>4</math>, we must have <math>f(1)=3</math>, <math>f(2)=2</math>, or <math>f(3)=1</math>. If <math>f(1)=3</math>, we just don't want <math>f(2)=1</math>, if <math>f(2)=2</math>, we don't want <math>f(1)=1</math>, or if <math>f(3)=1</math>, we don't want <math>f(1)=2</math>, otherwise we can arrange the function however we like. If at least <math>2</math> of the values rooks have a value of <math>4</math>, we can arange the rest of the rooks however we like, so there are <math>3(5!-4!)-3(4!)+3!=222</math> by PIE. | ||
+ | |||
+ | *If the score is <math>5</math>, then we have either <math>f(4)=1</math>, <math>f(3)=2</math>, <math>f(2)=3</math>, or <math>f(1)=4</math>. If we have the first case, we don't want <math>f(2)=2</math>, <math>f(1)=2</math>, or <math>f(1)=3</math>, so by PIE the number of bad cases is <math>4!+4!-3!=42</math>. If we have the second case, then we don't want <math>f(2)=1</math>, <math>f(1)=1</math>, or <math>f(1)=3</math>, so similarly there are <math>42</math> bad cases. Therefore, there are a total of <math>54</math> good cases for each one. The number of ways to get <math>f(1)=1, f(1)=4</math> is <math>4!-3!</math> because we don't want <math>f(2)=2</math>, the number of ways to get <math>f(4)=1, f(2)=3</math> is <math>4!-3!</math> ways because we don't want <math>f(1)=2</math>, the number of ways to get <math>f(2)=3, f(3)=2</math> is <math>4!-3!</math> ways because we don't want <math>f(1)=1</math>, and the number of ways to get <math>f(1)=4, f(2)=3</math> is <math>4!-3!</math> ways because we don't want <math>f(3)=1</math>. The number of ways to get at least <math>3</math> cases satisfied is <math>3! \cdot 4</math> because we can arrange the remaining rooks however we like, and the number of ways to get all <math>4</math> cases satisfied is <math>2!=2</math> ways because we can arrange the remaining rooks however we like, so by PIE we have <math>54 \cdot 4-18 \cdot 6 + 3! \cdot 4-2!=130</math> ways to get a score of <math>5</math>. | ||
+ | |||
+ | *The only way to get a score of <math>7</math> is to have all the rooks run on the antidiagonal. Therefore, the number of ways to get a sum of <math>6</math> is <math>6!-120-216-222-130-1=31</math>. | ||
+ | Thus, the expected sum is <math>\dfrac{120 \cdot 2 + 216 \cdot 3 + 222 \cdot 4 + 130 \cdot 5 + 31 \cdot 6 + 1 \cdot 7}{720}= \dfrac{2619}{720}=\dfrac{291}{80}</math>, so the desired answer is <math>291+80=\boxed{371}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | If the score is <math>n+1</math>, then one of the rooks must appear in the <math>n</math>th antidiagonal, and this is the first antidiagonal in which a rook can appear. To demonstrate this, we draw the following diagram when <math>n=4</math>. | ||
+ | |||
+ | <asy> | ||
+ | for (int i=0;i<7;++i) {draw((0,10*i)--(60,10*i));draw((10*i,0)--(10*i,60));} | ||
+ | path x=(1,1)--(9,9),y=(1,9)--(9,1); | ||
+ | for (int i=0;i<3;++i) {for (int j=3+i;j<6;++j) {draw(shift(10*i,10*j)*x,linewidth(1));draw(shift(10*i,10*j)*y,linewidth(1));}} | ||
+ | for (int i=0;i<4;++i) {filldraw((10*i,20+10*i)--(10*i+10,20+10*i)--(10*i+10,20+10*i+10)--(10*i,20+10*i+10)--cycle,lightgray);} | ||
+ | </asy> | ||
+ | We first count the number of arrangements that avoid the squares above the <math>n</math>th diagonal, and then we subtract from these the number of arrangements that avoid all squares above the <math>(n+1)</math>th diagonal. In the first column, there are <math>7-n</math> rows in which to place the rook. In the second column, there is one more possible row, but one of the rows is used up by the rook in the first column, hence there are still <math>7-n</math> places to place the rook. This pattern continues through the <math>n</math>th column, so there are <math>(7-n)^n</math> ways to place the first <math>n</math> rooks while avoiding the crossed out squares. We can similarly compute that there are <math>(6-n)^n</math> ways to place the rooks in the first <math>n</math> columns that avoid both the crossed out and shaded squares. Therefore, there are <math>(7-n)^n-(6-n)^n</math> ways to place the first <math>n</math> rooks such that at least one of them appears in a shaded square. | ||
+ | |||
+ | After this, there are <math>(6-n)</math> rows and <math>(6-n)</math> columns in which to place the remaining rooks, and we can do this in <math>(6-n)!</math> ways. Hence the number of arrangements with a score of <math>n</math> is <math>((7-n)^n-(6-n)^n)\cdot(6-n)!</math>. We also know that <math>n</math> can range from from <math>1</math> to <math>6</math>, so the average score is given by | ||
+ | |||
+ | <cmath>\frac{2\cdot(6^1-5^1)\cdot5!+3\cdot(5^2-4^2)\cdot4!+4\cdot(4^3-3^3)\cdot3!+5\cdot(3^4-2^4)\cdot 2!+6\cdot(2^5-1^5)\cdot 1!+7\cdot(1^6-0^6)\cdot 0!}{6!}=\frac{291}{80}.</cmath> | ||
+ | Thus the answer is <math>\boxed{371}</math>. | ||
+ | |||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | So we first count the number of permutations with score <math>\ge 2</math>. This is obviously <math>6!=720</math>. Then, the number of permutations with score <math>\ge 3</math> can also be computed: in the first column, there are five ways to place a rook- anywhere but the place with score <math>1</math>. In the next column, there are <math>5</math> ways to place a rook- anywhere but the one in the same row as the previous row. We can continue this to obtain that the number of permutations with score <math>\ge 3</math> is <math>600</math>. Doing the same for scores <math>\ge 4</math>, <math>\ge 5</math>, <math>\ge 6</math>, and <math>\ge 7</math> we obtain that these respective numbers are <math>384</math>, <math>162</math>, <math>32</math>, <math>1</math>. | ||
+ | |||
+ | Now, note that if <math>a_k</math> is the number of permutations with score <math>\ge k</math>, then <math>a_k-a_{k-1}=b_{k}</math>, where <math>b_k</math> is the number of permutations with score exactly <math>k</math>. Thus, we can compute the number of permutations with scores <math>2</math>, <math>3</math>, etc as <math>120,216,222,130,31,1</math>. We then compute <cmath>\frac{120(2)+216(3)+222(4)+130(5)+31(6)+1(7)}{720}=\frac{291}{80}</cmath> leading us to the answer of <math>291+80=\boxed{371}</math>. <math>\blacksquare</math> | ||
+ | |||
+ | ===Note=== | ||
+ | |||
+ | This problem is pretty bashy. There isn't a clever way to solve it. | ||
+ | |||
+ | |||
+ | ==Solution 4 (builds off Solution 3)== | ||
+ | |||
+ | The problem is asking us to compute <math>\mathbb{E}[S]</math>, where <math>S</math> is the random variable that takes an arrangement of rooks and outputs its score, which is a non-negative integer quantity. For any random variable <math>S</math> with non-negative integer values, we have the tail sum formula | ||
+ | <cmath> \mathbb{E}[S] = \sum_{n = 1}^{\infty}\mathbb{P}(S\geq n). </cmath> | ||
+ | These probabilities can be computed as in Solution 3, giving us the following table. | ||
+ | {| class="wikitable" | style="margin-left: auto; margin-right: auto; text-align: center;" | ||
+ | |+ Probabilities (out of 720) | ||
+ | |- | ||
+ | | <math>n</math> || <math>1</math> || <math>2</math> || <math>3</math> || <math>4</math> || <math>5</math> || <math>6</math> || <math>7</math> || <math>\geq 8</math> | ||
+ | |- | ||
+ | | <math>\mathbb{P}(S\geq n)</math> || <math>720</math> || <math>720</math> || <math>600</math> || <math>384</math> || <math>162</math> || <math>32</math> || <math>1</math> || <math>0</math> | ||
+ | |} | ||
+ | Hence | ||
+ | <cmath>\begin{align*} | ||
+ | \mathbb{E}[S] &= \frac{720 + 720 + 600 + 384 + 162 + 32 + 1}{720} \\ | ||
+ | &= 2 + \frac{1179}{720} = 2 + \frac{131}{80} = \frac{291}{80}, | ||
+ | \end{align*}</cmath> | ||
+ | and the final answer is <math>291 + 80 = \boxed{371}</math> as above. | ||
+ | |||
+ | ===Tail sum formula=== | ||
+ | |||
+ | The definition of expected value corresponds to summing the entries of the grid going column by column first, then adding up the column sums, whereas the tail sum formula corresponds to summing the entries of the grid going row by row first, then adding up the row sums. (Since all entries are non-negative, rearrangement of a potentially-infinite sum is no issue.) | ||
+ | <cmath>\begin{array}{cccccc} | ||
+ | \mathbb{P}(S = 1) & \mathbb{P}(S = 2) & \mathbb{P}(S = 3) & \mathbb{P}(S = 4) & \mathbb{P}(S = 5) & \cdots \\ | ||
+ | {} & \mathbb{P}(S = 2) & \mathbb{P}(S = 3) & \mathbb{P}(S = 4) & \mathbb{P}(S = 5) & \cdots \\ | ||
+ | {} & {} & \mathbb{P}(S = 3) & \mathbb{P}(S = 4) & \mathbb{P}(S = 5) & \cdots \\ | ||
+ | {} & {} & {} & \mathbb{P}(S = 4) & \mathbb{P}(S = 5) & \cdots \\ | ||
+ | {} & {} & {} & {} & \mathbb{P}(S = 5) & \cdots \\ | ||
+ | {} & {} & {} & {} & {} & \cdots \\ | ||
+ | \end{array}</cmath> | ||
− | |||
== See also == | == See also == | ||
{{AIME box|year=2016|n=II|num-b=12|num-a=14}} | {{AIME box|year=2016|n=II|num-b=12|num-a=14}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 16:53, 1 December 2021
Contents
Problem
Beatrix is going to place six rooks on a chessboard where both the rows and columns are labeled
to
; the rooks are placed so that no two rooks are in the same row or the same column. The
of a square is the sum of its row number and column number. The
of an arrangement of rooks is the least value of any occupied square.The average score over all valid configurations is
, where
and
are relatively prime positive integers. Find
.
Solution 1
We casework to find the number of ways to get each possible score. Note that the lowest possible score is and the highest possible score is
. Let the bijective function
denote the row number of the rook for the corresponding column number.
- For a score of
, we must have
, and we can arrange the rest of the function however we want, so there are
ways.
- For a score of
, we must have either
or
, and we can arrange the rest of the rooks however we want, so by PIE the number of ways is
.
- For a score of
, we must have
,
, or
. If
, we just don't want
, if
, we don't want
, or if
, we don't want
, otherwise we can arrange the function however we like. If at least
of the values rooks have a value of
, we can arange the rest of the rooks however we like, so there are
by PIE.
- If the score is
, then we have either
,
,
, or
. If we have the first case, we don't want
,
, or
, so by PIE the number of bad cases is
. If we have the second case, then we don't want
,
, or
, so similarly there are
bad cases. Therefore, there are a total of
good cases for each one. The number of ways to get
is
because we don't want
, the number of ways to get
is
ways because we don't want
, the number of ways to get
is
ways because we don't want
, and the number of ways to get
is
ways because we don't want
. The number of ways to get at least
cases satisfied is
because we can arrange the remaining rooks however we like, and the number of ways to get all
cases satisfied is
ways because we can arrange the remaining rooks however we like, so by PIE we have
ways to get a score of
.
- The only way to get a score of
is to have all the rooks run on the antidiagonal. Therefore, the number of ways to get a sum of
is
.
Thus, the expected sum is , so the desired answer is
.
Solution 2
If the score is , then one of the rooks must appear in the
th antidiagonal, and this is the first antidiagonal in which a rook can appear. To demonstrate this, we draw the following diagram when
.
We first count the number of arrangements that avoid the squares above the
th diagonal, and then we subtract from these the number of arrangements that avoid all squares above the
th diagonal. In the first column, there are
rows in which to place the rook. In the second column, there is one more possible row, but one of the rows is used up by the rook in the first column, hence there are still
places to place the rook. This pattern continues through the
th column, so there are
ways to place the first
rooks while avoiding the crossed out squares. We can similarly compute that there are
ways to place the rooks in the first
columns that avoid both the crossed out and shaded squares. Therefore, there are
ways to place the first
rooks such that at least one of them appears in a shaded square.
After this, there are rows and
columns in which to place the remaining rooks, and we can do this in
ways. Hence the number of arrangements with a score of
is
. We also know that
can range from from
to
, so the average score is given by
Thus the answer is
.
Solution 3
So we first count the number of permutations with score . This is obviously
. Then, the number of permutations with score
can also be computed: in the first column, there are five ways to place a rook- anywhere but the place with score
. In the next column, there are
ways to place a rook- anywhere but the one in the same row as the previous row. We can continue this to obtain that the number of permutations with score
is
. Doing the same for scores
,
,
, and
we obtain that these respective numbers are
,
,
,
.
Now, note that if is the number of permutations with score
, then
, where
is the number of permutations with score exactly
. Thus, we can compute the number of permutations with scores
,
, etc as
. We then compute
leading us to the answer of
.
Note
This problem is pretty bashy. There isn't a clever way to solve it.
Solution 4 (builds off Solution 3)
The problem is asking us to compute , where
is the random variable that takes an arrangement of rooks and outputs its score, which is a non-negative integer quantity. For any random variable
with non-negative integer values, we have the tail sum formula
These probabilities can be computed as in Solution 3, giving us the following table.
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Hence
and the final answer is
as above.
Tail sum formula
The definition of expected value corresponds to summing the entries of the grid going column by column first, then adding up the column sums, whereas the tail sum formula corresponds to summing the entries of the grid going row by row first, then adding up the row sums. (Since all entries are non-negative, rearrangement of a potentially-infinite sum is no issue.)
See also
2016 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.