Maths Olympiad Prep

Library / /149 of 156

Combinatorics Difficulty 6.8 National Olympiad Prove it China

There are 10 cards, each of which has two numbers, numbered 11, 22, 33, 44, 55, written on it, and the numbers on any two cards are not exactly identical. The 10 cards are placed in five boxes labelled 11, 22, 33, 44, 55, and a card with ii and jj written on it can only be placed in box ii or jj. One placement is called “good” if there are more cards in box 11 than in each of the other boxes. Then the total number of the “good” placements is ______.

Solution

Denote the card with i,ji, j written on it as {i,j}\{i, j\}. It is easy to know that these 10 cards are exactly {i,j}\{i, j\} (1i<j51 \le i < j \le 5).

Consider the “good” placements of the cards. There are 10 cards in the five boxes, so there are at least 3 cards in box 1. The only cards that will fit in box 1 are {1,2}\{1, 2\}, {1,3}\{1, 3\}, {1,4}\{1, 4\} and {1,5}\{1, 5\}.

Case 1: The 4 cards are all placed in box 1, and at this point it is no longer possible to have 4 cards in each of the remaining boxes. Therefore, no matter how the remaining 6 cards are placed, they will fit the requirements and there are 26=642^6 = 64 “good” placements.

Case 2: There are exactly 3 of the 4 cards in box 1 and the rest of each box contains at most 2 cards.

Consider the number NN of placements of {1,2}\{1, 2\}, {1,3}\{1, 3\}, {1,4}\{1, 4\} in box 1 and {1,5}\{1, 5\} in box 5.

There are 8 possible ways to place the cards {2,3}\{2, 3\}, {2,4}\{2, 4\}, {3,4}\{3, 4\}, with 6 of them being two cards placed in one of the boxes 2, 3, 4, and the remaining 2 being one card placed in each box of 2, 3, 4.

If there are two cards of {2,3}\{2, 3\}, {2,4}\{2, 4\} and {3,4}\{3, 4\} in a box, suppose that {2,3}\{2, 3\} and {2,4}\{2, 4\} are in box 2, and then {2,5}\{2, 5\} can only be in box 5. Therefore, box 5 already has {1,5}\{1, 5\} and {2,5}\{2, 5\}, so {3,5}\{3, 5\} and {4,5}\{4, 5\} are in boxes 3 and 4 respectively, namely, the placement of {2,5}\{2, 5\}, {3,5}\{3, 5\} and {4,5}\{4, 5\} is unique.

If one card of {2,3}\{2, 3\}, {2,4}\{2, 4\} and {3,4}\{3, 4\} is placed in each box of 2, 3, 4, then there are at most 2 cards in each box of 2, 3, 4. It is only necessary to make sure that there are no more than 2 cards in box 5, namely, there are 0 or 1 card of {2,5}\{2, 5\}, {3,5}\{3, 5\} and {4,5}\{4, 5\} in box 5, and the number of the corresponding placements is C30+C31=4C_3^0 + C_3^1 = 4.

As a result, N=6×1+2×4=14N = 6 \times 1 + 2 \times 4 = 14. By symmetry, there are 4N=564N = 56 “good” placements in case 2.

To sum up, there is a total of 64+56=12064 + 56 = 120 “good” placements.

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.