Problem #17 - shuffle me around


< change language

This post contains a problem that haunted me for a couple of years. I had it lingering in my brain for a long time and it felt quite challenging... then I presented it to a friend of mine one night, and the morning after I had a text from him saying he had cracked it! So kudos to him! I only got to the answer after he gave me a hint...

Problem statement: you and a friend are outside a room guarded by a sphinx. The sphinx tells you that inside the room there are 100 drawers, numbered from $1$ to $100$, where each drawer contains one of a hundred balls, also numbered from $1$ to $100$. The balls are randomly shuffled inside the drawers but each drawer contains exactly only one unique ball. You, your friend and the sphinx are to play a game. First of all, your friend is going to the room where he will be able check the contents of each drawer for as long as he wants; he will also be given the opportunity to swap the balls of two drawers. This swap is not mandatory. When your friend leaves the room the sphinx will tell you a number $n$ from $1$ to $100$ and you will go into the room to find the ball with the number $n$ in $50$ attempts or less.
What is the strategy that you and your friend should follow that maximizes the probability of finding the ball the sphinx picks?

Hint: checking $50$ drawers at random gives you $50\%$ probability of winning.

Solution: there is a strategy that guarantees that you will be able to find the ball that the sphinx picks. Take one more moment to think it through, now that you know for a fact that there is a perfect strategy.
The solution can be phrased shortly if you are familiar with permutations: the task of your friend is to go inside the room and see the balls inside the drawers as a permutation of the numbers from $1$ to $100$; check if the permutation has a cycle of length larger than $50$ and, if so, break it. When you go into the room, just start by opening the drawer $n$ and then follow the cycle it traces until you hit the ball $n$; because your friend broke the only possible cycle of length greater than $50$, you are guaranteed to find the ball you are looking for.
Now let me break it down for people who are not familiar with permutations or who aren't comfortable with them. For this I will also exemplify with a similar problem but with $6$ drawers/balls and a maximum of $3$ attempts. Assume this is the state the room is in: $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 3 & 6 & 1 & 4 \end{bmatrix}$$ where the top row gives the number of the drawer and the bottom row gives the number of the ball inside that drawer. If you imagine the numbers of the balls as telling you where to go next, you can sort of write out some "paths":
  • Starting at drawer $1$, extract ball number $2$ -> open drawer $2$ to find ball $5$ -> open drawer $5$ and find ball $1$ -> now you are back at the start;
  • Starting at drawer $3$, extract ball number $3$ -> you don't even get to move;
  • Starting at drawer $4$, extract ball number $6$ -> open drawer $6$ to find ball $4$ -> back where we started.
These sequences of moves $1 \to 2 \to 5 \to 1$, $3 \to 3$ and $4 \to 6$ are actually cycles. If you decide that your strategy will be to follow cycles, then it doesn't matter if you start with drawer $1$, $2$ or $5$: you will open all three of them in pursuit of the $n$ ball. Note this, as well: if you start the cycle of the drawer $d$, at the end of the cycle you find the ball with number $d$... So if you wanted to find, say, ball $4$ you would go through the cycle starting at the drawer number $4$, and you would find the ball $4$ after two attempts. If you wanted ball $5$, you would go to drawer $5$ and follow the cycle: you would find the $5$ ball at the third attempt, just the maximum number of guesses you had.
Now the actual solution to the problem lies in two small considerations:
First, after the balls are randomly shuffled, there cannot be more than one cycle with length greater than $50$.
Second, your friend can always go into the room and break the lengthy cycle into two bits of length smaller than or equal to $50$.

