Pigeonhole Principle of 18 pennies in a square of 6x6 I have a question regarding the Pigeonhole Principal. I essentially understand what it is but I am stuck on a problem:
18 pennies are placed on the squares of a 6x6 chess board randomly, up to one penny on each square of the 36. 
a) Prove that there is a row and column of the board that contain at least 5 pennies together. 
b) Show that there is an arrangement of the 18 pennies in a way such that no row-column combination would contain more than 6 pennies.
How would I go about this problem? I just can't seem to grasp the concept 100% especially one that would involve some drawings. Thank you.

1) Assume that every row-column pair contained 4 pennies. Add up the number of pennies in each row-column pair across all row-column pairs. This gives $4\cdot 36$ pennies. However, we have counted each penny several times, specifically $12$ times (once for each row and once for each column). Dividing by $12$ yields $12$ pennies on the board. Therefore any arrangement with $4$ or fewer pennies in each row-column pair cannot have more than $12$ pennies, as adding one more penny on any square will break the rule.
As noted in the comments, this same argument can be used to show that $5$ pennies in each row-column pair doesn't work (you find that there are $15$ pennies), and so in fact any arrangement requires at least $6$ pennies in some row-column pair.
2) Generally, "greedy" approaches (where you build the answer iteratively by making the best choice at each step) work for problems like this. If you work row-by-row filling each row with $3$ pennies in a way that makes no column have more than $3$ pennies, pretty much every possible arrangement works. For example, both the two-blocks-of-nine approach and the shift-the-row-by-one approach work. You'll note that both of these approaches produces $6$ pennies in every row-column pair. I postulate that this is necessarily the case, and that $19$ pennies requires at least $7$ in some row-column pair.
