0

here is the problem

The problem is quite complex and I would really like to know the solution.

Rand al'Thor
  • 116,845
  • 28
  • 322
  • 627
Unknown
  • 3
  • 1

1 Answers1

1

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.

phenomist
  • 13,602
  • 52
  • 70
  • 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. – Unknown May 21 '18 at 23:44
  • @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. – phenomist May 21 '18 at 23:48
  • Surprisingly, there actually is a strategy! – Deusovi May 21 '18 at 23:48
  • This argument fails to account for the fact that while Alice's actions don't depend on Trent's choice, Bob's do. – ffao May 21 '18 at 23:52
  • Oh oops, I thought Bob doesn't know Trent's card either. Misreading fail. – phenomist May 21 '18 at 23:52
  • Wait, I thought Bob doesn't know Trent's card, and has to guess blindly. What am I missing here? – MikeQ May 21 '18 at 23:54
  • 1
    Trent tells Bob what card to find – phenomist May 21 '18 at 23:55
  • Yes so you can open up to 26 cards and if one of them is the card Trent asked for, Bob will win – Unknown May 21 '18 at 23:57
  • 1
    @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! – ffao May 21 '18 at 23:59