BdMO National Primary 2020 P3

Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
BdMO National Primary 2020 P3
সৌমিত্র $$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$$?
This section is intentionally left blank.

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Contact:

Re: BdMO National Primary 2020 P3

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}$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Posts:1
Joined:Tue Apr 06, 2021 3:01 am

Re: BdMO National Primary 2020 P3

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

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Why will $1,2,3,... ,k$ be the worst scenario?
Cause any other sequence would have greater maximum sum of $4$ elements.