Difference between revisions of "2016 UMO Problems/Problem 2"

Latest revision as of 13:53, 7 December 2021

Problem

Four fair six-sided dice are rolled. What is the probability that they can be divided into two pairs which sum to the same value? For example, a roll of $(1,4,6,3)$ can be divided into $(1,6)$ and $(4,3)$ , each of which sum to $7$ , but a roll of $(1,1,5,2)$ cannot be divided into two pairs that sum to the same value.

Solution 1

We split this into cases based on the the form of the unordered values shown on the dice. In the following, $1 <= a,b,c,d <= 6$ are distinct numbers. After determining the (unordered) numbers that can appear on the dice, we must determine how many ways we can order those dice rolls in sequence.

Case1: The unordered numbers shown are {a,a,a,a} In this case, it is clear that the pairing (a,a) and (a,a) will yield equal sums, so we have 6 possible choices for a, and this is the number of possible rolls that take this form.

Case2: The unordered numbers shown are {a,a,a,b} In this case, one of the pairs will contain b, hence the pairs will be (a,b) and (a,a). But these can never be equal as a 6= b.

Case3: The unordered numbers shown are {a,a,b,b} To obtain equal sums, we must split the numbers into the pairs (a,b) and (a,b). There are $\binom{6}{2}= 15$ ways to select a and b, and there are $\binom{4}{2}= 6$ ways to order the rolls (select two of the rolls to be a’s). Hence there are 15·6 = 90 total rolls that take this form.

Case4: The unordered numbers shown are {a,a,b,c} In this case, either b pairs with a or b pairs with c. If b pairs with a, then $a + b = c + a$ , which is impossible as $b \ne c$ . Therefore, b must pair with c, so $2a = b + c$ . Therefore, b + c is even. We may assume without loss of generality that $b <= c$ , hence the possibilities for (b,c) are (b,c) = (1,3),(1,5),(2,4),(2,6),(3,5),(4,6). Therefore, there are six ways to choose (b,c), and a is automatically determined (it is the average of b and c). Then there are 4! 2! = 12 ways to order the rolls, hence there are $6\cdot 12 = 72$ total rolls that take this form.

Case5: The unordered numbers shown are {a,b,c,d} In this case, the sum of the pairs must be representable in at two ways with distinct integers. We ﬁnd 5 = 1 + 4 = 2 + 3; 6 = 1 + 5 = 2 + 4; 7 = 1 + 6 = 2 + 5 = 3 + 4; 8 = 2 + 6 = 3 + 5; 9 = 3 + 6 = 4 + 5. These are the only numbers that can be represented as the sum of two numbers in at least two ways using distinct numbers. In particular, for the numbers $5,6,8,9$ ,we know immediately what the four numbers a,b,c,d are. For 7,we must choose two of the three pairs, and we can do this in three ways. Therefore, the number of ways to choose {a,b,c,d} is $1+1+1+1+3 = 7$ . Then we can order the rolls in 4! = 24 ways. Thus there are $7\cdot 24 = 168$ total rolls that take this form. Adding these together, we ﬁnd $6 + 90 + 72 + 168 = 336$ possibilities, so the answer is $\frac{336}{64} = \frac{7}{27}$ .

Solution 2

We observe $\textbf{Probability}=\frac{\textbf{Favorable}}{\textbf{Total}}.$

We have $\textbf{Total}=6^4=1296.$

We now work on the favorable cases.

Suppose the four numbers, $a,b,c,$ and $d$ can be split as $N=a+b=c+d.$ We do casework on the value of $N.$ Notice that a sum of $n$ can be obtained in the same number of ways as a sum of $14-n$ can be obtained. Thus:

$\textbf{n=2:}$ A sum of $2$ can be obtained only if $a=b=c=d=1.$ Thus $1$ case.

$\textbf{n=3:}$ A sum of $3$ can be obtained as $3=1+2$ thus $\frac{4!}{2!\cdot 2!}=6$ cases.

$\textbf{n=4:}$ A sum of $4$ can be obtained as $4=1+3=2+2,$ which produces the three possibilities of

$(2,2,2,2)$ which produces $1$ case.

$(1,1,3,3)$ which produces $\frac{4!}{2!\cdot 2!}=6$ cases.

$(1,2,2,3)$ which produces $\frac{4!}{2!}=12$ cases.

Thus $1+6+12=19$ cases.

