Alice is performing a magic trick. She has a standard deck of 52 cards, which she may order beforehand. She invites a volunteer to pick an integer \(0\le n\le 52\), and cuts the deck into a pile with the top \(n\) cards and a pile with the remaining \(52-n\). She then gives both piles to the volunteer, who riffles them together and hands the deck back to her face down. (Thus, in the resulting deck, the cards that were in the deck of size \(n\) appear in order, as do the cards that were in the deck of size \(52-n\).) Alice then flips the cards over one-by-one from the top. Before flipping over each card, she may choose to guess the color of the card she is about to flip over. She stops if she guesses incorrectly. What is the maximum number of correct guesses she can guarantee? Proposed by Espen Slettnes
Problem
Source: ELMO Shortlist 2023 C2
Tags: Elmo, combinatorics
02.07.2023 19:36
I'm not sure i understand this problem - why wouldn't the answer just be $0$? Because she can't guarantee that the card at the top of the $n$ pile and the card at the top of the $52-n$ are the same color; either of these cards could appear at the top after the reshuffling....
14.09.2023 15:22
@above She doesn't have to guess each time. Also, bumppp
24.11.2023 07:04
Alice can guarantee $\boxed{26}$ correct guesses. Instead of the "riffling" flavortext, it's a lot more intuitive to think of the $n$ cards and $52-n$ cards as two separate decks placed side by side on a table; then, at each turn, the volunteer will draw the top card from one of the two decks and announce it to Alice (or let Alice guess). As long as the volunteer picks $n=1$, Alice certainly can't get more than $26$ guesses right. Say the $1$-card deck is the left deck, and the $51$-card deck is the right deck; assume the $1$ card in the left deck is red. Then, at each turn, if Alice knows the top card on the right deck is red, she can confidently guess "red"; however, if she knows the top card on the right deck is black, she'll have to pass, since the volunteer could at any time choose the red card from the left deck. Therefore she passes on every black card, meaning she will get at most $26$ guesses right. To guarantee $26$ correct guesses, she alternates the cards black and red – say the top card is black. If $n$ is even, Alice knows that the top cards of both the left and right deck are black, so she guesses black. For all positive integers $i$, Alice passes on her $(2i)$th turn because the cards on the top of each deck are different colors. If the card revealed to her is red, this must mean that now, the cards on the top of both decks are black, so she guesses black on her $(2i+1)$th turn. On the other hand, if the card revealed to her is black, this must mean that now, the cards on the top of both decks are red, so she guesses red on her $(2i+1)$th turn. An almost identical process works if $n$ is odd. For all positive integers $i$, Alice passes on her $(2i-1)$th turn because the cards on the top of each deck are different colors. If the card revealed to her is red, she knows the cards on the top of both decks are black, so she guesses black on her $(2i)$th turn. On the other hand, if the card revealed to her is black, she knows the cards on the top of both decks are red, so she guesses red on her $(2i)$th turn. a remark: what happens if Alice doesn't know $n$? I misread the problem at first so I thought that's how it was, and the problem seems quite different (and a lot harder) in that case.
08.04.2024 15:24
A more intriguing question is what if there were more than 2 colours? I misread the problem and thought Alice was trying to guess the suits of the cards. Much more challenging problem I guess?
19.09.2024 08:39
ihatemath123 wrote: a remark: what happens if Alice doesn't know $n$? I misread the problem at first so I thought that's how it was, and the problem seems quite different (and a lot harder) in that case. In this case, the answer is $1$. Notice Alice can always get one guess correct by waiting until the last card. Denote red cards by zeroes and black cards by ones. Assume WLOG that the deck ends with a $1$, and let $k$ be the positive integer such that the last $k+1$ cards in the deck consist of $01 \cdots 1$. Let the volunteer shuffle the deck so that the first $52-k-1$ cards are unchanged and the last $k+1$ cards are $1 \cdots 10$. Alice cannot guess the first $52-k-1$ cards because she has no way of knowing if a card was originally the $(k+1)^\text{th}$ card from the bottom (a $0$) or the bottommost card (a $1$). Alice cannot guess the next $k$ cards because she has no way of knowing if a card was originally the $(k+1)^\text{th}$ card from the bottom (a $0$) or a card from the bottom $k$ (a $1$). Thus, Alice can guarantee at most one correct guess. $\blacksquare$