Brainteasers from Interviews - Part 2

A computer replies with "damaged" or "undamaged" to a query on the status of another computer. Our algorithm for discovering an undamaged computer in the room is based on the following observation: Assuming that there is a linked list of computers where each computer except the last is queried on the status of its successor in the list, if the replies to all queries are ``undamaged" and if there is at least one undamaged computer in the list, then the last computer in the list is definitely undamaged! Our algorithm constructs such a linked list as detailed below.

Start with an empty list. Repeatedly affix one of the remaining computers to the end of the list. If the resulting list has at least two computers and if the penultimate computer replies with "damaged" to the query on the status of the last computer in the list, then remove both of these computers from the list and discard them from the room forever. At least one of the two computers discarded is damaged, so undamaged computers in the room remain in the majority throughout the process of building the linked list. The linked list must be non-empty after all computers have been processed, and there must be at least one undamaged computer in that list. Then, the last computer in the list must be undamaged. The total number of queries is exactly \(n-1\).

No! Each of the three piles at the beginning has an odd size. Hence, the first operation must be (a), that is, we must merge two existing piles together, resulting in two piles with possible sizes \(\{51, 54\}\), \(\{5, 100\}\), or \(\{49, 56\}\). Hence, after the first operation, we end up with an even-sized pile and an odd-sized pile.

Denote by \(d\) the greatest common divisor of these two pile sizes. In particular, \(d = 3\) if the piles are \(\{51, 54\}\); \(d = 5\) if the piles are \(\{5, 100\}\); and \(d = 7\) if the piles are \(\{49, 56\}\).

Note that, since \(d\) is odd and greater than \(1\), no matter what sequence of operations is carried out (merging two existing piles or dividing an even--sized pile into two equal piles), the size of every pile size will continue to be a multiple of \(d\). Since \(d > 1\), we can never reach a configuration where all piles are of size \(1\).

In order to minimize the maximum distance to a coffee shop, the Coffee Company should place the seven coffee shops at the midpoints of the sides and at the center of the regular hexagon inscribed in the perfect disk of radius \(1\)km, as indicated in the figure below. This way, the maximum distance a person anywhere on campus has to walk to find a coffee shop is exactly \(0.5\)km.

Why is \(0.5\)km optimal?

Suppose that, on the contrary, the Coffee Company could place seven coffee shops on campus so that the the maximum distance from anywhere on campus to a coffee shop would be \(r < 0.5\)km. Then, the seven disks of radius \(r\), centered at those coffee shops, would cover the entire campus, that is, the entire disk of radius of \(1\)km.

Let us prove that a disk of radius \(r\) (\(r< 1\)) can cover at most \(2\sin^{-1}{\left(r\right)}\) of the circumference of the disk of radius \(1\). Let us denote by \(A\) and \(B\) the instersections of the two disks. Then \(AB\leq 2r\). If \(O\) Is the center of the big disk of radius \(1\) and \(M\) the midpoint of \(AB\), then we have \[ AM=\sin \angle AOM.\] The arc \(AB\) has the length equal to \(\angle AOB\). This length satisfies \[\angle AOB = 2\angle AOM=2\sin^{-1}(AM)\leq 2\sin^{-1}\left(r\right).\]

Then, six disks of radius \(r\) cover at most \(6 \cdot 2\sin^{-1}{\left(r\right)} = 12 \sin^{-1}{\left(r\right)}\) of the circumference of the disk of radius \(1\). Note that, since \(r < 0.5\), it follows that \(\sin^{-1}{\left(r\right)} < \frac{\pi}{6}\) and therefore \[ 12 \cdot \frac{\pi}{6} ~=~ 2 \pi. \] Thus, six of the disks of radius \(r\) cannot cover the entire circumference of the unit circle, This means that all of the seven disks of radius \(r\) must touch the circumference of the disk of radius \(1\). Since \(r < 0.5\), none of those disks would cover the center the disk of radius \(1\); in other words, a person at the center of the campus would have to walk more than \(0.5\)km to the closest coffee shop, which is a contradiction.

