Brainteasers from Interviews - Part 3

Let \(A\) be the event that at the moment we stop the basket is empty. Since we must take apples out until all the green apples are out, the only way we would have to empty the entire basket in order to take all the green apples out is if the last apple in the basket is green.

Hence, we can now modify our random experiment in the following way: Denote the green apples by \(g_1\), \(g_2\), \(\dots\), \(g_M\) and the red apples by \(r_1\), \(r_2\), \(\dots\), \(r_N\). Instead of taking the apples out of the basket randomly one by one until all the apples left in the basket are red, we will take the apples out until no apple is left in the basket. The sample space \(\Omega\) for our experiment now becomes the set of all the permutations of the set \[ S ~=~ \left\{g_1, g_2, \dots, g_M, r_1, r_2,\dots, r_N\right\}. \] The size of \(\Omega\) is \((M+N)!\). The probability function \(\mathbb P\) assigns the value \(\frac{1}{(M+N)!}\) to each of the outcomes.

Note that \(A\) is the set of all permutations from \(\Omega\) whose last entry is from \(G=\left\{g_1\right.\), \(g_2\), \(\dots\), \(\left.g_M\right\}\). The number of permutations whose last entry is from \(G\) is \(M \cdot (M+N-1)!\), since there are \(M\) ways to choose the last entry and \((M+N-1)!\) ways to permute the remaining entries.

We conclude that the probability of the event \(A\) is \begin{equation} \mathbb P\left(A\right) ~=~ \frac{(M+N-1)!\cdot M}{(M+N)!}=\frac{M}{M+N}. \quad\quad\quad\quad\quad (1) \end{equation}

In retrospect, it would have been easier to derive (1) by noticing that, in the modified random experiment, the last ball in the basket is equally likely to be any of the balls in \(S\), hence, it is green with probability \(\frac{M}{M+N}\).

We will use the following notations: \begin{eqnarray*} \overrightarrow x &=& \left(x_1,\dots, x_9\right); \\ S\left(\overrightarrow x\right) &=& \sum_{i=1}^{9} \left|x_{i+1} - x_i\right|. \end{eqnarray*} Since the given sum does not change if the numbers are rotated around the circle, we can assume without any loss of generality that \(x_1=1\). Let \(1 < k \le 9\) such that \(x_k = 9\). Using the triangle inequality,\footnote{The triangle inequality states that \(|a| + |b| \ge |a+b|\) for any (real or complex) numbers \(a\) and \(b\). } we obtain that \begin{eqnarray*} S\left(\overrightarrow x\right) &=& \sum_{i=1}^{k-1} \left|x_{i+1} - x_i\right| + \sum_{i=k}^9 \left|x_{i+1} - x_i\right| \\ &\geq& \left|\sum_{i=1}^{k-1}\left(x_{i+1}-x_i\right)\right| + \left|\sum_{i=k}^9 \left(x_{i+1} - x_i\right)\right| \\ &=& \left|x_{k}-x_1\right| + \left|x_{10}-x_k\right| \\ &=& |9-1| + |1-9| \\ &=& 16. \end{eqnarray*} The minimal value of \(S\left(\overrightarrow x\right) = \sum_{i=1}^{9} \left|x_{i+1} - x_i\right|\) is \(16\), which is achieved if and only if \begin{eqnarray*} \sum_{i=1}^{k-1} \left|x_{i+1} - x_i\right| &=& \left|\sum_{i=1}^{k-1}\left(x_{i+1}-x_i\right)\right|; \\ \sum_{i=k}^9 \left|x_{i+1} - x_i\right| &=& \left|\sum_{i=k}^9 \left(x_{i+1} - x_i\right)\right|, \end{eqnarray*} which in turn happens if and only if the sequence \(\left(x_1=1\right.\), \(x_2\), \(\dots\), \(\left.x_{k} =9\right)\) is increasing and the sequence \(\left(x_k=9\right.\), \(x_{k+1}\), \(\dots\), \(\left.x_{10}=1\right)\) is decreasing.

Since \(x_1 = 1\), there is a total of \(8!\) arrangements of the numbers \(2\), \(3\), \(\dots\), \(9\) around the circle, all of them being equally likely. Let \(G\) be the set of all arrangements of \(x_1=1\), \(x_2\), \(\dots\), \(x_9\) around the circle that minimize the described sum. The probability that the sum \(\sum_{i=1}^{9} \left|x_{i+1} - x_i\right|\) is minimized is equal to \(\frac{|G|}{8!}\). For each \(k\in\{2\), \(3\), \(\dots\), \(9\}\), let \(G_k\subseteq G\) be the set of such arrangements with \(x_k=9\). Once the set of numbers \(S_{2,k-1}=\) \(\left\{x_2\right.\), \(\dots\), \(\left.x_{k-1}\right\}\) is fixed, the set \(S_{k+1,9}=\) \(\left\{x_{k+1}\right.\), \(\dots\), \(\left.x_9\right\}\) is also fixed. Moreover, the numbers \(x_2\), \(\dots\), \(x_{k-1}\) must form the unique permutation of \(S_{2,k-1}\) in which the numbers are in increasing order. Similarly, the numbers \(x_{k+1}\), \(\dots\), \(x_9\) must form the unique permutation of \(S_{k+1,9}\) in which the numbers are in decreasing order. Therefore, an arrangement in \(G_k\) is uniquely determined by the set \(S_{2,k-1}\).

