Bdtyktl

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?

Example:

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

Hint:

The answer for 9 cards is 3

I think you can get the bound down to

$lceil sqrt{N} rceil$, that is the square root of $N$, rounded up.

In the following way

Order the cards from $1$ to $N$ and partition them into $left[ frac{N}{lceil sqrt{N} rceil} right]$ subsets of size $lceil sqrt{N} rceil$ plus one additional subset of the leftovers (may have size zero). Then, reverse the order of the cards within each subset.

For example for $N=18$, we divide the cards into $3$ subsets of size $5$ and one of size $3$, i.e, $$ 1,2,3,4,5|6,7,8,9,10|11,12,13,14,15|16,17,18$$ then reverse the cards within each subset $$5,4,3,2,1|10,9,8,7,6|15,14,13,12,11|18,17,16$$ Then our maximum increasing or decreasing subsequence has size $5$.

For $N=9$ the corresponding ordering is $3,2,1,6,5,4,9,8,7$ which indeed has its longest increasing or decreasing subsequence with size $3$.

Why this works

To obtain an decreasing subsequence (option A) your friend must choose all of their cards to be within one of the partitions above (as cards between partitions are in increasing order). This gives them a maximum of $lceil sqrt{N} rceil$. On the other hand, if they choose option B, then all the cards they pick must be in different partitions as defined above, which gives them a maximum of $left[ frac{N}{lceil sqrt{N} rceil} right] leq frac{N}{lceil sqrt{N} rceil} leq lceil sqrt{N} rceil$. I think this is the best we can do while balancing the advantages of the two options.

There is actually a theorem which basically says that hexomino's solution is optimal. The name is

Erdős–Szekeres theorem.

Maybe I'm missing something, but

Put the cards 1..N/2 in increasing order, and N..N/2+1 in decreasing order. The friend gets at most N/2 cards (rounded down).


For example, with N=9:

1, 2, 3, 4, 9, 8, 7, 6, 5
The friend gets either 8, 7, 6 and 5 (option A) or 2, 3, 4 and 9 (option B).


With N=8:

1, 2, 3, 4, 8, 7, 6, 5

The friend gets either 7, 6 and 5 (option A) or 2, 3, 4 and 8 (option B).