Pigeonhole Principle of 18 pennies in a square of 6x6

Question

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.

Answer 1

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.

Answer 2

As for (b), just place the pennies on the black squares.

Answer 3

Rows and columns intersect in exactly one cell. So if a row has $i$ pennies and a column has $j$ pennies, their union has either $i+j-1$ or $i+j$ pennies.

For part (a), we can choose the row and column separately: we pick a row with the most pennies ($i$ say), and a column with the most pennies ($j$ say).

Since there are 6 rows, the number of pennies is thus $\leq 6i$. Since there are 6 columns, the number of pennies is thus $\leq 6j$. This gives lower bounds on $i$ and $j$, and thus a lower bound on $i+j-1$.

Part (b) seems adequately resolved by TonyK's answer.