Puzzle contest announcement

A question that just came in regarding the Column 3 puzzle: "Does the astronaut take out the boots one at a time or does she take out k boots all at once (where 0 < k <= 20)?" It is the latter. The astronaut takes out k boots all at once (where 0<k<=20). The question basically is - what is the minimum k such that she is guaranteed to have a pair of boots - one left and one right?

One could easily change the puzzle in subtle ways and pose variations of the same question, and one would get vastly different answers depending on the mathematics of the problem. And that is the beauty of it.

Anyway, the question came in in the context of the announcement of a contest for the puzzle in Column 3. We are running a contest for this puzzle in association with the Stanford Math Circle. The problem is really quite a bit easier than it looks. The prize is a $40 Amazon.com gift card. Anybody is eligible to participate but you have to pick up your prize at the Stanford Math Circle meeting. If you are not from the Bay Area, you could use a proxy to pick up the prize. That's about it about the puzzle contest. Happy solving!