You and your friend are playing a game with a deck of cards numbered 1 to N.
You will first put the deck of cards in whatever order you want. Next your friend will choose an option: "A" or "B". Finally, you will give your friend each card of the deck in order. For each card, your friend may either choose to keep it or discard it.
If they chose "A", your friend can only keep a card if it has a smaller number than the last card they kept. If they chose "B", they can only keep a card if it has a greater number than the last card they kept.
You know your friend is a cheater, and they know the order of the cards beforehand. How should you order the cards so your friend keeps the least # of cards possible?
There are 3 cards. Then you should order them 3, 1, 2. There is no option with better answer.
Source: COCI '14 Contest 6 #4 Kratki
The answer for 9 cards is 3