As to the first statement, we can think of the cycles as those diagrams with arrows that just go around, so the diagram $1 \to 2 \to 3 \to 1$ is the same as the diagram $2 \to 3 \to 1 \to 2$. Then each diagram contains some portion of the total number of balls available, and two different diagrams cannot share numbers. For example, it would not make sense to have both these diagrams: $1 \to 6 \to \cdots \to 1$ and $2 \to 6 \to \cdots \to 2$ because it means that both the drawer number $1$ and drawer number $2$ have the ball with the number $6$, which cannot be the case. So if there were two different cycles with length greater than $50$ we would need at least $102$ balls, but we only have $100$. So there is, at most, one cycle of length greater than $50$.
Now we just have to show that your friend can always break a cycle that is too long. The easiest way to prove this is to show how it is done; for that, I will exemplify and let you extrapolate for the case where we have $100$ balls. Suppose we had the cycle $1 \to 6 \to 2 \to 4 \to 3 \to 5 \to 1$, which has length $6$; we are going to break it into two cycles of length $3$. That cycle means our drawers look like this: $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 5 & 3 & 1 & 2 \end{bmatrix}$$ and the problem is that after opening drawer number $2$, we should be sent back to $1$ but instead got sent to $4$... Well, then move the ball $1$ to drawer $2$ and put the ball that was inside drawer $2$ in the drawer from which you got ball $1$... So do this swap: $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 5 & 3 & 1 & 2 \end{bmatrix} \mapsto \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & \underline{\textbf{1}} & 5 & 3 & \underline{\textbf{4}} & 2 \end{bmatrix}$$ Now we have the cycles $1 \to 6 \to 2 \to 1$ and $3 \to 5 \to 4 \to 3$.
And this proves what we needed! Going over it one more time, your friend has to go inside the room and if there is a cycle that is too long, break it. When the sphinx asks you to find ball $n$, just go into the room, open the drawer $n$ and follow the path the cycle gives you!

If you liked this post, consider subscribing to the Mathspp newsletter and like it on Facebook.
O problema deste post perseguiu-me durante um par de anos. Eu achava que era um problema bastante difícil e durante uma noite partilhei-o com um amigo. Na manhã seguinte tinha uma mensagem dele a dizer que o tinha resolvido. Eu só o consegui resolver depois de ele me dar uma pista bastante óbvia...

Enunciado: dois amigos estão à porta de uma sala que está guardada por uma esfinge. Dentro da sala estão 100 gavetas numeradas de $1$ a $100$ e cada gaveta tem uma única bola; as cem bolas também estão numeradas de $1$ a $100$ e as bolas estão distribuídas aleatoriamente pelas gavetas (uma única bola por gaveta). Os dois amigos e a esfinge jogam um jogo: o primeiro amigo entra na sala e pode abrir as gavetas que quiser e olhar para dentro delas; pode, ainda, escolher duas gavetas e trocar as bolas dentro dessas duas gavetas. Depois, sai da sala. De seguida, a esfinge escolhe um número $n$ de $1$ a $100$ e diz esse número ao segundo amigo, que tem de entrar dentro da sala e encontrar a bola com o número $n$! Para isso, tem $50$ tentativas. Qual é que é a estratégia que os dois amigos têm de combinar para maximizar a probabilidade de conseguirem encontrar a bola que a esfinge escolher?

Pista: se a estratégia do segundo amigo for abrir $50$ gavetas ao acaso, os amigos têm $50\%$ probabilidade de ganharem.

Solução: há uma estratégia que permite aos dois amigos ganharem sempre, independentemente da bola $n$ que a esfinge escolha. Se ainda não tinham resolvido o problema, tentem outra vez. Saberem que há uma estratégia perfeita facilita o problema um bocado.
Para as pessoas que conhecem permutações, a solução é fácil de descrever: o primeiro amigo tem de entrar na sala e ver as bolas dentro das gavetas como uma permutação dos números de $1$ a $100$; se houver um ciclo com tamanho superior a $50$, então o primeiro amigo tem de usar a sua troca para quebrar esse ciclo. Quando o segundo amigo entra na sala, ele deve começar por abrir a gaveta $n$ (a gaveta com o número que a esfinge escolheu) e depois deve seguir os números das bolas que lhe vão aparecendo; precisamente por o primeiro amigo ter quebrado o único ciclo de tamanho maior que $50$, o segundo amigo tem a garantia de que vai encontrar a bola $n$ em $50$ tentativas ou menos.
Agora vou apresentar uma solução mais explícita para quem nunca trabalhou com permutações ou precisa de uma revisão. Para este efeito, vou simplificar o problema e assumir que há $6$ gavetas/bolas e que os amigos só têm $3$ tentativas. Suponhamos que a sala estava assim: $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 3 & 6 & 1 & 4 \end{bmatrix}$$ os números da fila de cima são o número da gaveta e os números da linha de baixo são as bolas dentro de cada gaveta. Se pensarmos que o número de uma bola nos está a dizer a gaveta para onde devíamos ir a seguir, então conseguimos criar alguns "caminhos":
  • Começamos na gaveta $1$, tiramos a bola número $2$ -> abrir a gaveta $2$ e tirar a bola $5$ -> abrir a gaveta $5$ e tirar a bola $1$ -> e agora estamos de volta ao ponto de partida;
  • Começamos na gaveta $3$, tiramos a bola número $3$ -> nem saímos do lugar;
  • Começamos na gaveta $4$, tiramos a bola número $6$ -> abrimos a gaveta $6$ e tiramos a bola $4$ -> de volta ao princípio.
