1270.12 – Pigeonholes no. 2

What is the largest number of pigeonholes that can be occupied by 100 pigeons if each hole is occupied but no two holes contain the same number of pigeons? (Some of these pigeonholes will be roomy.)

Solution

Start by putting 1 pigeon in hole #1, 2 pigeons in #2, and so on. When we get up to 13 we have taken care of 1 + 2 + . . . + 13 pigeons, and the formula for that sum is 13⋅142=91.\frac {13\cdot14}{2}=91. There are 8 pigeons left but we already have a pigeonhole with 8, no good.

We see that if we to up to 14 we are over our 100 pigeons: 14⋅152=105\frac {14\cdot15}{2}=105, no good.

We'd better back up to 12: 1 + 2 + 3 + . . . + 12 = 12⋅132=78\frac {12\cdot13}{2}=78. So in the 13th pigeonhole we'll stuff in 22 pigeons (yikes!), and that takes care of our 100.