Back to Mathematical Olympiad
Difficulty: 4/102021 IOQM 2021 (Q7)

Find the number of maps such that whenever .

Guide / Hint

Hint 1: Identify that the condition defines a non-decreasing sequence of length 3 chosen from 5 elements.

Hint 2: Formulate this as a combinations with repetition problem: choosing 3 elements from 5 with replacement.

Hint 3: Apply the formula with and .

Solution

We are asked to find the number of non-decreasing maps , i.e., maps such that .

This is equivalent to choosing elements from the set with repetition allowed, and then arranging them in non-decreasing order (which can be done in exactly one way).

Using the combination with repetition formula (Stars and Bars):

where (size of the codomain) and (size of the domain).

Therefore, the number of such maps is .

Ready to track your progress and master these topics?

Create a free account
    2021 IOQM 2021 Q7 - Olympiad Math Olympiad Question | Leminno