Brainteasers from Interviews - Part 1

While Bob has fruits in all three sacks, he will have to give three fruits at each checkpoint. The optimal approach for Bob is to try to empty one bag as quickly as possible, so he will only have to give two fruits from that point on, then focus on emptying a second bag, after which he would only have to give one fruit at each checkpoint.

In other words, when passing through the first \(10\) checkpoints, Bob will give three fruits at each checkpoint from the same bag until that bag is empty. He is now left with two bags with \(30\) fruits each. When passing through the next \(15\) checkpoints, Bob will give two fruits at each checkpoint from the same bag until that bag is empty. He now has \(30\) fruits left, all of them in one bag. Bob has to go through \(5\) more checkpoints and will give one fruit at each of those checkpoints.

Bob will be left with \(25\) fruits, all of them in one bag.

The player in the center of the room will only give three kinds of requests to the players on the circle; we call them \(R_1\), \(R_2\), and \(R_3\).

These three requests are defined below and we also specify the sequence in which these three requests should be given:

• The request \(R_1\) asks the players in the chairs \(1\) and \(3\) to change the colors of their hats.
• The request \(R_2\) asks the players in the chairs \(1\) and \(2\) to change the colors of their hats.
• The request \(R_3\) asks only the player in the chair \(1\) to change his/her hat.

Denote the white hats by \(1\) and black hats by \(-1\). Note that the requests \(R_1\) and \(R_2\) preserve the product of all the numbers, while the request \(R_3\) changes the product of the numbers. There are \(2^4\) possible configurations of hats. Half of them have the product equal to \(1\) and half of them have the product equal to \(-1\). Denote by \(S_+\) the set of all possible configurations that have the product equal to \(1\) and by \(S_-\) the set of all configurations that have the product equal to \(-1\).

We will now define the sequence \(\Sigma_+\) of requests whose terms are \(R_1\) and \(R_2\) only. During the requests in \(\Sigma_+\), the configuration of hats will not move from \(S_+\) to \(S_-\) (or vice versa). The sequence \(\Sigma_+\) will be chosen in such a way to guarantee that at some point all hats become of the same color, provided that the original configuration belongs to \(S_+\). If during the application of the sequence \(\Sigma_+\) the hats never become of the same color, then we are sure that the original configuration is \(S_-\). In that case, the player in the center of the room gives the request \(R_3\) and repeats the sequence \(\Sigma_+\). This repeat application of \(\Sigma_+\) will guarantee that at some point the hats all become of the same color. Thus, once we construct \(\Sigma_+\), the desired sequence of operations will be \[\left(\Sigma_+, R_3, \Sigma_+\right).\]

In making \(\Sigma_+\), our goal is to arrange the requests \(R_1\) and \(R_2\) in such a way that if the configuration of hats is in \(S_+\), then at some point all the hats become of the same color. We will thus only work with configurations in \(S_+\). It suffices to restrict our attention only to the subset \(S_+^2\) of those configurations that have two terms equal to \(1\) and two terms equal to \(-1\). Configurations in \(S_+\) that are not in \(S_+^2\) are trivial: the hats are all of the same color and the game is over. We partition the set \(S_+^2\) in two subsets \(A\) and \(B\). The subset \(A\) consists of those configurations in which the signs alternate: \[ A = \left\{ (1, -1, 1, -1), (-1,1,-1,1)\right\}. \] The set \(B\) consists of the remaining four configurations. \begin{eqnarray*} B&=&\left\{(1,1,-1,-1), (1,-1,-1,1),\right.\\ &&\left. (-1,-1,1,1), (-1,1,1,-1)\right\}. \end{eqnarray*} Let us now analyze the request \(R_1\). The request \(R_1\) takes a configuration from \(B\) into a configuration from \(B\). However, \(R_1\) will take a configuration from \(A\) into the one in which all hats are of the same color.

The first term of the sequence \(\Sigma_+\) will be \(R_1\). If the configuration was in \(A\), then the game is over after this request \(R_1\). If the game is not over yet, then we are sure that the configuration is in \(B\).

Assume now that the request \(R_2\) is given and that the configuration of hats is in \(B\). Since the set \(B\) has only \(4\) elements, it is easy to verify directly that \(R_2\) applied to any element in \(B\) will either result in all hats being of the same color, or in all hats falling into a configuration that belongs to \(A\).

Therefore, the sequence \(\Sigma_+\) defined as \[ \Sigma_+ = \left(R_1, R_2, R_1\right) \] guarantees that at some point all hats are of the same color, provided that initially an even number of hats is black.

Thus, the sequence of requests that, for each initial configuration, guarantees that the hats will be of the same color at some point is