Let \begin{equation} \mathcal{I} ~=~ \int_{0}^{\frac{\pi}{2}} \ln{(\sin{x})} \,dx. \quad\quad\quad\quad\quad (1) \end{equation} We will use the substitution \(u = \frac{\pi}{2} - x\). Then, \(x = 0\) corresponds to \(u = \frac{\pi}{2}\), \(x = \frac{\pi}{2}\) corresponds to \(u = 0\), \(x = \frac{\pi}{2} - u\), and therefore \(dx = -du\). Thus, \begin{eqnarray} \mathcal{I} &=& \int_{0}^{\frac{\pi}{2}} \ln{(\sin{(x)})}\, dx \nonumber \\ &=& \int_{\frac{\pi}{2}}^{0} \ln{(\cos{(u)})}\, (-du) \nonumber \\ &=& \int_{0}^{\frac{\pi}{2}}\ln{(\cos{(u)})}\, du \nonumber \\ &=& \int_{0}^{\frac{\pi}{2}}\ln{(\cos{(x)})}\, dx, \quad\quad\quad\quad\quad (2) \end{eqnarray} where for the last equality we changed the integration variable from \(u\) to \(x\).

By adding (1) and (2), we obtain that \begin{eqnarray} 2 \mathcal{I} &=& \int_{0}^{\frac{\pi}{2}} \ln{(\sin{(x)})} + \ln{(\cos{(x)})}\,dx \nonumber \\ &=& \int_{0}^{\frac{\pi}{2}} \ln{\left(\sin{(x)}\cos{(x)}\right)}\, dx. \quad\quad\quad\quad\quad (3) \end{eqnarray} Recall that \(\sin(2x)=2\sin(x)\cos(x)\) and write (3) as \begin{eqnarray} 2 \mathcal{I} &=& \int_{0}^{\frac{\pi}{2}} \ln{\left(\frac{1}{2}\sin{(2x)}\right)}\, dx \nonumber \\ &=& \int_{0}^{\frac{\pi}{2}} \ln{\left(\frac{1}{2}\right)}\, dx ~+~ \int_{0}^{\frac{\pi}{2}} \ln{(\sin(2x))}\, dx \nonumber \\ &=& -\frac{\pi}{2} \ln{2} ~+~ \int_{0}^{\frac{\pi}{2}} \ln{(\sin(2x))}\, dx, \quad\quad\quad\quad\quad (4) \end{eqnarray} since \(\ln{\left(\frac{1}{2}\right)} = - \ln{2}\).

By using the substitution \(w = 2x\), we find that \begin{eqnarray} & & \int_{0}^{\frac{\pi}{2}} \ln{(\sin(2x))}\, dx \nonumber \\ &=& \frac{1}{2} \int_0^{\pi} \ln{(\sin(w))}\, dw \nonumber \\ &=& \frac{1}{2} \int_0^{\frac{\pi}{2}} \ln{(\sin(w))}\, dw ~+~ \frac{1}{2} \int_{\frac{\pi}{2}}^{\pi} \ln{(\sin(w))}\, dw \nonumber \\ &=& \frac{\mathcal{I}}{2} ~+~ \frac{1}{2} \int_{\frac{\pi}{2}}^{\pi} \ln{(\sin(w))}\, dw \quad\quad\quad\quad\quad (5) \end{eqnarray} Furthermore, by using the substitution \(u = \pi - w\), we obtain that \begin{eqnarray} & & \int_{\frac{\pi}{2}}^{\pi} \ln{(\sin(w))}\, dw \nonumber \\ &=& \int_{\frac{\pi}{2}}^0 \ln{(\sin(\pi-u))}\, (-du) \nonumber \\ &=& \int_0^{\frac{\pi}{2}} \ln{(\sin(u))}\, du \nonumber \\ &=& \mathcal{I}, \quad\quad\quad\quad\quad (6) \end{eqnarray} where we used the fact that \(\sin(\pi-u) = \sin(u)\).

From (5) and (6), it follows that \begin{equation} \int_{0}^{\frac{\pi}{2}} \ln{(\sin(2x))}\, dx ~=~ \frac{\mathcal{I}}{2} ~+~ \frac{\mathcal{I}}{2} ~=~ \mathcal{I}, \quad\quad\quad\quad\quad (7) \end{equation} and, from (4) and (7), we conclude that \[ 2 \mathcal{I} ~=~ -\frac{\pi}{2} \ln{2} ~+~ \mathcal{I}. \] Thus, \(\mathcal{I} = -\frac{\pi}{2} \ln{2}\) and therefore \[ \int_{0}^{\frac{\pi}{2}} \ln{(\sin{x})} \,dx ~=~ -\frac{\pi}{2} \ln{2}. \]

