0
$\begingroup$

Here's a question from the AIME competition: https://artofproblemsolving.com/wiki/index.php/1998_AIME_Problems/Problem_4

Nine tiles are numbered $1, 2, 3, \cdots, 9,$ respectively. Each of three players randomly selects and keeps three of the tiles, and sums those three values. The probability that all three players obtain an odd sum is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

It's also been asked before on Math Stack Exchange before here: Probability question and how to approach it

Here's what I did. Let's say the order in which people take tiles does matter. Then my result is$${{3 \binom{5}{3} 2 \binom{4}{2}}\over{3! \binom{9}{3,3,3}}} = {1\over{28}}.$$However, the answer at the given link, where they don't take into consider order (saying it will be the same final answer) is:$${{3 \binom{5}{3} 2 \binom{4}{2}}\over{\binom{9}{3,3,3}}} = {3\over{14}}.$$So my question is, if we take into consideration the order in which people take tiles, then why do we need an extra $3!$ in the numerator (to cancel out the $3!$ in the denominator)? I thought the $3$ I had already took care of that, since only $1$ of the $3$ players will have $3$ odds, which "fixes" the configuration. So how am I mistaken, what am I missing?

$\endgroup$
1
  • 1
    $\begingroup$ It is not clear to me what the $3!$ represents in your denominator of $3! \binom{9}{3,3,3}$. The order $A$ then $B$ then $C$ is already in the $\binom{9}{3,3,3}$, though the order of the cards each takes is not; if you wanted that too then it would be $9! =(3!)^3 \binom{9}{3,3,3}$ and the numerator would have to increase too. $\endgroup$
    – Henry
    Apr 30, 2022 at 7:48

2 Answers 2

1
$\begingroup$

The trinomial coefficient (note the third $3$ is not typically written since it is understood that it must be $9-3-3 = 3$, in as much as $\binom{n}{k}$ is not written $\binom{n}{k,n-k}$) $$\binom{9}{3,3} = \frac{9!}{3!3!3!} = 1680$$ represents the number of ways for the three players to select $3$ distinct tiles without replacement, in which the order of the players matters but the order of the tiles selected by each player does not. So for instance, the selection $$(\{1,2,3\}, \{4,5,6\}, \{7,8,9\})$$ is equivalent to $$(\{3,2,1\}, \{6,5,4\}, \{9,8,7\})$$ but not equivalent to $$(\{7,8,9\}, \{4,5,6\}, \{1,2,3\}).$$

On the other hand, if the order of tiles taken by each player matters, but the order of the players does not, then the correct number of distinct outcomes is simply $9!/3! = 60480$, since there are $9!$ total permutations of the tiles, which are then partitioned in sequence among the $3$ players, and then for each such outcome, there are $3!$ orderings of the $3$ players assigned to the sequence.

Your denominator $3! \binom{9}{3,3} = 10080$ doesn't match either of these ways of counting.

If you want to count the outcomes in which neither ordering of tiles nor players matters, then clearly this is just $1680/3! = 280$. If you want to count outcomes in which the order of everything matters, it is just $9!$.

$\endgroup$
1
$\begingroup$

I think that the simplest way to conceive it is to frame the answer entirely in terms of the multinomial coefficient $\binom{n}{k_1, \;k_2,\; k_3\; ...}, \Sigma(k_i) = n,$

defined as the number of ways to put $n$ distinct objects into $k$ distinct boxes with $k_1$ in box $1$, $k_2$ in box $2$, etc, not $k_1$ in any box.

For this problem, the formulation for $3$ odd, $0$ even for person $A$ would be

$\dfrac{\dbinom{5}{3,1,1}\dbinom{4}{0,2,2}}{\dbinom{9}{3,3,3}}$

But the configuration $3$ odd, $0$ even could go to any of the three people, hence multiplication by $3$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .