The integers 1 thru 100 are written on individual cards, and those 100 cards are mixed into a hat. Aisha draws one card at a time, without replacement, until she draws a card relatively prime to all the cards she has already collected. What is the maximum number of cards Aisha could draw in this game?

Solution: 90.  One can construct a sequence of maximal length as follows:

• Starting with 2, include all the even numbers from 2 through 100, a total of 50.
• Ignoring 1, now include all the odd numbers that are not primes over 50. Since there are 10 primes between 50 and 100, there are 49-10=39 of these.
• The 90^th pick will now either be a 1 or a prime over 50, all of which will be relatively prime to all those on the list.