Maths Olympiad Prep

Library / /36 of 43

Combinatorics Difficulty 6.0 National Olympiad Find the answer Italy

Problem:

A gang of thieves wants to open a bank's safe. An insider got the bank manager drunk and managed to find out that:

a. the combination is formed by 5 digits from 0 to 9;

b. the combination is an even number;

c. exactly one of the 5 digits of the combination is odd;

d. four different digits appear in the combination, the repeated digit is even and appears in two non-consecutive positions.

How many possible combinations are there based on this information?

Pick one

Solutions — 2

Solution 1

Solution:

The answer is (B). From the fact that the number is even it follows that the last digit must be even. It is convenient to distinguish according to whether this is the doubled one or not.

In the first case the other doubled digit can occupy 3 different positions (not the 4th) and for each of these the odd digit can occupy any one of the remaining 3 positions.

In the second case the two equal digits can be arranged in 3 different ways (1 and 3, 1 and 4, 2 and 4) and for each of these the odd digit can occupy 2 positions out of the 3 free ones (not the 5th).

In total there are 33+32=153 \cdot 3 + 3 \cdot 2 = 15 ways to fix the positions of the two equal digits and of the odd digit. For each of these ways one can freely choose the odd digit (5 ways), the doubled even digit (5 ways), the first and the second of the single even digits (4 and 3 ways respectively), for a total of 155543=450015 \cdot 5 \cdot 5 \cdot 4 \cdot 3 = 4500 different combinations that satisfy the requirements.

Solution 2

Solution:

The number of ways to arrange 2 objects in nn spaces so that they are not consecutive is (n12)\binom{n-1}{2}. One can indeed think of arranging them without restrictions on n1n-1 spaces and then inserting a new empty space between them.

If we set aside for the moment the information (a), the valid ways to fix the positions of the two equal digits and of the odd digit are then (512)3=18\binom{5-1}{2} \cdot 3 = 18. Of these, the ones that do not satisfy the information (a) are (411)1=3\binom{4-1}{1} \cdot 1 = 3 (the odd digit is fixed in the last position and the doubled one has the 4 remaining spots available). In total there are then 183=1518 - 3 = 15 ways to fix the positions that satisfy all the information. To conclude, one multiplies by 55435 \cdot 5 \cdot 4 \cdot 3 as before.

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 translated into English from it; metadata (topic, difficulty) added by this project.