We conclude that \(|G_k|\) is equal to the number of ways in which the elements of \(S_{2,k-1}\) can be chosen. The number of such choices is \(\binom 7{k-2}\). Therefore, \begin{eqnarray*} |G|&=&\sum_{k=2}^9\left|G_k\right|=\sum_{k=2}^9\binom{7}{k-2}\\ &=&\binom70+\binom71+\cdots+\binom77=2^7. \end{eqnarray*} Thus, the probability that the sum \(\sum_{i=1}^{9} \left|x_{i+1} - x_i\right|\) is minimized is equal to \[ \frac{|G|}{8!} ~=~ \frac{2^7}{8!} ~=~ \frac1{315}. \]

We need to calculate the probability of the event \(G\) that the selected ball is green. Denote by \(A\) the event that the selected ball was originally from container \(A\) and by \(A^C\) the event that the selected ball was originally from container \(B\). Note that \(\mathbb P\left( A \right) = \frac{1}{3}\) and \(\mathbb P\left( A^C \right) = \frac{2}{3}\), since \(2000\) balls were added from container \(A\) to the \(4000\) balls in container \(B\).

Conditioned on the event that the selected ball is from \(A\), the probability of the ball being green is \(\frac{1}{4}\), that is, \(\mathbb P\left( G | A \right) = \frac{1}{4}\). Conditioned on the event that the selected ball is from \(A^C\), the probability of the ball being green is \(\frac{3}{4}\), that is, \(\mathbb P\left( G | A^C \right) = \frac{3}{4}\).

We conclude that \begin{eqnarray*} \mathbb P\left(G\right) &=& \mathbb P\left( G | A \right) \, \mathbb P\left( A \right) ~+~ \mathbb P\left( G | A^C \right) \, \mathbb P\left( A^C \right) \\ &=& \frac{1}{4} \cdot \frac{1}{3} ~+~ \frac{3}{4} \cdot \frac{2}{3} \\ &=& \frac{7}{12}. \end{eqnarray*}

The correct answer to this problem is ``No, I cannot.'' We will build two probability spaces that satisfy the conditions of the problem, but have different probabilities of heads when conditioned on the described event.

Denote by \(E\) the event that \(A\) predicts \(T\) and \(B\) predicts \(H\), and by \(L_H\) the event that the coin lands heads. We will build two probability spaces \(\left(\Omega_1,\mathbb P_1\right)\) and \(\left(\Omega_2,\mathbb P_2\right)\), such that \[\mathbb P_1\left(\left. L_H\right|E\right)\neq \mathbb P_2\left(\left. L_H\right|E\right).\]

First, we consider the following sample space \[\Omega_1=\left\{HA_1B_1, TA_1B_1, TA_1B_0,TA_0B_0\right\},\] where the outcomes are sequences of three symbols with the following meanings:

• The first symbol is \(H\) or \(T\), representing whether the coin lands heads or tails;
• The second symbol is either \(A_1\) or \(A_0\); \(A_1\) implying that \(A\) makes the correct prediction, and \(A_0\) implying that \(A\) makes the wrong prediction;
• The third symbol is either \(B_1\) or \(B_0\), with meanings analogous to those of \(A_1\) and \(A_0\), respectively.

For example, an outcome \(TA_1B_0\) means that the coin lands tails, the scientist \(A\) makes the correct prediction, and the scientist \(B\) makes the wrong prediction.

The probability function \(\mathbb P_1\) is defined as \begin{eqnarray*} &\mathbb P_1(HA_1B_1)=0.5, &\mathbb P_1\left(TA_1B_1\right)=0.1, \\ &\;\mathbb P_1\left(TA_1B_0\right)=0.2,& \mathbb P_1\left(TA_0B_0\right)=0.2. \end{eqnarray*}

Note that, with \(\Omega_1\) as the sample space, we have \(E = \left\{TA_1B_0\right\}\) and \(L_H\cap E = \emptyset\), which implies that \[\mathbb P_1\left(\left.L_H\right|E\right)=0.\]

