The answer is $k=21$. If $k\leq20$, assume those colors are $C_1, C_2, ...., C_k$ Because there is no color that is used in all paintings, there exist paintings $P_1, P_2,....,P_k$ such that $P_i$ doesn't contains the color $C_i$ $(1\leq{i}\leq{k})$ Consider the paintings $P_1, P_2,....,P_k$ and any other $20-k$ paintings, they surely don't have a common color. Contradiction! Following is the construction of $k=21$ : $P_i$ contains all colors except $C_i$ $(1\leq{i}\leq21)$ And the rest of the paintings contains all of the colors.

Lemma: for $n\leq 20$ each group of $n$ paintings have at least $21-n$ common colors. Proof: from the statement, for $n=20$ lemma is true. Now let's prove lemma with reduction from $n+1$ to $n$. We know, that each group of $n+1$ paintings have at least $21-(n+1)$ common colors. Then each group of $n$ have at least $21-(n+1)$ common colors, too. Assume, that there are $n$ paintings with exactly $21-(n+1)$ common colors. Obviously, for each of these $21-(n+1)$ colors, in the remaining $100-n$ paintings there is a painting, that doesn't have this color. Now, if we look at $20$ paintings ($n$, that we had at the beginning and $21-(n+1)=20-n$ - one for every of $21-(n+1)$ color) they don't have common colors. Contradiction, so each $n$ paintings have at least $21-(n+1)+1=21-n$ common colors, and lemma is proven. Therefore, each painting has at least $21-1=20$ colors. Construction for $k=20$: Break $100$ paintings into $21$ groups ($G_1$, ..., $G_21$: $16$ groups of $5$ paintings and $5$ groups of $4$ paintings). We have 21 colors ($C_1$, ..., $C_21$). Let all paintings in $G_i$ contain all colors except $C_i$. It is easy to see, that this construction satisfies all conditions. Answer: $k=20$

Same problem discussed here

What is the correct answer?

The answer is k=20

Attachments:

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.

Let's first rephrase the problem: Rephrased Problem wrote: Let $P_1 , P_2 , \dots ,P_{100}$ be $100$ sets such that $|P_i| = k$ for all $i = 1,2, \dots 100$ and the intersection of any $20$ of them is nonempty. If, $|\bigcap\limits_{i=1}^{100} P_i| =0$ then find the minimum value of $k$. Claim: For every $1 \leq j \leq 20$, there are at least $21 - j$ elements in the intersection of any $j$ of the $P_i$'s. Proof: For $j = 20$, this is obvious by the hypothesis. Let's assume this holds for some $2 \leq j \leq 20$, we will prove it for $j-1$. Assume for contradiction that there are some $P_{i_1} , P_{i_2} , \dots ,P_{i_{j-1}}$ such that the intersection of them contains at most $21 - j$ elements. Call $S = \{P_{i_1} , P_{i_2} , \dots ,P_{i_{j-1}}\}$. Then, by the induction hypothesis, for any $P_i \not \in S$, $P_i$ must contain all the elements in $T = \bigcap\limits_{m=1}^{j-1} P_{i_m}$. But, this means if we take some $x \in T$, then $x$ is contained in all sets, contradiction. Thus our induction is complete. By the claim, we have $|P_i| = k \geq 20$ for all $i = 1,2, \dots ,100$. We will prove that $k = 20$ indeed works. Let $X = \{a_1 , a_2 , \dots , a_{21}\}$ be our color set and for each $1\leq i \leq 20$, let $P_i = X - \{a_i\}$ and $P_i = \{a_1 , a_2 , \dots , a_{20}\}$ for all $21 \leq i \leq 100$. It is easy to see that all of our claims and the hypothesis in the problem are satisfied, thus we are done.