BdMO 2017 National Round Secondary 7
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]
[100% sure]
-
- Posts:17
- Joined:Thu Feb 01, 2018 11:28 am
- Location:Sylhet
Re: BdMO 2017 National Round Secondary 7
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.
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO 2017 National Round Secondary 7
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$ !prottoy das wrote: ↑Tue Feb 19, 2019 10:29 pmThe 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!!!
-
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO 2017 National Round Secondary 7
What is the correct answer ?
$20$ or $21$?
$20$ or $21$?
-
- Posts:194
- Joined:Sat Jan 02, 2021 9:28 pm
Re: BdMO 2017 National Round Secondary 7
20(maybe)
Induction may help.(Try inducting on the multiples of 5)
Induction may help.(Try inducting on the multiples of 5)
Re: BdMO 2017 National Round Secondary 7
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.
$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.
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: BdMO 2017 National Round Secondary 7
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
— John von Neumann
Re: BdMO 2017 National Round Secondary 7
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.Anindya Biswas wrote: ↑Tue Aug 03, 2021 12:47 amShouldn'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)$.