Maths Olympiad Prep

Library / /12 of 13

Combinatorics Difficulty 6.7 National olympiad Prove it Bulgaria

Given a natural number nn. We have n+1n + 1 balls numbered 11, 11, 22, 33, ..., nn (only the first two are the same). We need to color these balls in nn given colors so that every ball is a single color and every color is used at least once. We denote by ana_n the number of possible colorings. Find the smallest nn for which ana_n is divisible by 20242024.
(Ivaylo Kortezov)

Solutions — 2

Solution 1

Exactly one of the colors will be used for two of the balls; let their numbers be aa and bb, such that aba \le b.

If a>1a > 1, then we have (n1)(n2)/2(n-1)(n-2)/2 choices for aa and bb, and nn choices for their color. The remaining n1n-1 balls (two of which are the same) must be colored in the remaining n1n-1 colors; for this we have (n1)!/2(n-1)!/2 variants. Therefore, in this case the number of possible colorings is 14(n1)!.n(n1)(n2)=14n!(n23n+2)\frac{1}{4}(n-1)!.n(n-1)(n-2) = \frac{1}{4}n!(n^2-3n+2).

If a=1a = 1, then there are n!n! options for coloring all balls except aa in nn colors. Now there are nn choices for the color of aa. Thus, in this case there are n!.nn!.n possible colorings.

Finally an=14n!(n23n+2+4n)=14n!(n2+n+2)a_n = \frac{1}{4}n!(n^2 - 3n + 2 + 4n) = \frac{1}{4}n!(n^2 + n + 2).

If ana_n is a multiple of 2024=2311232024 = 2^3 \cdot 11 \cdot 23 and n<23n < 23, it must be 23n2+n+223|n^2 + n + 2. Direct inspection shows that the smallest such nn is 99, but a9=9!.23a_9 = 9!.23 is not divisible by 1111, and the next suitable nn is 1313, where a13=13!.46a_{13} = 13!.46 is divisible by 2311232^3 \cdot 11 \cdot 23. \square

Solution 2

If a>1a > 1, then we have (n1)(n2)/2(n-1)(n-2)/2 choices for aa and bb, and nn choices for their color. The remaining n1n-1 balls (two of which are the same) must be colored in the remaining n1n-1 colors; for this we have (n1)!/2(n-1)!/2 variants. Therefore, in this case the number of possible colorings is 14n!(n1)!n(n1)(n2)=14n!(n23n+2)\frac{1}{4}n!(n-1)!n(n-1)(n-2) = \frac{1}{4}n!(n^2-3n+2).
If a=1a = 1, then there are n!n! options for coloring all balls except aa in nn colors. Now there are nn choices for the color of aa. Thus, in this case there are n!nn! \cdot n possible colorings.
Finally an=14n!(n23n+2+4n)=14n!(n2+n+2)a_n = \frac{1}{4}n!(n^2 - 3n + 2 + 4n) = \frac{1}{4}n!(n^2 + n + 2). If ana_n is a multiple of 2024=2311232024 = 2^3 \cdot 11 \cdot 23 and n<23n < 23, it must be 23n2+n+223|n^2 + n + 2. Direct inspection shows that the smallest such nn is 99, but a9=9!23a_9 = 9! \cdot 23 is not divisible by 1111, and the next suitable nn is 1313, where a13=13!46a_{13} = 13! \cdot 46 is divisible by 2311232^3 \cdot 11 \cdot 23. \square

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 and solution reproduced as published; topic and difficulty added by this site.