Answer: 2 We first show that Lesha can always leave 2 columns. Select two arbitrary column. For each row, name a color which doesn't appear in the two cells in selected column of the row(there are at most 2 colors and Lesha can name the other). Then, the selected two column leave after deletion. Next, Kostya can paint the table in such a way that Lesha cannot leave more than 2 columns. For each rows we label two element subset $\{i, j\}$ of $\{1,2,\ldots,25\}$ . There are exactly $\binom{25}2 = 300$ subsets. Let the colors be $A,B,C$. For each row labeled $\{i,j\}$, we color $i$-th cell $A$, $j$-th cell $B$ and other cells $C$. Then, we show that Lesha cannot leave more than 2 columns. If Lesha name color $C$, for some row, only 2 columns left. Thus, Lesha must name $A$ or $B$ to each row. We assume three columns which is $i,j,k$-th column left. Consider the row with label $\{i,j\}$, the $i,j,k$-th cell in the row has three different colors. Thus, Lesha must mark at least one of these cells, a contradiction.