Question: There is an arbitrary (finite) amount of colors N, and M<2048 points, each colored by at least half of the colors. Does there exists 10 colors such that every point is colored by at least one of them?
This is true for N<20, and by dichotomy the statement would have been easy to prove to be true if it was 1023 points or less, so I think the answer is no but I would need to construct a countexample
Best Answer
There is indeed a counter-example. Let $\mathbb Z_2$ be the finite field of order $2$, the set $\{0,1\}$ with addition and multiplication modulo $2$.
Points: For each nonzero $v\in (\mathbb Z_2)^{11}$, there is a point $p_v$. There are $2^{11}-1$ points.
Colors: For each nonzero $w\in (\mathbb Z_2)^{11}$, there is a color $c_w$. There are $2^{11}-1$ colors.
We say that point $p_v$ has color $c_w$ if and only if $v\cdot w=1$. Recall that $(v_1,\dots,v_{11})\cdot (w_1,\dots,w_{11})=v_1w_1+\dots+v_{11}w_{11}$, where the addition and multiplication is $\pmod 2$.
Each point is colored by exactly $2^{10}$ colors, which is more than half of the colors. However, given any $10$ colors, with corresponding nonzero vectors $w_1,\dots,w_{10}$, there will always exist a vector $v$ which is orthogonal to all $10$ of them, meaning that $v\cdot w_i=0$ for each $i\in \{1,\dots,10\}$. Therefore, that $v$ is not colored by any of those colors, so these $10$ colors fail to color all points.
Here is the proof that for any $10$ vectors in $(\mathbb Z_2)^{11}$, there exists a nonzero $v\in (\mathbb Z_2)^{11}$ which is orthogonal to all of them. Consider the linear transformation $T:(\mathbb Z_2)^{11}\to (\mathbb Z_2)^{10}$, defined by $$T(v)=(v\cdot w_1,\dots,v\cdot w_{10}).$$ The rank nullity theorem implies $\dim(\text{im } T)+\dim(\ker T)=11$. Since $\dim(\text{im }T)\le 10$, we conclude $\dim(\ker T)\ge 1$, so there exists a nonzero vector $v$ for which $T(v)=0$.