The triangle on which the bug moves is a complete graph of size \(3\). Denote by \(E = \left( e_{ij} \right)_{1 \le i,j \le 3}\) the \(3 \times 3\) incidence matrix of this graph. The entries of the matrix \(E\) are \(0\) or \(1\). The entry \(e_{ij}\) is \(1\) if there is an edge between the vertices \(i\) and \(j\). Re--label the vertices \(A\), \(B\), and \(C\) of the triangle to \(1\), \(2\), and \(3\). The incidence matrix is \begin{eqnarray*} E&=&\left[\begin{array}{ccc}0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\end{array}\right]. \end{eqnarray*}

We will use the following result which was also used in Question 2 from the section Linear Algebra of the book Challenging Brainteasers for Interviews:

If \(E\) is an incidence matrix of a graph, then \(E^k(i,j)\) is the total number of paths of length \(k\) from the vertex \(i\) to the vertex \(j\).

Thus, the number of paths of length \(8\) starting at \(A\) and ending back at \(A\) is equal to the entry \((1,1)\) of the matrix \(E^8\).

To calculate \(E^8\), note that, since the matrix \(E\) is symmetric, it has the diagonal form \begin{equation} E ~=~ Q D Q^t \quad\quad\quad\quad\quad (8) \end{equation} where \(Q\) is the orthogonal matrix whose columns are the eigenvectors of the matrix \(E\), and \(D\) is a diagonal matrix whose diagonal entries are the eigenvalues of \(E\). Then, \begin{equation} E^8 ~=~ Q D^8 Q^t. \quad\quad\quad\quad\quad (9) \end{equation}

We now compute the matrices \(D\) and \(Q\). The characteristic polynomial of the matrix \(E\) is \begin{eqnarray*} P_E(t) &=& \mbox{det}(t I - E) ~=~ \mbox{det} \left[ \begin{array}{ccc} t & -1 & -1 \\ -1 & t & -1 \\ -1 & -1 & t \end{array} \right] \\ &=& t^3 - 2 - 3t ~=~ (t-2)(t+1)^2. \end{eqnarray*} The roots of \(P_E(t)\) are \(2\), with multiplicity \(1\) and \(-1\), with multiplicity \(2\). Since the eigenvalues of a matrix are the roots of its characteristic polynomial, it follows that the eigenvalues of the matrix \(E\) are \(\lambda_1=2\), \(\lambda_2 = \lambda_3=-1\). The corresponding eigenvectors are \[ v_1 = \left[ \begin{array}{c} \frac1{\sqrt{3}} \\ \frac1{\sqrt{3}} \\ \frac1{\sqrt{3}} \end{array} \right];~~ v_2 = \left[ \begin{array}{c} \frac1{\sqrt{2}} \\ -\frac1{\sqrt{2}} \\ 0 \end{array} \right];~~ v_3 = \left[ \begin{array}{c} \frac1{\sqrt{6}} \\ \frac1{\sqrt{6}} \\ -\frac2{\sqrt{6}} \end{array} \right]. \] Thus, the matrices \(Q\) and \(D\) are \[ Q = \left[ \begin{array}{ccc} \frac1{\sqrt{3}} & \frac1{\sqrt{2}} & \frac1{\sqrt{6}} \\ \frac1{\sqrt{3}} & -\frac1{\sqrt{2}} & \frac1{\sqrt{6}}\\ \frac1{\sqrt{3}} & 0 & -\frac2{\sqrt{6}} \end{array} \right];~~ D = \left[ \begin{array}{ccc} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -1 \end{array} \right]. \] Then, from (9), we obtain that \[ E^8 ~=~ Q~ \left[ \begin{array}{ccc} 2^8 & 0 & 0 \\ 0 & (-1)^8 & 0 \\ 0 & 0 & (-1)^8 \end{array} \right] ~Q^t. \] By direct computation, we find that \(E^8(1,1) = 86\) and therefore conclude that there are \(86\) paths of length \(8\) that start at the vertex \(A\) and end back at \(A\).