Maths Olympiad Prep

Library / /8 of 10

Combinatorics Difficulty 6.4 National Olympiad Prove it Philippines

Problem:

In how many ways can Alex, Billy, and Charles split 77 identical marbles among themselves so that no two have the same number of marbles? It is possible for someone not to get any marbles.

Solution

Solution:

Let the numbers of marbles that Alex, Billy, and Charles get be aa, bb, and cc, respectively, with aa, bb, c0c \geq 0 and a+b+c=7a + b + c = 7. We require that aa, bb, and cc are all distinct (no two are equal).

Since the marbles are identical and the people are distinguishable, we are counting ordered triples (a,b,c)(a, b, c) of non-negative integers, all distinct, with sum 77.

First, list all possible unordered triples of distinct non-negative integers that sum to 77.

Let a<b<ca < b < c (since the variables are symmetric, we can count the number of such ordered triples for each unordered triple by multiplying by 66 for all permutations).

Let us find all sets {a,b,c}\{a, b, c\} with a<b<ca < b < c, a,b,c0a, b, c \geq 0, a+b+c=7a + b + c = 7.

Try a=0a = 0:

Then b<cb < c, b1b \geq 1, cb+1c \geq b + 1.

0+b+c=7    b+c=70 + b + c = 7 \implies b + c = 7

So bb can be 1,2,31, 2, 3:

- b=1b = 1, c=6c = 6
- b=2b = 2, c=5c = 5
- b=3b = 3, c=4c = 4

So possible triples: (0,1,6)(0, 1, 6), (0,2,5)(0, 2, 5), (0,3,4)(0, 3, 4)

Try a=1a = 1:

Then b<cb < c, b2b \geq 2, cb+1c \geq b + 1.

1+b+c=7    b+c=61 + b + c = 7 \implies b + c = 6

So b=2,3b = 2, 3:

- b=2b = 2, c=4c = 4
- b=3b = 3, c=3c = 3 (but b=cb = c not allowed)

So only (1,2,4)(1, 2, 4)

Try a=2a = 2:

Then b+c=5b + c = 5, b3b \geq 3, cb+1c \geq b + 1

- b=3b = 3, c=2c = 2 (not possible, c>bc > b)
- b=4b = 4, c=1c = 1 (not possible, c>bc > b)

So no solutions.

Try a=3a = 3:

Then b+c=4b + c = 4, b4b \geq 4, cb+1c \geq b + 1

But b=4b = 4, c=0c = 0 (not possible, c>bc > b)

So no solutions.

Thus, the possible unordered triples are:

(0,1,6)(0, 1, 6)
(0,2,5)(0, 2, 5)
(0,3,4)(0, 3, 4)
(1,2,4)(1, 2, 4)

Each unordered triple corresponds to 3!=63! = 6 ordered triples (since all numbers are distinct).

So total number of ways is 4×6=244 \times 6 = 24.

Answer: 24\boxed{24}

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.