Maths Olympiad Prep

Library / /72 of 72

Combinatorics Difficulty 8.1 Shortlist Prove it Vietnam

There are 4 identical fair dices. Denote xix_i (1xi61 \leq x_i \leq 6) be the number of dots on a face appearing on the ii-th dice 1i41 \leq i \leq 4.
a) Find the number of possible tuples (x1,x2,x3,x4)(x_1, x_2, x_3, x_4).
b) Find the probability that there exists a number xjx_j such that xjx_j is equal to the sum of the remaining numbers.
c) Find the probability that we can divide x1,x2,x3,x4x_1, x_2, x_3, x_4 into 2 groups that have the same sum.

Solution

a) Using the principle of multiplication, the answer is 64=12966^4 = 1296.

b) Firstly, there are 4 ways to choose ii such that xix_i is equal to the sum of the remaining numbers. For each ii, we choose xix_i first and using the star-bar problem, one can obtain (xi12)\binom{x_i-1}{2} ways to choose the other 3 numbers. For xi=3,4,5,6x_i = 3, 4, 5, 6; we find that there are
(22)+(32)+(42)+(52)=1+3+6+10=20 \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} = 1 + 3 + 6 + 10 = 20
tuples (x1,x2,x3,x4)(x_1, x_2, x_3, x_4) such that xix_i is equal to the sum of the remaining numbers. Thus, there are 4×20=804 \times 20 = 80 tuples satisfying the condition and the probability is 801296=581\frac{80}{1296} = \frac{5}{81}.

c) Denote S1,S2,S3S_1, S_2, S_3 to be the sets of tuples that satisfy
x1+x2=x3+x4,x1+x3=x2+x4,x1+x4=x2+x3. x_1 + x_2 = x_3 + x_4, \quad x_1 + x_3 = x_2 + x_4, \quad x_1 + x_4 = x_2 + x_3.
We consider the case x1+x2=x3+x4x_1 + x_2 = x_3 + x_4, which is equivalent to
(x11)+(x21)+(6x3)+(6x4)=10. (x_1 - 1) + (x_2 - 1) + (6 - x_3) + (6 - x_4) = 10.
Let y1=x11y_1 = x_1 - 1, y2=x21y_2 = x_2 - 1, y3=6x3y_3 = 6 - x_3, y4=6x4y_4 = 6 - x_4 then
{0y1,y2,y3,y45,y1+y2+y3+y4=10.(1) \begin{cases} 0 \le y_1, y_2, y_3, y_4 \le 5, \\ y_1 + y_2 + y_3 + y_4 = 10. \end{cases} \quad (1)
Denote AA to be the set of tuples (y1,y2,y3,y4)(y_1, y_2, y_3, y_4) such that
{y1,y2,y3,y40,y1+y2+y3+y4=10.(2) \begin{cases} y_1, y_2, y_3, y_4 \ge 0, \\ y_1 + y_2 + y_3 + y_4 = 10. \end{cases} \quad (2)
By using star-bar problem, we have
A=(1310)=286. |A| = \binom{13}{10} = 286.
Denote AiA_i to be the set of tuples (y1,y2,y3,y4)(y_1, y_2, y_3, y_4) that satisfy (2) and yi6y_i \ge 6. Assume that y16y_1 \ge 6 or
{y16,y2,y3,y40,(y16)+y2+y3+y4=6. \begin{cases} y_1 \ge 6, y_2, y_3, y_4 \ge 0, \\ (y_1 - 6) + y_2 + y_3 + y_4 = 6. \end{cases}
Using the star-bar problem, we obtain A1=(74)=35|A_1| = \binom{7}{4} = 35. Similarly, we get A2=A3=A4=35|A_2| = |A_3| = |A_4| = 35. It is also clear that A1,A2,A3,A4A_1, A_2, A_3, A_4 are disjoint. The number of tuples (y1,y2,y3,y4)(y_1, y_2, y_3, y_4) that satisfy (1) is
A(A1+A2+A3+A4)=146. |A| - (|A_1| + |A_2| + |A_3| + |A_4|) = 146.
Hence, the number of tuples (x1,x2,x3,x4)(x_1, x_2, x_3, x_4) that x1+x2=x3+x4x_1+x_2 = x_3+x_4 is 146 or S1=146|S_1| = 146.
Clearly, S1S2S_1 \cap S_2 is the set of tuples (x1,x2,x3,x4)(x_1, x_2, x_3, x_4) such that
{x1+x2=x3+x4,x1+x3=x2+x4,{x1=x4,x2=x3. \begin{cases} x_1 + x_2 = x_3 + x_4, \\ x_1 + x_3 = x_2 + x_4, \end{cases} \quad \longleftrightarrow \quad \begin{cases} x_1 = x_4, \\ x_2 = x_3. \end{cases}
Thus, there are 6 ways to choose x1x_1 and x4x_4, 6 ways to choose x2x_2 and x3x_3, which implies S1S2=62=36|S_1 \cap S_2| = 6^2 = 36. Similarly,
S2S3=S3S1=36. |S_2 \cap S_3| = |S_3 \cap S_1| = 36.
In case S1S2S3S_1 \cap S_2 \cap S_3, one can check that x1=x2=x3=x4x_1 = x_2 = x_3 = x_4. There are 6 ways to choose x1,x2,x3,x4x_1, x_2, x_3, x_4 which implies that S1S2S3=6|S_1 \cap S_2 \cap S_3| = 6. By applying the principle of inclusion and exclusion, we obtain
S=S1S2S3=(S1+S2+S3)(S1S2+S2S3+S3S1)+S1S2S3=1463363+6=336. \begin{aligned} |S| &= |S_1 \cup S_2 \cup S_3| \\ &= (|S_1| + |S_2| + |S_3|) - (|S_1 \cap S_2| + |S_2 \cap S_3| + |S_3 \cap S_1|) \\ &\quad + |S_1 \cap S_2 \cap S_3| = 146 \cdot 3 - 36 \cdot 3 + 6 = 336. \end{aligned}
Combining with part b), the number of tuples (x1,x2,x3,x4)(x_1, x_2, x_3, x_4) such that we can divide the numbers in two groups that have the same sum which is 336+80=416336 + 80 = 416 or the probability is 4161296=2681\frac{416}{1296} = \frac{26}{81}.
\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.