The card game Push is played between two people. A deck is shuffled then divided in half, with each player receiving a half (face down). During a round, both players reveal the top card of their deck; the high card scores a point. (Ties are handled in a special way.) The winning player is whoever has the most points after all of the cards have been revealed. Obviously players can control the outcome of the game by magically manipulating probabilities.  In this brief note, I discuss optimal strategies for increasingly complex variations of the game. I describe the variant in one paragraph, followed by the solution. You should feel free to read the variant and discover the solution on your own.

1 Two full decks

Problem: Suppose you are playing a simpler version of this game where you and your opponent each get a full deck of cards. Suppose the cards are numbered, say 1 through 52. Finally, suppose you know the exact order of your opponent's cards, which will not change. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: The [only?] optimal solution is whenever your opponent plays a card, you play the card ranked one above it. The only card for which this strategy is impossible is when your opponent plays the highest-ranked card in the deck (which is unbeatable) in which case you play the lowest-ranked card in the deck. This "rotate by one" strategy is optimal because you win every round except the one in which your opponent plays a card that can never lose and you match it with a card that can never win.

2 Splitting one deck

Problem: Now suppose we split a single shuffled deck in half, giving one half to you and one half to your opponent. Suppose you still have perfect knowledge in this variant: you know exactly the shuffled order of your opponent's cards, which will not change. Consequently, you can determine which cards you've been dealt. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: Note that we are trying to decide which cards in your deck to match against which cards in your opponent's deck. Once we've decided on that matchup policy, it doesn't matter how the opponent's deck is shuffled; just play the corresponding matched card. Here's an optimal strategy: You know which cards you have and which cards your opponent has. Mentally arrange your deck in ascending order of rank, and arrange your opponents cards the same way. Look at your opponent's highest-ranked card, and pair it with the lowest-ranked card you have that can beat it. (If none of your cards can beat it, pair it with your lowest-ranked card overall.)  Eliminate those two cards from consideration and repeat the matching process. This strategy is at least locally optimal because whenever you play a high card, you win, and whenever you don't, it's impossible to win. I suspect it is globally optimal as well. This strategy is also very general: it subsumes the strategy from the previous section, and actually applies to any two decks of the same size (not just decks created by splitting a single deck in half).

3 Opponent plays at random

Problem: Now suppose you only know the contents, but not the order, of both decks: we split a single shuffled deck in half, giving one half to you and one half to your opponent. You know which cards each person has, and your opponent's cards are in a fixed but unknown order. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: Perhaps surprisingly, you can't do anything strategic against a random opponent. Regardless of your chosen strategy, your expected score is equal to the probability that you win a random matchup between one of your cards and one of theirs, times the number of cards you have. You can prove this by induction, using an n-by-n matrix which has a 1 in entry (i,j) if your ith card beats their jth card and a 0 otherwise. Regardless of strategy, your expected score is equal to the sum of the entries in this matrix, divided by n.

4 Paying for entropy

Problem: Next, we introduce tychokinetic costs. Again, a shuffled deck is split in two, with both players receiving a half. You know the contents of both decks, and as with the deterministic variant, suppose you know the fixed order of your opponent's deck. Normally, when you play a card, you are drawing uniformly from the set of all cards you haven't played yet. Using tychokinesis, you may instead choose to draw uniformly from a smaller subset. The smaller subset consists of your choice of one or more cards that you haven't played yet. When drawing from a smaller subset, you must pay an entropy cost of (n/k) log(n/k), where k>0 is the size of the subset and n is the total number of unplayed cards in your deck. Suppose you just want to win, not necessarily by the largest possible margin. Find the strategy that minimizes the amount of entropy you pay for, subject to the condition that you still win the game if possible.

Solution: ???