I got this problem from Rustan Leino, who was told it by Roger Wattenhofer.
I solved it and wrote up my solution.
Someone picks, at their will, two cards from a deck of cards. The cards have different numbers, so one is higher than the other. (In other words, the person picks two distinct numbers in the inclusive range 1 through 13.) The cards are placed face-down on a table in front of you. You get to choose one of the cards and turn it face-up. Now, you'll select one of the two cards (one of which you can see the face of, the other one of which you can't). If you select the highest card, you win. Design a card-selection strategy for which your chance of winning is strictly greater than 50%.
Flip a fair coin to choose the card you look at. After looking at the card, roll a fair 12-sided die with faces labeled 1 through 12. If the number you saw (which is in the inclusive range 1 through 13) is greater than the die-roll result, then select the card you looked at. Otherwise, select the face-down card.
The reason this works is as follows.
Call the numbers on the cards $a$ and $b,$ where $a < b,$ so that you win if you select card $b.$
If you look at card $a,$ you'll select the other one and win if you roll a number $\geq a.$ There are $13-a$ such numbers on the die, so your conditional probability of winning in this case is $(13-a)/12.$
If you look at card $b,$ you'll select it and win if you roll a number $< b;$ there are $b-1$ such numbers on the die, so your conditional probability of winning in this case is $(b-1)/12.$
Since you flip a fair coin to choose which card to look at, your probability of looking at $a$ is $1/2,$ the same as the probability of looking at $b.$ Thus, your overall probability of winning is $(1/2)(13-a)/12 + (1/2)(b-1)/12.$ This is equal to $1/2 + (b-a)/24.$ Since $a < b,$ this probability is greater than 50%.