Good example of something (although it's perhaps a bit trivial) that is a puzzle that seems to make even non-mathematicians curious is the 'justification' for g

Good example of something (although it's perhaps a bit trivial) that is a puzzle that seems to make even non-mathematicians curious is the 'justification' for greco-latin squares. The idea is that you have 6 files of 6 men. Each is of a different regiment, each is of a different rank. Is it possible to arrange them so that no row and no file have two men of the same rank or from the same regiment? You can mention this in your first lecture on algebraic geometry (or, for that matter, combinatorial geometry i.e. matroid theory) and then come back to it when you talk about projective geometries.