BdMO 2017 National Round Secondary 7

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Tasnood
Posts:73
Joined:Tue Jan 06, 2015 1:46 pm
Re: BdMO 2017 National Round Secondary 7

Unread post by Tasnood » Wed Mar 07, 2018 10:17 am

Told you before, if $20$ pictures can share more than two common color and not all of them share the same color, the answer is $2$.
[100% sure] :D

prottoy das
Posts:17
Joined:Thu Feb 01, 2018 11:28 am
Location:Sylhet

Re: BdMO 2017 National Round Secondary 7

Unread post by prottoy das » Tue Feb 19, 2019 10:29 pm

The problem is from Turkey Junior National math olympiad 2015,Q2!!! At least 3 of the problems of secondary category of nationa bdmo 2017 was stolen!!!
Last edited by prottoy das on Wed Feb 20, 2019 1:47 pm, edited 1 time in total.

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: BdMO 2017 National Round Secondary 7

Unread post by samiul_samin » Wed Feb 20, 2019 9:16 am

prottoy das wrote:
Tue Feb 19, 2019 10:29 pm
The problem is from Turkey Junior National math olympiad 2015,Q2!!! At least 3 of the roblems of secondary category of nationa bdmo 2017 was stolen!!!
Actually making this type of hard problems is too much tough and that's why problems are taken from those contests!It is happening from the very beginning of BdMO and you might get a common question @ National Olympiad $2019$ !

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: BdMO 2017 National Round Secondary 7

Unread post by samiul_samin » Fri Feb 22, 2019 7:09 pm

What is the correct answer ?
$20$ or $21$?

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BdMO 2017 National Round Secondary 7

Unread post by Asif Hossain » Sat Jan 02, 2021 9:40 pm

20(maybe)
Induction may help.(Try inducting on the multiples of 5)

User avatar
its.nabid
Posts:2
Joined:Wed Dec 30, 2020 3:16 pm
Contact:

Re: BdMO 2017 National Round Secondary 7

Unread post by its.nabid » Sun Aug 01, 2021 5:54 pm

We will rather prove this general statement,
$n$ is the lowest number of colors needed to color $m$ pictures in such a way that there is a common color in every $n$ pictures. But, there is no common color in all $m$ pictures.

The given conditions are,
$(i)$ There is a common color in any $n$ pictures.
$(ii)$ There is no common color in all $m$ pictures.

By $c_i$ we will denote $i$th color.

Base case: $\mathbf{n=2}$ Of course in this case, $2$ is the lowest because if it was $1$ then the $(ii)$ condition wouldn't have been fulfilled. And condition $(i)$ is also achievable by coloring the pictures by picking any element from this set, $\{c_1c_2,c_2c_3,c_3c_1\}$ and ensuring that every element is used at least once. So the Base case is true.
Let's assume that the conditions hold for $n=3,4,\cdots ,l-1$.

Now we will prove for $n=l$.
First we will show that the conditions are achievable when $n=l$.
Let $S$ be a set such that, $S=\{c_1\cdots c_{l}, c_2\cdots c_{l+1},\cdots ,c_{l+1}\cdots c_{l-1}\}$
Meaning the elements of $S$ is taken cyclically containing $l$ colors in each element. That's why every element has a missing $c_i$ so when any $l$ elements are chosen then there will be a total $l$, $c_i$s missing but because we have used $l+1$ colors there will be a single common color . But if you take all the $l+1$ elements there will be no common colors.
Now if we use every element of $S$ at least a single time to color all the $m$ pictures then our conditions will be fulfilled.

Now we will show that, $l$ is the lowest.
FSOC let us assume that $q$ is the lowest number of colors needed to color $m$ pictures in such a way that there is a common color in every $n$ pictures. But, there is no common color in all $m$ pictures where $q<l$.
Again from the inductive hypothesis we know that $P(q)$ is true.
So think of a set of $q$ pictures, they have a common color $c_j$. Now in the remaining set of pictures there must be at least one picture which doesn't contain $c_j$ unless the $(ii)$ won't hold. Now if we add that picture with the initial set we will get a set of $q+1$ pictures where there is no common color, that means we will surely get at least a set of $l$ pictures where there is no common color (just add any $l-q-1$ pictures to that set). Contradiction with the initial assumption! So $l$ is indeed the lowest.

Now if we just take, $n=20,m=100$ our problem will be solved.

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

Re: BdMO 2017 National Round Secondary 7

Unread post by Anindya Biswas » Tue Aug 03, 2021 12:47 am

its.nabid wrote:
Sun Aug 01, 2021 5:54 pm
We will rather prove this general statement,
$n$ is the lowest number of colors needed to color $m$ pictures in such a way that there is a common color in every $n$ pictures. But, there is no common color in all $m$ pictures.
Shouldn't we need at least $n+1$ colors? I've gone through your proof, now asking just to be sure. If $\{c_1,c_2,\dots,c_l\}$ are the colors, where $l\leq n$, then we can construct a set of at most $n$ pictures such that each picture has at least one color absent from it, contradicting your $(i)$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
its.nabid
Posts:2
Joined:Wed Dec 30, 2020 3:16 pm
Contact:

Re: BdMO 2017 National Round Secondary 7

Unread post by its.nabid » Tue Aug 03, 2021 12:21 pm

Anindya Biswas wrote:
Tue Aug 03, 2021 12:47 am
its.nabid wrote:
Sun Aug 01, 2021 5:54 pm
We will rather prove this general statement,
$n$ is the lowest number of colors needed to color $m$ pictures in such a way that there is a common color in every $n$ pictures. But, there is no common color in all $m$ pictures.
Shouldn't we need at least $n+1$ colors? I've gone through your proof, now asking just to be sure. If $\{c_1,c_2,\dots,c_l\}$ are the colors, where $l\leq n$, then we can construct a set of at most $n$ pictures such that each picture has at least one color absent from it, contradicting your $(i)$.
Yes we need a total of $n+1$ colors in the pallet but we will only take $n$ colors cyclically for each picture, that means there will one color missing in every picture thats why we if we take $n$ picture there will be total $n$ colors missing but remember we used $n+1$ colors? Thats why there will exist a single color which is available on all the $n$ pictures. Just think of this example for $n=2,m=3$ we color the first picture with Red and Green the second with Green and Blue and the third with Blue and Red. Now take any two there will be a common color but no common color in all of them and notice we used total three color R,G and B but we only used any two while coloring a single picture. I hope you understood.

Post Reply