# Proof that there are at least 10 colored cells in a column with the pigeonhole principle

I have a table with 13 rows and 10 columns, and I have to prove that if every row has at least 7 colored cells there will be a column with at least 10 colored cells (with pigeonhole principle).

From what I understand there are 10C7=120 ways to choose cells in each row, but do I relate it to the columns?

• Try thinking about the following two points: (1) As every row has at least $7$ coloured cells, what do you know about the total number of coloured cells? (2) If every column had up to $9$ coloured cells, what would that imply about the total number of coloured cells?
– user700480
Commented Dec 27, 2019 at 17:41
• Thanks! I get it now. Commented Dec 27, 2019 at 17:49

Since every row has at least $$7$$ colored cells, we have at least $$7\times 13 = 91$$ colored cells in total. So, by the pigeonhole principle, there will be a column in the $$10$$ columns with at least $$\lceil 91/10 \rceil = 10$$ colored cells.