MathDB

There are two different versions of this problem, each with different solutions. You must find bounds for each of these problems.
[*] Alice and Bob are playing a collaborative game in which they agree upon an encoding/strategy. Alice shuffles a deck of 52 cards (numbered 1-52) (*) and takes the first

n

cards off the top of the deck. Alice then chooses one card to be put to the side, and chooses an ordering of the other

n-1

cards. Bob then walks into the room seeing the

n-1

cards in the order Alice put them in. For example, if Alice was given 9-4-10-51-7-8 and chose to put 8 to the side, she could put 5 cards in order of 9-4-10-51-7 which Bob would see.
Find the lowest

n

for which Bob could guarantee that he could use Alice's encoding to find the card placed to the side.
(*) (If you would prefer, you can write your solution in terms of the deck being a standard deck with 4 suits and 13 ranks, there's a way to move between them that we can handle.)
[*] Alice and Bob are playing a collaborative game in which they agree upon an encoding/strategy. Alice shuffles a deck of 52 cards (numbered 1-52) and takes the first

n

cards off the top of the deck. Alice then chooses one card to be put to the side, and chooses an ordering of the other

n-1

cards. Carol then comes in to the room and randomly discards one of the

n-1

cards, and places the cards back in a way that preserves the order Alice had. Bob then walks into the room seeing the

n-2

cards in the order Alice put them in. For example, if Alice was given 1-2-3-4-5-6 and chose to put 6 to the side, she would put 5 cards in order of 1-2-3-4-5, and Carol removed 4, Bob would see 1-2-3-5.
Find the lowest

n

for which Bob could guarantee that he could use Alice's encoding to find the card placed to the side.
Proposed by Eric Oh

Problem Statement