$100$ pictures of BdMO math campers were painted by Benjamin . Exactly $k$ colors were used in each picture. There is a common color in every $20$ pictures. But, there is no common color in all $100$ pictures. Find the smallest possible value of $k$.
I reading solution this problem but i don’t understand Solution:
The problem is equivalent to: There is a "universal" set $C$ of size $c$. A painter chooses $100$ sets $K_i$, each of size $c-k$, so that every element of $C$ is in at least one $K_i$, and no $20$ distinct $K_i$ can be chosen to have $C$ as their union. We wish to minimize $k$. The construction is fairly simple: make the universal set have size $21$, initially make every $K_i$ a copy of $C$, and then remove $1$ element from each $K_i$ so that every element of $C$ is removed from at least one set. This gives us $\boxed{k=20}$. Now suppose that there is a solution with $k\leq19$. In particular, we can choose some random $K_i$ to get $c-k$ elements of $C$. The other $k$ elements can then just be chosen by choosing some appropriate $K_i$ one-by-one so that the ultimate union is $C$. This gives the desired contradiction, since this process uses at most $1+k\leq 20$ sets. Someone can explan or other solution
There are two stages. First is to prove you can do it with $21$.
Each painting has $20$ of the available $21$ colors. If you choose $20$ paintings, there are at most $20$ colors missing, so there is at least one color common to all the paintings. This is the pigeonhole principle.
Next is to prove you can't do it with $20$.
If there were only $20$ colors, we could pick $20$ paintings without a common color. There must be at least one painting missing each color so there is not a common color for the $100$. Just go through the colors and pick a painting missing it. There is no problem if you pick the same painting twice because it is missing two colors. If your set is less than $20$, pick some more paintings at random and you will have $20$ paintings with no common color.