We have a $
5 \times 5$ grid of points, all colored white. Now 11 of the 25 points are colored black. Prove that it is possible to find 3 points all colored black such that no two of them share the same row or column.
I strongly feel this can be proved using the Pigeonhole Principle. Hence, I tried to attempt by finding the number of triplets of points which satisfy the condition of not sharing rows or columns. This comes out to be 600 out of total of 2300 ways to pick triplets. The number of triplets with 3 black points is 165. I could not proceed any further, with such values.
I also thought 11 black points must occupy at least 3 distinct rows and columns, using Pigeonhole principle. I think I am close to the solution with this approach but am not able to connect the result to be proved with this observation.
Best Answer
Color the table diagonally like this:
Then we have 5 ''diagonals'' and 11 pigeons, so one diagonal must contain 3 pigeons and we are done.