$\textbf{n=5:}$ A sum of $5$ can be obtained as $5=1+4=2+3,$ which produces the three possibilities of

$(2,2,3,3)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

$(1,1,4,4)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

$(1,2,3,4)$ which produces $4!=24$ cases.

Thus $6+6+24=36$ cases.

$\textbf{n=6:}$ A sum of $6$ can be obtained as $6=1+5=2+4=3+3,$ which produces the six possibilities of

$(3,3,3,3)$ which produces $1$ case.

$(1,3,3,5)$ which produces $\frac{4!}{2!}=12$ cases.

$(2,3,3,4)$ which produces $\frac{4!}{2!}=12$ cases.

$(1,1,5,5)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

$(1,2,4,5)$ which produces $4!=24$ cases.

$(2,2,4,4)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

Thus $1+6+12+12+6+24=61$ cases.

$\textbf{n=7:}$ A sum of $7$ can be obtained as $6=1+6=2+5=3+4,$ which produces the six possibilities of

$(1,1,6,6)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

$(1,2,5,6)$ which produces $4!=24$ cases.

$(1,3,4,6)$ which produces $4!=24$ cases.

$(2,2,5,5)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

$(2,3,4,5)$ which produces $4!=24$ cases.

$(4,4,5,5)$ which produces $\frac{4!}{2!\cdot2!}=6$ cases.

Thus, $6+24+24+6+24+6=90$ cases.

This means, we have $\textbf{Favorable} = 90 +2\left(1+6+19+36+61\right)=336.$

This means $\textbf{Probability}=\frac{\textbf{Favorable}}{\textbf{Total}}=\frac{336}{1296}=\boxed{\frac{7}{27}}.$

@@ Line 1: / Line 1: @@
 ==Problem ==
