Today’s strategy is the well-known box (or pigeonhole) principle: if n+1 items are distributed among n boxes, at least one box must contain more than one item.
More generally, if kn+1 items are distributed among n boxes, at least one box must contain at least k+1 items.
Sample problem: Five points with integer coordinates are chosen on the plane. Prove that you can always choose two of these points so that the segment joining them passes through another point with integer coordinates. (The solution is at the end of the worksheet).
For the worksheet, click here.