BdMO National Primary 2020 P3

[Mursalin]

সৌমিত্র \(1\) থেকে \(4040\)-এর মধ্যে বিভিন্ন সংখ্যা নিচ্ছে। একটি সংখ্যা সে সর্বোচ্চ একবার নিতে পারবে! সৌমিত্র অন্তত কতগুলো সংখ্যা নিলে তুমি নিশ্চিত হতে পারবে, যে সেখানে চারটি সংখ্যা আছে যাদের যোগফল \(2020\) অপেক্ষা বেশি?


Soumitra is picking numbers between \(1\) and \(4040\), so that no number is picked more than once. How many numbers will Soumitra have to pick (at least) before you can guarantee that there are four of them with sum greater than \(2020\)?

[Anindya Biswas]

Let's assume $k$ is the largest integer for which we can choose $k$ integers and no $4$ of them has a sum greater than $2020$. Since we are trying the worst case scenario, choose the numbers $1,2,3,\dots,k$.
So, the maximum value of sum of $4$ numbers $k+(k-1)+(k-2)+(k-3)\leq2020$
$\Longleftrightarrow 4k-6\leq2020$
$\Longleftrightarrow k\leq506.5$
That means we have a set of positive integers of size $506$ for which we don't have $4$ elements whose sum is greater than $2020$.
Let's see if $507$ does the job. Let's choose randomly $a_1,a_2,\dots,a_{507}$. and arrange them in ascending order, that means,
$a_1<a_2<\dots<a_{507}$
$\Longleftrightarrow a_1\leq a_2-1\leq a_3-2 \leq\dots\leq a_{507}-506$
Let's choose the largest $4$ of them,
$a_{507}+a_{506}+a_{505}+a_{504}\geq a_1+506+a_1+505+a_1+504+a_1+503$
$\Longrightarrow a_{507}+a_{506}+a_{505}+a_{504}\geq 4a_1+2018\geq2022$
So, any random set of size $507$ works while $506$ doesn't. So our answer is $\boxed{507}$.

[eletro madness]

Why will $1,2,3,... ,k$ be the worst scenario?

[Anindya Biswas]

Why will $1,2,3,... ,k$ be the worst scenario?

Cause any other sequence would have greater maximum sum of $4$ elements.