Puzzles

"For now, what is important is not finding the answer, but looking for it" - Kurt Gödel

Here are some fun mathematical puzzles that I have come across.

  1. Say there are 100 prisoners, numbered \(J_1 - J_{100}\). Slips of paper containing each of their numbers, 1 - 100, are randomly placed in a 100 boxes in a sealed room. One at a time, each prisoner is allowed to enter the sealed room and open any 50 of the 100 boxes, searching for their number and afterwards, they must leave the room exactly as they found it, and they can't communicate in any way with the other prisoners. If all 100 prisoners find their own number with the given 50 tries, they will all be freed. But if even one of them fails to find their number, they will all be executed. The prisoners are allowed to strategize before, before any of them goes into the sealed room. What is their best strategy and provide a mathematical reasoning, why you think so! (Hint: If they each search for their own number "randomly", then the probability of each success, \(\text{Prob} (J_i) = \frac{1}{2}\), where \(1 \le i \le 100\), so the total success probability, \[\text{Prob}\left(\bigcup_{i = 1}^{100} J_i\right) = \prod^{100}_{i = 1} \text{Prob}\left(J_i\right) = \left(\frac{1}{2}\right)^{100} = 0.0000000000000000000000000000008\] which looks kind of pathetic, so provide a better strategy such that the probability of total success is better than this crap! You may ask, what is the hint here! I provided a bound to work on, LOL!)
    2. Click the toggle for solution! Our main goal is to provide a right strategy, in which we can raise their chances to nearly one in three, ie. approx 0.31, really!!!! it improves their odd of a random chance by nearly 30 orders of magnitude. So, here is the solution!
    Pretend you are one of the prisoners, when you go into the room, open the box with your number on it, the number on the slip inside probability won't be yours, but that's okay! Then go to the box with that number on it, look at the number inside, then go to the box with that number on it and so on. Keep doing this until you find the slip with your number. If you find your number, that essentially tells you to go back to the box where you started. It closes the loop of the number you have been following, but if you've found your number, thn you are done. You can stop and leave the room. This simple strategy gives over a \(31\%\) chance, that all prisoners will find their number. Let me give a detailed explanation.
    The first thing to notice is that all boxes become part of a closed loop. The simplest loop would be a box that contains its own number. If \(J_1\) goes to box one, it contains slip one, then \(J_1\) is done. \(J_1\) was put in a loop of length one, but one could have a loop of 3, 5, or 5, or any length all the way upto 100. But more generally, any random arrangement of the slips in these boxes, will result in the mixture of some shorter and some longer loops. When you start with a box labeled with your number, you are guaranteed to be on the loop that includes your slip. So the thing that determines whether or not you find your slip is the length of the loop. If your number, is part of the loop that is shorter than 50, then you will definitely find your slip, but if its longer you are in trouble!!!
    When you open the box, labeled with your number, you are infact starting at the farthest point on the loop from your slip. You wanna know where is the slip that points to this box, but to find it, you have to follow the loop of numbers all the way around to the end. That means, if the prisoners follow this strategy and the longest loop is 51, not just one or two prisoners will fail to find their number, but all 51 on this loop won't make it. They would make it to the box just before the box with their slip, but they would have to stop searching there. So, the probability that a random arrangement of a 100 numbers, contains no loops longer than 50 is \(\sim \frac{1}{3}\).
    But how? If you connect 100 boxes to form a loop of length 100, you could have \(100!\) different ways of arranging. Some of the loops that look different, are actually exactly the same loop, for example \[ \begin{aligned} \boxed{2} \to \boxed{3} \to \boxed{4} \to \cdots \to \boxed{100} \to \boxed{1} \ = \ \boxed{1} \to \boxed{2} \to \boxed{3} \to \cdots \to \boxed{100} \to \boxed{1} \end{aligned} \] You can rearrange the way you write those numbers in a 100 different ways, but they all represent the same loop. So the total number of unique loops of length 100 is, \[ \frac{100!}{100} \] So, now what is the probability that any random arrangement of 100 boxes, will contain a loop of length 100? \[ \text{Prob}(L = 100) = \frac{\# (\text{unique loops})}{\text{total permutations}} = \frac{\frac{100!}{100}}{100!} = \frac{1}{100} \] So, there is a \(1\%\) chance that a random arrangement of slips results in a loop of length 100, and we can genenralized the above result for any length, \[ \text{Prob}(L = n) = \frac{\frac{n!}{n}}{n!} = \frac{1}{n} \] So the probability, that there exists a loop longer than 50, is \[ \sum^{100}_{i=51} \frac{1}{i} = \frac{69}{100} = 0.69 \] So there is a \(69\%\) chance of failure for the prisoners, meaning a \(31\%\) chance of success, where the longest loop is 50 or shorter.
    So using the loop strategy, what is the probability that each prisoner alone finds their number? It is still only \(50\%\). Each prisoner can still only open half of the boxes, so their individual chance is still \(\frac{1}{2}\), but these probabilities are no longer independent of each other. So using this strategy, all of the prisoners would find their numbers \(31\%\) of the time and \(69\%\) of the time, fewer than 50 find their number. So the prisoners all win together, or majority loses together. If you understood till here, a question would have popped, "why do we assume that the number will always be on the loop that we started on?". I leave it as a brainstorming question to you. heee!
    Now, what if there is a sympathetic prison guard, who sneaks into the room before any of the prisoners go in, well they can guarantee success for the prisoners by swapping the contents of just two boxes, that's because there can be atmost one loop that is longer than 50 and you can break it in half, just by swapping the slip and creating two seperate loops that are each shorter than 50. But on the contrary, the probability of success does not change even if a malicious guard changes the boxes to ensure to form a loop longer than 50, why? think back about the random rearrangement of loops.
    For fun, let's think about what happens if you increase the number of prisoners?, so let's do some computations, ewww! \[ \begin{aligned} 100 \text{ prisoners}&: 1 - \left(\sum^{100}_{i=51} \frac{1}{i}\right) = 31.18\% \\ 1000 \text{ prisoners}&: 1 - \left(\sum^{1000}_{i=501} \frac{1}{i}\right) = 30.74\% \\ 1000000 \text{ prisoners}&: 1 - \left(\sum^{1000000}_{i=500001} \frac{1}{i}\right) = 30.685\% \end{aligned} \] So the probability of total success indeed approaches a limit. So, by generalizing \[ \begin{aligned} \text{Prob}(\text{success}) &= 1 - \text{Prob}(\text{failure}) \\ &= 1 - \int^{2n}_n \frac{1}{x} \ dx \\ &= 1 - \text{ln}(2) \\ &\approx 30.7\% \end{aligned} \] So the loop strategy is the solution to the riddle. This problem is my most favorite one, for its elegance and beauty in its solution!

  2. Assume that there exists a hotel with "infinite" rooms, with \(n \) guests, where \(n < \infty\), living in it. We will number each existing guests from \(1\) to \(n\). Now, there are infinitely many buses waiting outside the hotel, waiting to get accomodated and each bus has infinitely many new arrivals, ie., infinite buses with infinite individuals. Now, how will the hotel accomodate, infinite number of new arrivals from infinite number of buses. (Hint: Don't even think about putting them in the last room, since last room does not exist. I will provide a case of finite people. Assume, there is a bus with \(k\) number of guests, where \(k < \infty\). How, will we accomodate then newly arrived guests? we can move the existing guests by \(k + n\) rooms, which let us empty out the first \(k\) rooms, in which we can accomdate the newly arrived. For the original riddle, think about a number theoretic concept, that we know a very "less" about, heeee!).
    3. Click the toggle for solution! Before, actually getting into the original problem, let's think about an subset of the original issue. Imagine, there is "a" bus, with infinite number of new arrivals. How will the accommodate the new arrivals? We can't use the hint, that I had given, \(n + \infty\), really! Something does not look right. So, we need to think of a way, that will divide the infinite number of rooms into two infinite groups, ie., odd and even rooms. So we will move the existing guests, to room \(2n\). So all the existing guests, will move to all even numbered rooms, which will empty out all the odd numbered rooms, so we can accommodate the infinite number of newly arrived guests in the infinitely many odd numbered rooms, so room \(n\) is going to move to \(2n\)
    Now, I think you guys would have gotten a pretty good idea about the original question. We will now discuss that, By Euclid's Lemma, we know that there are infinitely many primes. So, we will use the prime numbers in the problem. So to accommodate, an infinite number of buses with an infinite number of people in each bus, we need to move everybody in the rooms, to the 1st prime no. to the power of their room no. So, mathematically, we can define the function \(N_R : \mathbb{Z} \to \mathbb{Z}\), with \(r \mapsto 2^r\), this is nothing fancy, \(N_R\) denotes the function "new rooms" and \(r\) denotes room no, heeee! So, \[ \begin{aligned} 1 &\mapsto 2^1 = 2 \\ &\vdots \\ 5 &\mapsto 2^5 = 32 \\ &\vdots \\ 8 &\mapsto 2^8 = 256 \\ &\vdots \end{aligned} \] So, now we took care of the current guests that were staying at the hotel by moving them into new rooms. What about the infinitely many people waiting in those infinitely many buses? Before, we get crazy with infinity, we will denote, the people waiting in those buses for a piece of mind. Let \(m, n\) denote the bus no., \(m\) and seat no., \(n\) for the infinitely many people in those buses. We will now move the passengers to the rooms, using the following function, \(R_B : \mathbb{Z} \to \mathbb{Z} \), with \((m, n) \mapsto p^n_{m+1}\), where \(p_{m+1}\), denotes the \((m+1)^{\text{th}}\) prime. So, \[ \begin{aligned} (1, 1) &\mapsto 3^1 = 3 \\ &\vdots \\ (1, 7) &\mapsto 3^7 = 2187 \\ &\vdots \\ (5, 4) &\mapsto 13^4 = 28561 \\ &\vdots \end{aligned} \] So, this is the solution. It is not so hard to prove it mathematically rigorous.
    For fun, you can try that if there are infinitely many ships, with infinitely many buses, with infinitely many people. How will you accommodate all those passengers?

  3. 10 individuals are placed in a sigle-file line faced forward in size-order, so that each of them can see everyone lined up ahead of them. They will not be able to look behind or step out of the line. Each of them will either have a black, or a white hat (denoted as denoted as \(B\) and \(W\)) on their head, assigned randomly and we dont know how many of each color there are, ie., \(\# (B) = \# (W)\) or \(\# (B) \ne \# (W)\). After assigning, each of them must guess the color of the hat, that is placed on their head. Starting with the person in the back and moving up the line. They are not allowed to speak or signal in any other manner, other than telling the color "black" or "white", obviously!. Atleast, 9 of the 10 people should provide the correct color. Provide a strategy that will let them to win the game.
    4. Click the toggle for solution! Before, thinking about a strategy, let's number each individuals from P10 - P1, where P10 is the tallest person, located back of the line and P1 is the shortest person, located front of the line. The key is the the person at the back of the line, who can see everyone else's hats can use the words "black" or "white", to communicate some coded information. So, we need to think about a meaning that can be assigned to those words that will allow everyone else to deduce their hat colors! It cannot be the total number of black or white hats, since there are more than two possible values. But "what" does have two possible values, the \(\textbf{parity}\)! So the solution is to agree that whoever goes first will, for example say "black", if he sees an odd number of black hats and "white" if he sees an even number of black hats. \[W \hspace{2ex} B \hspace{2ex} B \hspace{2ex} B \hspace{2ex} B \hspace{2ex} W \hspace{2ex} W \hspace{2ex} W \hspace{2ex} W \hspace{2ex} W\] But, what if this is a possible arrangement, \[W \hspace{2ex} W \hspace{2ex} B \hspace{2ex} B \hspace{2ex} W \hspace{2ex} W \hspace{2ex} W \hspace{2ex} W \hspace{2ex} W \hspace{2ex} B\] The tallest captive at the atmost left, sees three black hats in front of him. So he says "black", telling everyone else that he sees an odd number of black hats. He get's his own hat color wrong but that's fine, since they are collectively allowed to have one wrong answer. P9 also sees an odd number of black hats, so he knows that his is white, so answers correctly, P8 sees even number of black hats, so he knows that his must be one of the black hats that the other two individuals saw, so he answers correctly ans so on. As for P1, if P2 saw odd number of black hats, that can only mean one thing! You wil find that this strategy works for any possible arrangment of the hats. P10 has a probability of 50\% of providing the right answers but the parity information he conveys allows everyone else to guess theirs with absolute certainty, each begins by expecting to see an odd or even number of hats of the specified color. If what they count does not match, that means their own hat is the color, and everytime this happens the next person in line will switch the parity they expect to see.

    For fun, try to provide a rigorous mathematical proof for the logic, I have provided above. I will try and post it!