Question 21

For $$n\in\mathbb{N}$$, consider non-negative integer-valued functions $$f$$ on $$\{1,2,..., n\}$$ satisfying $$f(i)\ge f(j)$$ for $$i>j$$ and $$\sum_{i=1}^{n}(i+f(i))=2023$$. Choose $$n$$ such that $$\sum_{i=1}^{n}f(i)$$ is the least. How many such functions exist in that case?


Correct Answer: 15

Let $$n\in\mathbb{N}$$ and let the required function be $$f:\{1,2,\dots ,n\}\rightarrow\mathbb{Z}_{\ge 0}$$ with $$f(1)\le f(2)\le\cdots\le f(n)$$.

The condition on the sum gives
$$\sum_{i=1}^{n}\bigl(i+f(i)\bigr)=\frac{n(n+1)}{2}+\sum_{i=1}^{n}f(i)=2023.$$ Hence
$$\sum_{i=1}^{n}f(i)=2023-\frac{n(n+1)}{2}\;.\quad -(1)$$

Because every $$f(i)$$ is non-negative, the right-hand side of $$(1)$$ must be $$\ge 0$$, so $$\dfrac{n(n+1)}{2}\le 2023$$. To minimise $$\sum f(i)$$ we must maximise $$\dfrac{n(n+1)}{2}$$ subject to this inequality.

Compute the largest such $$n$$:
$$n(n+1)\le 4046.$$ Checking successive integers, $$63\cdot 64=4032\le 4046,\qquad 64\cdot 65=4160\gt 4046.$$ Therefore $$n_{\text{max}}=63.$

With $$n=63$$, equation $$(1)$$ gives
$$$$\sum_{i=1}^{63}f(i$$)=2023-$$\frac{63\cdot 64}{2}$$=2023-2016=7.$$ Thus the least possible value of $$$$\sum$$ f(i)$$ is $$7$$ and it is achieved when $$n=63$$.

We now have to count the non-decreasing sequences $$0\le f(1)\le f(2)\le$$\cdot$$s\le f(63),\qquad$$\sum_{i=1}^{63}f(i$$)=7.$$

Such a sequence is obtained by writing the integer $$7$$ as an unordered sum of non-negative integers (a partition) and then appending enough zeros to reach length $$63$$. Hence the number of admissible sequences equals the number of partitions of $$7$$ into any number of parts (at most $$63$$, but $$63\gt 7$$ so this restriction is irrelevant).

The partitions of $$7$$ are:
$$7;\;6+1;\;5+2;\;5+1+1;\;4+3;\;4+2+1;\;4+1+1+1;\;3+3+1;\;3+2+2;\; 3+2+1+1;\;3+1+1+1+1;\;2+2+2+1;\;2+2+1+1+1;\;2+1+1+1+1+1;\; 1+1+1+1+1+1+1.$$ There are $$15$$ of them.

Therefore exactly $$15$$ functions satisfy all the conditions.

Answer: $$\boxed{15}$$

Get AI Help

Book Free CAT Mentorship

Get personalized CAT strategy from a 99%iler

500+ students mentored
CAT mentor
banner

banner

50,000+ JEE Students Trusted Our Score Calculator

Predict your JEE Main percentile, rank & performance in seconds

Ask AI