Maths Olympiad Prep

Library / /125 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

For nNn \in \mathbb{N}, consider non-negative valued functions ff on {1,2,,n}\{1,2, \cdots , n\} satisfying f(i)f(j)f(i) \geqslant f(j) for i>ji>j and i=1n(i+f(i))=2023.\sum_{i=1}^{n} (i+ f(i))=2023. Choose nn such that i=1nf(i)\sum_{i=1}^{n} f(i) is at least. How many such functions exist in that case?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. We start with the given condition that for nN n \in \mathbb{N} , the function f f is non-negative and defined on the set {1,2,,n}\{1, 2, \ldots, n\} such that f(i)f(j) f(i) \geq f(j) for i>j i > j . Additionally, we have the equation:
i=1n(i+f(i))=2023 \sum_{i=1}^{n} (i + f(i)) = 2023

2. We can separate the sum into two parts:
i=1ni+i=1nf(i)=2023 \sum_{i=1}^{n} i + \sum_{i=1}^{n} f(i) = 2023

3. The first sum is the sum of the first n n natural numbers, which is given by:
i=1ni=n(n+1)2 \sum_{i=1}^{n} i = \frac{n(n+1)}{2}

4. Substituting this into the equation, we get:
n(n+1)2+i=1nf(i)=2023 \frac{n(n+1)}{2} + \sum_{i=1}^{n} f(i) = 2023

5. Solving for i=1nf(i)\sum_{i=1}^{n} f(i), we have:
i=1nf(i)=2023n(n+1)2 \sum_{i=1}^{n} f(i) = 2023 - \frac{n(n+1)}{2}

6. To minimize i=1nf(i)\sum_{i=1}^{n} f(i), we need to maximize n(n+1)2\frac{n(n+1)}{2} while ensuring that i=1nf(i)\sum_{i=1}^{n} f(i) remains non-negative. This means:
2023n(n+1)20 2023 - \frac{n(n+1)}{2} \geq 0

7. Solving the inequality:
2023n(n+1)2 2023 \geq \frac{n(n+1)}{2}
4046n(n+1) 4046 \geq n(n+1)

8. We need to find the largest integer n n such that n(n+1)4046 n(n+1) \leq 4046 . Testing values, we find:
n=63    63×64=4032(valid) n = 63 \implies 63 \times 64 = 4032 \quad (\text{valid})
n=64    64×65=4160(invalid) n = 64 \implies 64 \times 65 = 4160 \quad (\text{invalid})

Therefore, the maximum n n is 63.

9. Substituting n=63 n = 63 back into the equation for i=1nf(i)\sum_{i=1}^{n} f(i):
i=1nf(i)=202363×642=20232016=7 \sum_{i=1}^{n} f(i) = 2023 - \frac{63 \times 64}{2} = 2023 - 2016 = 7

10. We need to count the number of non-negative integer solutions to the equation:
i=163f(i)=7 \sum_{i=1}^{63} f(i) = 7
where f(i)f(j) f(i) \geq f(j) for i>j i > j . This is equivalent to finding the number of partitions of 7 into at most 63 parts, which is the same as the number of partitions of 7.

11. The number of partitions of 7 is given by:
p(7)=15 p(7) = 15

The final answer is 15\boxed{15}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.