The problem is quite complex and I would really like to know the solution.
1 Answer
There is a strategy that allows Bob to correctly find Trent's card with 100% probability. First, Alice and Bob agree on an ordering of the 52 cards. Call this function of card to position $f$. Bob's strategy is to start with card $f(T)$, where $T$ is the card Trent picks, and continue opening $f(f(T))$, and so on. If $T$ is in a cycle of size 26 or less, we win! Otherwise we lose.
Fortunately Alice can control the size of the cycles. Namely, there exists only one cycle at most with size greater than 26. If one exists, Alice can break the cycle into two smaller cycles of equal size via a single swap. For instance, if the cycle is $c_1 \rightarrow c_2 \rightarrow \cdots c_n \rightarrow c_1$, then Alice should swap cards $c_{\lfloor n/2\rfloor}$ and $c_n$. Then the cycles are $c_1 \rightarrow c_2 \rightarrow \cdots c_{\lfloor n/2\rfloor} \rightarrow c_1$ and $c_{\lfloor n/2 \rfloor + 1} \rightarrow c_{\lfloor n/2 \rfloor + 2} \rightarrow \cdots c_n \rightarrow c_{\lfloor n/2 \rfloor + 1}$, with cycle size at most $\lceil n/2 \rceil \leq 26$ Therefore, the final state does not have any cycle of size greater than 26, and the duo is guaranteed a one month salary increase.
-
$\begingroup$ I actually went into a lot of thought abt this and presumed that maybe Alice can hint ( through the switch off cards ) on which Side of the table there are more red cards and hence increase the probability of finding. Actually I find it so hard to believe that there is no actual solution to this because this problem was given to all the participants of Singaporean national Olympiad for informatics in the last round and the first 10 to solve were promised expensive gifts. $\endgroup$– UnknownMay 21, 2018 at 23:44
-
$\begingroup$ @Unknown Yeah, I've heard of similar puzzles (and I think one relies on the ability to control cycle size, which does convey information), and I think this puzzle mostly tries to riff off that. $\endgroup$ May 21, 2018 at 23:48
-
$\begingroup$ Surprisingly, there actually is a strategy! $\endgroup$– Deusovi ♦May 21, 2018 at 23:48
-
1
-
1$\begingroup$ @MikeQ It's not completely random -- remember Alice gets to tamper with them. As an extreme case, assume Alice can do as many swaps as she wants -- then Bob can trivially find any card in a single guess, since Alice can sort the cards in a previously decided order. This case is a lot less intuitive, but it turns out one swap is all Alice needs to guarantee Bob's success in 26 guesses! $\endgroup$– ffaoMay 21, 2018 at 23:59