We now build another pair \(\left(\Omega_2,\mathbb P_2\right)\) of a sample space and a probability measure for which the conditional probability \(\mathbb P_2\left(\left.L_H\right|E\right)\) is equal to \(1\). The sample space \(\Omega_2\) is defined as \begin{eqnarray*} \Omega_2=\left\{ HA_1B_0, HA_0B_1, HA_0B_0, TA_1B_1 \right\}. \end{eqnarray*} The probability function \(\mathbb P_2\) is defined as \begin{eqnarray*} &\mathbb P_2\left(HA_1B_0\right)=0.3, & \mathbb P_2\left(HA_0B_1\right)=0.1, \\ &\mathbb P_2\left(HA_0B_0\right)=0.1, &\mathbb P_2\left(TA_1B_1\right)=0.5. \end{eqnarray*} The events \(E\) and \(L_H\cap E\), as subsets of \(\Omega_2\), contain a single outcome, \(HA_0B_1\). Thus, \[\mathbb P_2\left(\left.L_H\right|E\right)=1.\]

Denote by \(W_k\) the event that the \(k\)-th card is an Ace and that one more card is an Ace among the first \(k-1\) cards. Note that \(k \le 50\) since there must be at least two cards (Aces) left after the top \(50\) cards are drawn. We need to find \(1 \le k \le 50\) such that \(\mathbb P(W_k)\) is maximized. Let \(N_k\) be the number of ways in which the deck can be shuffled to have one Ace in the \(k\)-th position, one Ace in a position from the set \(\{1,2, \dots, k-1\}\), and two Aces in positions from the set \(\left\{k+1, \dots, 52\right\}\). Then, \begin{equation} \mathbb P\left(W_k\right) ~=~\frac{N_k}{52!}. \quad\quad\quad\quad\quad (2) \end{equation} Denote by \(M_k\) the number of ways in which we can choose the positions for four Aces. For each choice of positions for the four Aces, the Aces can be placed in those positions in \(4!\) ways, while the other cards can be placed in the remaining positions in \(48!\) ways. Therefore, \begin{equation} N_k ~=~ 4!\cdot 48!\cdot M_k. \quad\quad\quad\quad\quad (3) \end{equation}

To calculate \(M_k\), note that: the \(k\)-th position must be chosen; one position is in \(\{1\), \(2\), \(\dots\), \(k-1\}\) and can be chosen in \(k-1\) ways; the other two positions are in \(\{k+1\), \(k+2\), \(\dots\), \(52\}\) and can be chosen in \(\binom{52-k}2\) ways. Thus, \begin{eqnarray} M_k &=& (k-1) \cdot \binom{52-k}2 \nonumber \\ &=& \frac{(k-1)(52-k)(51-k)}{2}. \quad\quad\quad\quad\quad (4) \end{eqnarray} From (2), (3), and (4), it follows that the probability of winning, when choosing \(k\), is \begin{eqnarray*} \mathbb P\left(W_k\right) &=& \frac{4!\cdot 48!}{52!} \cdot \frac{(k-1)(52-k)(51-k)}{2} \\ &=& \frac{12(k-1)(52-k)(51-k)}{52\cdot 51\cdot 50\cdot 49}. \end{eqnarray*} The maximum value of \(\mathbb P\left(W_k\right)\) is obtained for the value of \(k\) that maximizes the function \begin{eqnarray*} f(k) &=& (k-1)(52-k)(51-k) \\ &=& (k-1)\cdot \left[51-(k-1)\right]\cdot \left[50-(k-1)\right]. \end{eqnarray*} Let \(z = k-1\), \(M=51\), and \[ g(z) ~=~ z(51-z)(50-z). \] Since \(f(k)=g(k-1)\), the maximum of \(f\) is attained at \(k_{\star}=z_{\star}+1\), where \(0 \le z_{\star} \le 49\) is the integer for which the function \(g\) is the largest; recall that \(1 \le k \le 50\). The derivative of \(g(z)\) is \[ g'(z) ~=~ 3z^2-2(2M-1)z+M(M-1) \] and the solutions of the equation \(g'(z)=0\) are \begin{eqnarray*} z_{1,2}&=&\frac{2M-1\pm\sqrt{M^2-M+1}}{3}. \end{eqnarray*} Since \((M-1)^2< M^2-M+1< M^2\), we find that \begin{eqnarray*} &&z_1 \in \left( \frac{M-1}3, \frac M3 \right) = \left(16.67,17\right),\\ &&z_2 \in \left( M-\frac23 , M-\frac13 \right) = \left(50.33,50.67\right). \end{eqnarray*} The quadratic function \(g'(z)\) is negative on the interval \((z_1,z_2)\) and positive everywhere else. This implies that \(g\) is increasing on \((-\infty,z_1)\), decreasing on \((z_1,z_2)\), and increasing on \((z_2,+\infty)\). Hence, the value \(0 \le z_{\star} \le 49\) where \(g\) attains its maximum is either \(\lfloor z_1\rfloor = 16\) or \(\lceil z_1\rceil = 17\). In other words, \(z_{\star}\in\{16,17\}\), which corresponds to \(k_{\star}\in\{17,18\}\). Since \(f(17) = 19040\) and \(f(18) = 19072\), we conclude that it is optimal to choose is \(k=18\).