This is a question that my professor asked to the class.
There are 52 cards with numbers ranging from 1 to 52 on them. There will be 2 players, and their aim is to find a card on the card list in at most 26 tries. They will have time to speak before game starts. After game starts, Player 2 will leave the room and Player 1 will see all the cards. Player 1 has to swap 2 cards so when Player 2 comes back, he can find the desired card in at most 26 tries. Player 1 does not know the desired card. Which cards Player 1 needs to swap so Player 2 can find the desired card in at most 26 tries?
Professor solved this problem by finding the biggest cycle in the list and dividing it so the biggest cycle can include at most 26 cards. He gave an example where Player 2 trying to find card with 37 number so they look for the card in 37th index first, if it has number 9, they look for 9th index etc.
No one in the class could answer this question unless professor mentioned Permutation Graphs. He also added this question belongs to some 12 year olds math competition.
I do not understand how this works so I thought it would be great to ask it here.
This is a variation of 100 prisoners problem. The main idea of the solution is the following.
Let's substitute all cards by numbers $1, 2, \ldots, 52$. Then the deck is a permutation of these numbers. Without help of the first player, every strategy of the second player gives the same result of winning probability $1/2$. But with such a help, everything changes and they have a guarantee to win.
They can agree that the second player acts in the following way. Suppose he wants to find a card $c_0$. Then firstly he takes a card (= number) $c_1$ from the position $c_0$. After that he takes a card $c_2$ from the position $c_1$. And so on, taking card $c_i$ from the position $c_{i-1}$. The main idea is that at some point he always takes card $c_0$, because he always moves along corresponding cycle of the permutation.
However this cycle may be too long initially. So all the first player needs to change is the cycle that is longer than $52 / 2 = 26$ numbers (if such a cycle exists). The first player should find it and split it into two cycles. He even doesn't need to know $c_0$ in advance! Because there can be at most one cycle longer than $52 / 2 = 26$ numbers. To destruct such a cycle $x_1x_2\ldots x_kx_1$ of length $k > 26$ it is enough to swap two cards at distance of at least $k - 26$, for example $x_1$ and $x_{27}$, or $x_1$ and $x_{1 + \lfloor k / 2\rfloor}$.
Reference to the permutation graph seems to be incorrect. I guess the professor meant the following. If we introduce a directed graph $G_{\pi}$ where vertices are elements of permutation $\pi \in \mathbb S_{52}$ and there is an arc $(i, \pi(i))$ for every $i = 1, 2, \ldots, 52$, then we can prove that such graph $G_{\pi}$ always consists of one or more cycles (thinking a vertex with self-loop to be a cycle).