As sequências de movimentos $1 \to 2 \to 5 \to 1$, $3 \to 3$ e $4 \to 6$ são ciclos. Se decidirmos que a nossa estratégia é seguir um ciclo, então não interessa se começamos com a gaveta $1$, $2$ ou $5$: vamos abrir as três à procura da bola $n$. Note-se também isto: se começarmos um ciclo na gaveta $d$, então no fim do ciclo está a bola $d$... Portanto se estivermos à procura, por exemplo, da bola $4$, devemos começar o ciclo na gaveta $4$ e à segunda tentativa encontraríamos a bola $4$. Se quisessemos a bola $5$, abriamos a gaveta $5$ e seguíamos o ciclo: encontraríamos a bola $5$ à terceira tentativa, que é precisamente o limite máximo de tentativas que poderíamos usar.
Para chegarmos à solução final do problema, basta-nos notar duas coisas:
Primeiro, independentemente do modo como as bolas estão distribuídas, é impossível haver mais do que um ciclo com comprimento maior que $50$.
Segundo, o amigo que entra primeiro na sala pode sempre partir o ciclo mais comprido em dois ciclos mais pequenos, cada um com comprimento menor que $50$.

Para provar a primeira consideração, vamos pensar nos ciclos como os diagramas de setas que "dão a volta", de modo que os diagramas $1 \to 2 \to 3 \to 1$ e $2 \to 3 \to 1 \to 2$ representam o mesmo ciclo. Assim, cada diagrama contém alguma quantidade do número total de bolas e dois diagramas diferentes não podem ter bolas com números iguais. Por exemplo, não faz sentido ter o diagrama $1 \to 6 \to \cdots \to 1$ e o diagrama $2 \to 6 \to \cdots \to 2$ ao mesmo tempo, porque isso quer dizer que tanto na gaveta $1$ como na gaveta $2$ está uma bola com o número $6$, e nós sabemos que isso nunca acontece. Portanto, se houver dois ciclos diferentes com comprimento maior que $50$, então cada um deles tem pelo menos $51$ bolas e precisaríamos de, no mínimo, $102$ bolas diferentes para que isso fosse possível. Mas nós só temos $100$ bolas, portanto é impossível haver dois ciclos com comprimento maior que $50$.
Finalmente, vamos mostrar que o primeiro amigo a entrar na sala pode sempre partir um ciclo que seja demasiado grande. A forma mais fácil de mostrar que isto é possível é explicando como se faz; para tal, vou exemplificar para o caso em que temos $6$ bolas. Vamos supor que temos o ciclo $1 \to 6 \to 2 \to 4 \to 3 \to 5 \to 1$ que tem comprimento $6$ e que nós vamos partir em dois ciclos de comprimento $3$. Se temos este ciclo, então é porque as nossas gavetas estão assim: $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 5 & 3 & 1 & 2 \end{bmatrix}$$ e o problema é que, depois de abrir a gaveta com o número $2$, devíamos ser enviados de volta para a gaveta $1$ mas em vez disso somos enviados para a gaveta $4$... Bom, então o que há a fazer é pôr a bola $1$ na gaveta $2$ e pegar na bola que estava na gaveta $2$ e pô-la no sítio de onde tirámos a bola $1$... Portanto faríamos esta troca: $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 5 & 3 & 1 & 2 \end{bmatrix} \mapsto \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & \underline{\textbf{1}} & 5 & 3 & \underline{\textbf{4}} & 2 \end{bmatrix}$$ Agora temos os ciclos $1 \to 6 \to 2 \to 1$ e $3 \to 5 \to 4 \to 3$.
E isto prova o que precisávamos! Resumindo, o primeiro amigo entra na sala e descobre se há algum ciclo demasiado comprido; se houver, parte-o em dois. Quando a esfinge pedir ao segundo amigo para encontrar a bola $n$, basta ir até à gaveta $n$ e seguir o ciclo que a bola dentro da gaveta $n$ vai começar!

Se gostaram deste post, considerem subscrever a newsletter do blog e deixem um like no Facebook.

  - RGS

Comments

Popular posts from this blog

Markov Decision Processes 02: how the discount factor works

Problem #16 - the hamburger dilemma

Markov Decision Processes 01: the basics