Let \(E_n\) be the expected number of rolls until you roll the same number \(n\) times in a row. We need to find \(E_6\). Assume that you have just rolled the same number \(n-1\) times in a row, which took \(E_{n-1}\) rolls on average. Then, one of the following two outcomes will happen:

• with probability \(\frac{1}{6}\), you roll the same number again on the next roll; in this case, you end up rolling the same number \(n\) times in a row and it took \(E_{n-1} + 1\) rolls to obtain this outcome;
• with probability \(\frac{5}{6}\), you roll a different number on the next roll; in this case, you already started on your way to roll the same number \(n\) times in a row and you will need \(E_{n-1} + E_{n}\) to achieve this.

Hence, we obtain the following recurrence: \[ E_n ~=~ \frac{1}{6}\left( E_{n-1} + 1 \right) + \frac{5}{6}\left(E_{n-1} + E_{n}\right), \] which is equivalent to \begin{equation} E_n ~=~ 6E_{n-1} + 1, ~~\forall~ n > 1. \quad\quad\quad\quad\quad (1) \end{equation} By iterating (1), we obtain that \begin{equation} E_n ~=~ 1 + 6 + \ldots + 6^{n-2} + 6^{n-1}E_{1}. \quad\quad\quad\quad\quad(2) \end{equation} Since \(E_{1} = 1\), we obtain from (2) that \[ E_n = \sum_{i=0}^{n-1} 6^i = \frac{6^n - 1}{5}. \] Thus, for \(n=6\), we find that \(E_6 = 9331\).

Since \(L < D\), the needle can intersect at most one horizontal and at most one vertical line. Denote by \(X\) the distance from the midpoint of the needle to the closest horizontal line. (The probability that the needle will land on the sheet of paper so that its midpoint is exactly halfway between two consecutive horizontal lines is zero, so the horizontal line closest to the midpoint of the needle is well-defined.) Denote by \(Y\) the distance from the midpoint of the needle to the closest vertical line. Let \(\theta\) denote the angle between the vertical line through the midpoint of the needle and the line containing the needle itself, as in the figure below.

Note that the position of the needle is completely determined by the values of \(X\), \(Y\), and \(\theta\). The random variables \(X\), \(Y\), and \(\theta\) are independent; \(X\) and \(Y\) are uniformly distributed on \(\left(0, \frac{D}{2}\right)\), while \(\theta\) is uniformly distributed on \(\left(0, \frac{\pi}{2}\right)\). Denote by \(A\) the event that the needle crosses a horizontal line and by \(B\) the event that the needle crosses a vertical line.

Since the needle can intersect at most one horizontal and at most one vertical line, the expected number of lines crossed by the needle is precisely \[ \mathbb{P}\left(A\right) + \mathbb{P}\left(B\right) ~=~ 2\,\mathbb{P}\left(A\right). \] The last equality follows from \(\mathbb{P}\left(A\right) = \mathbb{P}\left(B\right)\), a fact easily established by rotating the sheet of paper by \(\pi/2\). Similarly, the probability that the needle crosses a line is precisely \[ \mathbb{P}\left(A\right) + \mathbb{P}\left(B\right) - \mathbb{P}\left(A\cap B\right) ~=~ 2\,\mathbb{P}\left(A\right) - \mathbb{P}\left(A\cap B\right). \]

Hence, we need to compute \(\mathbb{P}\left(A\right)\) and \(\mathbb{P}\left(A\cap B\right)\). Denote by \(d\) the distance from the midpoint of the needle to the point of intersection of the line containing the needle itself with the horizontal line (see figure).

Note that \(d = \frac{X}{\cos{\theta}}\). The event \(A\) occurs if and only if \(d < \frac{L}{2}\), that is, if and only if \(\frac{X}{\cos{\theta}} < \frac{L}{2}\). Similarly, the event \(B\) occurs if and only if \(\frac{Y}{\sin{\theta}} < \frac{L}{2}\).

Since \(X\) and \(\theta\) are independent, their joint density \(f_{X,\theta}\) is the product of marginal densities and, thus, satisfies \[f_{X,\theta}(u,v)=\frac{1}{D/2}\cdot\frac{1}{\pi/2}.\] By integrating the joint density over an appropriate region, we obtain that \begin{eqnarray*} \mathbb{P}\left(A\right) &=& \mathbb{P}\left(\frac{X}{\cos{\theta}} < \frac{L}{2}\right) = \mathbb{P}\left(X < \frac{L}{2}\cos{\theta}\right)\\ &=& \int_0^{\frac{\pi}{2}} \int_0^{\frac{L}{2}\cos{\theta}} \frac{1}{D/2}\cdot \frac{1}{\pi/2}\, dx\, d\theta\\ &=& \frac{4}{\pi D}\int_0^{\frac{\pi}{2}} \frac{L}{2}\cos{\theta}\, d\theta \\ &=& \frac{2L}{\pi D}\sin{\theta}\left|_{0}^{\pi/2} \right. \\ &=& \frac{2L}{\pi D}. \end{eqnarray*}

