The Nation Has Problems: Vol. 8

About Last Month

Beyond the fold--solutions to the hat problems from last week and a problem I once got duringg a job interview!

1. Two players are each given either a red hat or a blue hat. They can each tell what color hat the other person is wearing, but don't know what color they are wearing. Before they get their hats, they are allowed to discuss a strategy, but may not communicate after they receive their hats. They are also required to guess simultaneously, so they can't infer anything from the other person's guess. Show that it is possible for them to develop a strategy such that at least one player is always right.

This is a nifty problem with a very simple solution. Player one looks at player two's hat and guesses as though their hats are the same color. Player two looks at player one's hat and guesses as though they are wearing different colored hats. If their hats are the same color, player 1 is correct. If their hats are different colors, player 2 guesses correctly.

2. Now \(n\) players are sitting in a circle and each is given a hat. Given the same assumptions, if there are \(k\) differently possible colors of hats, show that it is possible for the players to come up with a strategy such that at least \(\text{floor}(n/k)\) of them are right. The floor function is the smallest integer less than or equal to that number. For instance, \(\text{floor}(7/3)=2\), \(\text{floor}(5)=5\), and \(\text{floor}(17.1)=17\).

This is one of the problems where treating numbers as colors makes things easier. Note that in the first case, we came up with 2 different situations so that at least one of them was correct. In this case, we want to come up with \(k\) different situations so that at least one of them is correct and we'll be finished. First, let's call the colors \(0,1,2,\ldots,k-1\) and let \(S\) be the sum of all colors of all the hats. Then, the player in the \(i\)th position will guess as if \(S\equiv i\pmod k\). Since there are at least \(\text{floor}(n/k)\) players sitting in a position that's equivalent to \(i\pmod k\) for \(i=0,1,2\ldots, k-1\) for each \(i\) and at least one of these cases is correct, all of those players will guess correctly.

The problems

Problem 1 is a nice simple discrete math problem.

For problem 2, I was once given this problem in a job interview and given about 30 minutes to solve it (I did). It seems intimidating at first, but trying some simple examples might give you a good idea of when this is possible.

1. In a game of footsketball, you can score a 3-pointer or a 5-pointer. It is easy to see that you can score 3,5,8, or 10 points and also easy to see that you can't score 2 or 4 points. What is the largest number of points that cannot be scored in footsketball? Bonus: Show how to always score more than that number.

2. You're given an \(n\times m\) matrix full of nonnegative integers. The goal of this problem is to "reduce" the matrix to a matrix of all zeros using the following two operations.

  1. Double each entry in a single row.
  2. Subtract 1 from each entry in a single column.

Here's an example. Let's start with the following matrix:

$$\begin{bmatrix} 1 & 1 & 3 \\ 4 & 4 & 12 \end{bmatrix}$$

Now we'll use operation #1 twice on the first row to get

$$\begin{bmatrix} 1 & 1 & 3 \\ 4 & 4 & 12 \end{bmatrix} \rightarrow\begin{bmatrix} 2 & 2 & 6 \\ 4 & 4 & 12 \end{bmatrix} \rightarrow\begin{bmatrix} 4 & 4 & 12 \\ 4 & 4 & 12 \end{bmatrix} $$

Now we'll use operation #2 on the first column 4 times

$$\begin{bmatrix} 4 & 4 & 12 \\ 4 & 4 & 12 \end{bmatrix} \rightarrow\begin{bmatrix} 3 & 4 & 12 \\ 3 & 4 & 12 \end{bmatrix} \rightarrow\begin{bmatrix} 2 & 4 & 12 \\ 2 & 4 & 12 \end{bmatrix} \rightarrow\begin{bmatrix} 1 & 4 & 12 \\ 1 & 4 & 12 \end{bmatrix} \rightarrow\begin{bmatrix} 0 & 4 & 12 \\ 0 & 4 & 12 \end{bmatrix} $$

Now likewise, we apply operation #2 to the second column 4 times and to the last column 12 times and we are finished.

So in this previous example, it is possible to get the all zeros matrix. And hey! It only took 22 operations to do it (For bonus points, convince yourself this is best possible for this matrix). However, this isn't possible for every matrix. Characterize all matrices for which this is possible.

P.S. Thanks to Sean for adding LaTeX support for this site. That made this problem a lot easier to write up!

12 thoughts on “The Nation Has Problems: Vol. 8”

  1. So for #1,

    Spoiler SelectShow
  2. Spoiler: Problem 1 SelectShow
  3. Spoiler: Problem 2 thoughts SelectShow
  4. Spoiler: Problem 2 SelectShow
    1. Translating part of it...

      Spoiler SelectShow
  5. #1

    Spoiler SelectShow

Comments are closed.