+Four fair six-sided dice are rolled. What is the probability that they can be divided into two pairs which sum to the same value? For example, a roll of <math>(1,4,6,3)</math> can be divided into <math>(1,6)</math> and <math>(4,3)</math>, each of which sum to <math>7</math>, but a roll of <math>(1,1,5,2)</math> cannot be divided into two pairs that sum to the same value.
-== Solution ==
+== Solution 1 ==
+We split this into cases based on the the form of the unordered values shown on the dice. In the following, <math>1 <= a,b,c,d <= 6</math> are distinct numbers. After determining the (unordered) numbers that can appear on the dice, we must determine how many ways we can order those dice rolls in sequence.
+Case1: The unordered numbers shown are {a,a,a,a} In this case, it is clear that the pairing (a,a) and (a,a) will yield equal sums, so we have 6 possible choices for a, and this is the number of possible rolls that take this form.
+Case2: The unordered numbers shown are {a,a,a,b} In this case, one of the pairs will contain b, hence the pairs will be (a,b) and (a,a). But these can never be equal as a 6= b.
+Case3: The unordered numbers shown are {a,a,b,b} To obtain equal sums, we must split the numbers into the pairs (a,b) and (a,b). There are <math>\binom{6}{2}= 15</math> ways to select a and b, and there are <math>\binom{4}{2}= 6</math> ways to order the rolls (select two of the rolls to be a’s). Hence there are 15·6 = 90 total rolls that take this form.
+Case4: The unordered numbers shown are {a,a,b,c} In this case, either b pairs with a or b pairs with c. If b pairs with a, then <math>a + b = c + a</math> , which is impossible as <math>b \ne c</math>. Therefore, b must pair with c, so <math>2a = b + c</math>. Therefore, b + c is even. We may assume without loss of generality that <math>b <= c</math>, hence the possibilities for (b,c) are (b,c) = (1,3),(1,5),(2,4),(2,6),(3,5),(4,6).
+Therefore, there are six ways to choose (b,c), and a is automatically determined (it is the average of b and c). Then there are 4! 2! = 12 ways to order the rolls, hence there are <math>6\cdot 12 = 72</math> total rolls that take this form.
+Case5: The unordered numbers shown are {a,b,c,d} In this case, the sum of the pairs must be representable in at two ways with distinct integers. We ﬁnd
+= 1 + 4 = 2 + 3;  6 = 1 + 5 = 2 + 4; 7 = 1 + 6 = 2 + 5 = 3 + 4; 8 = 2 + 6 = 3 + 5; 9 = 3 + 6 = 4 + 5.
+These are the only numbers that can be represented as the sum of two numbers in at least two ways using distinct numbers. In particular, for the numbers <math>5,6,8,9</math>,we know immediately what the four numbers a,b,c,d are. For 7,we must choose two of the three pairs, and we can do this in three ways. Therefore, the number of ways to choose {a,b,c,d} is <math>1+1+1+1+3 = 7</math>. Then we can order the rolls in 4! = 24 ways. Thus there are <math>7\cdot 24 = 168</math> total rolls that take this form. Adding these together, we ﬁnd <math>6 + 90 + 72 + 168 = 336</math> possibilities, so the answer is <math>\frac{336}{64} = \frac{7}{27}</math>.
+== Solution 2 ==
+We observe
+<cmath>\textbf{Probability}=\frac{\textbf{Favorable}}{\textbf{Total}}.</cmath>
+We have <math>\textbf{Total}=6^4=1296.</math>
+We now work on the favorable cases.
+Suppose the four numbers, <math>a,b,c,</math> and <math>d</math> can be split as
+<cmath>N=a+b=c+d.</cmath>
+We do casework on the value of <math>N.</math> Notice that a sum of <math>n</math> can be obtained in the same number of ways as a sum of <math>14-n</math> can be obtained. Thus:
+<math>\textbf{n=2:}</math> A sum of <math>2</math> can be obtained only if <math>a=b=c=d=1.</math> Thus <math>1</math> case.
+<math>\textbf{n=3:}</math> A sum of <math>3</math> can be obtained as <math>3=1+2</math> thus <math>\frac{4!}{2!\cdot 2!}=6</math> cases.
+<math>\textbf{n=4:}</math> A sum of <math>4</math> can be obtained as <math>4=1+3=2+2,</math> which produces the three possibilities of
+<math>(2,2,2,2)</math> which produces <math>1</math> case.
+<math>(1,1,3,3)</math> which produces <math>\frac{4!}{2!\cdot 2!}=6</math> cases.
+<math>(1,2,2,3)</math> which produces <math>\frac{4!}{2!}=12</math> cases.
+Thus <math>1+6+12=19</math> cases.
+<math>\textbf{n=5:}</math> A sum of <math>5</math> can be obtained as <math>5=1+4=2+3,</math> which produces the three possibilities of
+<math>(2,2,3,3)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+<math>(1,1,4,4)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+<math>(1,2,3,4)</math> which produces <math>4!=24</math> cases.
+Thus <math>6+6+24=36</math> cases.
+<math>\textbf{n=6:}</math> A sum of <math>6</math> can be obtained as <math>6=1+5=2+4=3+3,</math> which produces the six possibilities of
+<math>(3,3,3,3)</math> which produces <math>1</math> case.
+<math>(1,3,3,5)</math> which produces <math>\frac{4!}{2!}=12</math> cases.
+<math>(2,3,3,4)</math> which produces <math>\frac{4!}{2!}=12</math> cases.
+<math>(1,1,5,5)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+<math>(1,2,4,5)</math> which produces <math>4!=24</math> cases.
+<math>(2,2,4,4)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+Thus <math>1+6+12+12+6+24=61</math> cases.
+<math>\textbf{n=7:}</math> A sum of <math>7</math> can be obtained as <math>6=1+6=2+5=3+4,</math> which produces the six possibilities of
+<math>(1,1,6,6)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+<math>(1,2,5,6)</math> which produces <math>4!=24</math> cases.
+<math>(1,3,4,6)</math> which produces <math>4!=24</math> cases.
+<math>(2,2,5,5)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+<math>(2,3,4,5)</math> which produces <math>4!=24</math> cases.
+<math>(4,4,5,5)</math> which produces <math>\frac{4!}{2!\cdot2!}=6</math> cases.
+Thus, <math>6+24+24+6+24+6=90</math> cases.
+This means, we have
+<cmath>\textbf{Favorable} = 90 +2\left(1+6+19+36+61\right)=336.</cmath>
+This means
+<cmath>\textbf{Probability}=\frac{\textbf{Favorable}}{\textbf{Total}}=\frac{336}{1296}=\boxed{\frac{7}{27}}.</cmath>
 == See Also ==
 {{UMO box|year=2016|num-b=1|num-a=3}}
-[[Category:]]
+[[Category: Intermediate Combinatorics Problems]]

2016 UMO (Problems • Answer Key • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All UMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2016 UMO Problems/Problem 2"

Latest revision as of 13:53, 7 December 2021

Contents

Problem

Solution 1

Solution 2

See Also