BdMO National Primary 2020 P3

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
Location:Dhaka, Bangladesh.
BdMO National Primary 2020 P3

Unread post by Mursalin » Mon Feb 08, 2021 5:55 pm

সৌমিত্র \(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.

User avatar
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO National Primary 2020 P3

Unread post by Anindya Biswas » Mon Mar 22, 2021 9:25 pm

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

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

Re: BdMO National Primary 2020 P3

Unread post by eletro madness » Tue Apr 06, 2021 10:26 am

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

User avatar
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO National Primary 2020 P3

Unread post by Anindya Biswas » Tue Apr 06, 2021 10:08 pm

eletro madness wrote:
Tue Apr 06, 2021 10:26 am
Why will $1,2,3,... ,k$ be the worst scenario?
Cause any other sequence would have greater maximum sum of $4$ elements.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply