This problem has stumped me:
Suppose we have $k$ colors (call them $1, 2, \dots, k$), and let $n = C_1 + C_2 + \dots + C_k$, where we make no assumption about the $C_i$ except that they are integers summing to $n$. We have $n$ objects to paint with the $k$ colors, and each object must be painted a solid color. Prove that for some $1 \leq i \leq k$, we must paint at least $C_i$ objects with color $i$.
Hint: by contradiction—what if we do not paint at least $C_i$ objects with color $i$, for every $1 \leq i \leq k$?
I get that it is most likely a pigeonhole principle problem but I do not understand what I have to prove. That there will be an unpainted object or two colors will be on the same object, and what the math behind that would be.
Is there any general tips for discrete math to get in the right state of mind to attack these problems?