Similarly, since \(X\), \(Y\), and \(\theta\) are independent, their joint density is the product of marginal densities and, thus, is equal to \(\left(\frac{1}{D/2}\right)^2\cdot\frac{1}{\pi/2}\). Then, \begin{eqnarray*} & & \mathbb{P}\left(A\cap B\right) \\ &=& \mathbb{P}\left(\frac{X}{\cos{\theta}} < \frac{L}{2} \mbox{ and } \frac{Y}{\sin{\theta}} < \frac{L}{2}\right) \\ &=& \mathbb{P}\left(X < \frac{L}{2}\cos{\theta} \mbox{ and } Y < \frac{L}{2}\sin{\theta} \right)\\ &=& \int_0^{\frac{\pi}{2}} \int_0^{\frac{L}{2}\cos{\theta}}\int_0^{\frac{L}{2}\sin{\theta}}\left(\frac{1}{D/2}\right)^2 \cdot \frac{1}{\pi/2}\, dy\, dx\, d\theta. \end{eqnarray*} The last integral can be evaluated as follows: \begin{eqnarray*} \mathbb{P}\left(A\cap B\right) &=& \frac{8}{\pi D^2}\cdot\frac{L^2}{4}\int_0^{\frac{\pi}{2}} \sin{\theta}\cos{\theta}\, d\theta\\ &=& \frac{L^2}{\pi D^2}\int_0^{\frac{\pi}{2}} \sin{(2\theta)}\, d\theta \\ &=& \frac{L^2}{\pi D^2}\cdot \left(-\frac{1}{2}\cos{(2\theta)}\right)\left|_{0}^{\pi/2} \right. \\ &=& \frac{L^2}{\pi D^2}. \end{eqnarray*}

We conclude that the expected number of lines crossed by the needle is \[2\,\mathbb{P}\left(A\right) = \frac{4L}{\pi D},\] while the probability that the needle crosses a line is \[2\,\mathbb{P}\left(A\right) - \mathbb{P}\left(A\cap B\right) = \frac{4L}{\pi D} - \frac{L^2}{\pi D^2}.\]

First, we distribute the candies. Let \(c_i\) denote the number of candies the \(i\)th child gets, \(i \in \{1\), \(2\), \(3\), \(4\}\). Counting the ways to distribute \(7\) candies among \(4\) children, so that each child gets at least one candy, is then equivalent to counting positive integer solutions to equation \[c_1 + c_2 + c_3 + c_4 = 7.\] Any such solution, say \((c_1, c_2, c_3, c_4) = (1, 2, 3, 1)\) can be uniquely represented as a sequence \[\star \big| \star \star \big| \star \star \star \big| \star\] of \(7\) stars (representing candies) and \(3\) bars (separating the candy lots that \(4\) children receive). So, the number of positive integer solutions to equation \(c_1 + c_2 + c_3 + c_4 = 7\) is precisely the number of sequences of \(7\) stars and \(3\) bars, where bars are placed in between the stars, but not before the first or after the last star, and so that no place between two stars can be occupied by more than one bar (since each child gets at least one candy). Hence, one only needs to choose \(3\) out of the \(6\) places between the stars and place bars there. Thus, the number of ways to distribute \(7\) candies among \(4\) children, so that each child gets at least one candy, is \({6\choose 3}\).

Once we have distributed the candies, we need to distribute the stickers so that each child gets more stickers than candies. Let \(s_i\) denote the number of stickers the \(i\)th child gets, \(i = 1, 2, 3, 4\). Counting integer solutions to equation \(s_1 + s_2 + s_3 + s_4 = 14\) such that \(s_i > c_i\) is equivalent to counting positive integer solutions to equation \((s_1 - c_1) + (s_2 - c_2) + (s_3 - c_3) + (s_4 - c_4) = 14-7 = 7\). Thus, setting \(d_i = s_i - c_i\), we need to count positive integer solutions to equation \(d_1 + d_2 + d_3 + d_4 = 7\), which is precisely the counting problem we have already solved in the previous paragraph. Thus, (with candies already distributed among the children) the number of ways to distribute the stickers so that each child gets more stickers than candies is \({6\choose 3}\).

We conclude that the number of ways in which we can divide \(7\) candies and \(14\) stickers among \(4\) children, so that each child gets at least one candy and also gets more stickers than candies, is \[ {6\choose 3} ^2 ~=~ 400. \]