There are three horses: Uri, Uli and Buki. Results that can be possible in the race are 13.

  • Uri first, Uli second, Buki third.
  • Buki first, Uri second, Uli third.
  • Buki first, Uri and Uli second together.
  • Uri and Buki first, Uli second.
  • Uri, Buki and Uli first all together.

There are eight more possible results but didn't write them all because I guess you understand what I mean. Given that information, they ask to calculate how many different possible results can be with 5 horses.

I can calculate how many results can be if all the horses come at different times:

$120 = 5\cdot4\cdot3\cdot2\cdot1$

How do I do it with the other cases? Please don't use complicated math, famous formulas or theoremas, I'm supposed to calculate this just with logic.

  • $\begingroup$ For the cases of 3 horses we calculate the probabilities for the following cases and add them up: 3_0_0 : implying that all 3 horses come first, 0 come second and 0 come third Similarly, we have: 2_1_0, 1_2_0, 1_1_1 If we calculate the probabilities for each case and add them up, it sums to 13. We follow the same procedure for 5 horses. There will be of course many more cases: 5_0_0, 4_1_0, 3_2_0, 3_1_1, 2_3_0, 2_2_1, 2_1_2, 1_4_0, 1_3_1, 1_2_2, 1_1_3 $\endgroup$ Nov 21 '15 at 20:58
  • $\begingroup$ @AmitSaxena Yes, I know that. I'm trying to know how's the fastest way to resolve it. $\endgroup$ Nov 21 '15 at 21:05
  • $\begingroup$ There is no faster way that I can think of. I forgot to add cases where 4 and 5 places will be filled: 2_1_1_1, 1_2_1_1, 1_1_2_1, ,1_1_1_2, 1_1_1_1_1 $\endgroup$ Nov 22 '15 at 11:11
  • $\begingroup$ Its rather easy e.g. the number of ways for 1_1_1_2 will be 5*4*3 = 60 $\endgroup$ Nov 22 '15 at 11:12
  • $\begingroup$ Once you have solved 1_1_1_2 you don't have to solve for 2_1_1_1, 1_1_2_1 and 1_2_1_1 as they will also have 60 ways to happen. $\endgroup$ Nov 22 '15 at 11:20

If we are to use little machinery, we can divide into cases, count the number of ways for each, and then add up.

Roughly, the cases can be described as follows: $5$; $4$-$1$; $3$-$2$; $3$-$1$-$1$; $2$-$2$-$1$; $2$-$1$-$1$-$1$; $1$-$1$-$1$-$1$-$1$.

We count the number of possibilities for each.

$5$: This the the five-way tie. There is $1$ way this can happen.

$4$-$1$: Either $4$ tied first, and a loser, or $1$ winner, and $4$ tied for last, or to put it more nicely, for second. The horse by itself can be chosen in $5$ ways. It can be tied for first or tied for last, for a total of $(2)(5)$ possibilities.

$3$-$2$: Again we have $2$ possibilities, a two-way tie for first or for last. The group of $2$ can be chosen in $\binom{5}{2}=10$ ways, giving a total of $(2)(10)$.

$3$-$1$-$1$: The group of $3$ can be chosen in $\binom{5}{3}=10$ ways. It can be in any of $3$ places. The leftmost empty place can then be filled in $2$ ways, for a total of $(2)(3)(10)$.

$2$-$2$-$1$: The lone horse can be chosen in $5$ ways, and can be in any of $3$ positions. We can fill the leftmost remaining position in $\binom{4}{2}=6$ ways, for a total of $(6)(3)(5)$.

Only two to go, one of which you have done!

Remark: For a lot more information, please see the Online Encyclopedia of Integer Sequences.

  • $\begingroup$ What do you mean by $\bigl( \begin{smallmatrix} 5 \\ 3 \end{smallmatrix} \bigr)$ and $\bigl( \begin{smallmatrix} 4 \\ 2 \end{smallmatrix} \bigr)$? What do this symbolize? $\endgroup$ Nov 21 '15 at 21:19
  • $\begingroup$ The notation $\binom{n}{k}$ is the number of ways a subset of $k$ elements can be selected from a set of $n$ elements. $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ so $$\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1 \cdot 2 \cdot 1} = 10$$ $\endgroup$ Nov 21 '15 at 21:20
  • 1
    $\begingroup$ The binomial coefficient $\binom{n}{k}$ may be familiar to you under other symbols, such as ${}_nC_k$ or $C(n,k)$ or $C_k^n$. It is the number of ways to choose $k$ objects from a collection of $n$ objects. $\endgroup$ Nov 21 '15 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.