BdMO Online Forum

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]

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!!!

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$ !

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

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

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.

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)$.

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.