The Nation Has Problems: Vol. 8

February 13, 2012 GreekHouse 12 Comments

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.

Double each entry in a single row.
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”

So for #1,

Spoiler	Select Show
the \(\text{score}= s = 3x +5y\) where \(x,y>=0, \in \Delta \), where \(\Delta =\text{non-negative integers}\) So then we have the set \( \theta = {3x_i; x_0=0, x_1=1,\dotso x=\infty} \) and the corresponding set \( \gamma = {5y_i: y_0=0, y_1=1, \dotso y=\infty}\). Then we have the set of possible scores \(\Sigma = \theta \cap \gamma \). So if we then take the complement \(\Delta - \Sigma\) that should be all the scores that are not possible. I think. *If nothing else, I got my LaTeX to work.

Spoiler

Select Show

Spoiler: Problem 1	Select Show
Scoring anything 0 mod 3 is easy (lots of 3-point touchgoalruns) Scoring anything 1 mod 3 is possible for any number >= 10 (two 5-pointers and the correct number of 3-pointers) Scoring anything 2 mod 3 is possible for any number >= 5 (one 5-pointer and the correct number of 3-pointers) So the highest number that can't be scored is 7, (which is the largest number less than 10 that = 1 mod 3) *Look at me, using modular arithmetic!

Spoiler: Problem 1

Select Show

sean says:

February 13, 2012 at 9:58 am

Spoiler Select Show

*Look at me, using modular arithmetic!

But not LaTeX! For shame.
1. Daneekas Ghost says:
  
  February 13, 2012 at 7:39 pm
  
  I'm going to need some kind of tutorial for that.
  1. sean says:
    
    February 13, 2012 at 8:17 pm
    
    LaTeX Wikibook
  2. sean says:
    
    February 14, 2012 at 12:10 pm
    
    I just noticed this; you can right-click any MathJax equation and view the source for it.

Spoiler	Select Show
*Look at me, using modular arithmetic! But not LaTeX! For shame.

Spoiler: Problem 2 thoughts	Select Show
It seems like the least common multiple of all of the numbers within a given column must be greater than zero. We must reduce an entire column to zero at once, otherwise when doubling, the rows that have a zero in them will remain there. Once step two happens, it will become negative.

Spoiler: Problem 2	Select Show
I think that any matrix that contains all non-zero entries can be reduced in that manner to all zeroes. You can reduce the problem to the following: Is there a way to make any two numbers in the same column equivalent by those operations? Because if you can, then you can treat those two numbers and a third number with the same method and then those three numbers plus a fourth, etc. etc. until the entire column is filled with one number. Then you can subtract 1 that number of times and make that column zero. That won't affect the other columns except to increase the numbers (with all the doublings), but the method should still apply to the other columns. So, if x and y are in the same column and x>y, there exists n>0 such that (2^n)y≥x and (2^[n-1])y<x. (If (2^n)y=x, then you're done, don't read the rest of this) so the first operation is to multiply y by 2 n times so now the two numbers in the column are (2^n)y and x. Now I want to get these to a point where the larger number is the double of the smaller one, so I have to subtract some number from both of them to get to that point. Call that number D. (2^n)y-D = 2(x-D), so D = 2x-(2^n)y So if we subtract 2x-(2^n)y from both of the numbers in the column we get: (2^n)y-D = (2^n)y-2x+(2^n)y = (2^[n+1])y-2x x-D = x-2x+(2^n)y = (2^n)y-x, which, when multiplied by 2 equals the result of the top equation. So any pair of non-zero integers in the same column can be turned into equivalent integers by this method, and by applying this to all the integers in each column, one can reduce it to the all zero matrix desired.

Spoiler: Problem 2

Select Show

Translating part of it...

Spoiler	Select Show
So, if x and y are in the same column and \(x \gt y\), there exists \(n \gt 0\) such that \((2^n)y \ge x\) and \((2^{n-1})y \lt x\). (If \((2^n)y=x\), then you're done, don't read the rest of this) so the first operation is to multiply \(y\) by \(2 n\) times so now the two numbers in the column are \((2^n)y\) and \(x\). Now I want to get these to a point where the larger number is the double of the smaller one, so I have to subtract some number from both of them to get to that point. Call that number \(D\). $$ (2^n)y-D = 2(x-D), so D = 2x-(2^n)y $$ So if we subtract \( 2x-(2^n)y \) from both of the numbers in the column we get: $$ (2^n)y-D = (2^n)y-2x+(2^n)y = (2^{n+1})y-2x $$ \( x-D = x-2x+(2^n)y = (2^n)y-x \) which, when multiplied by 2 equals the result of the top equation. So any pair of non-zero integers in the same column can be turned into equivalent integers by this method, and by applying this to all the integers in each column, one can reduce it to the all zero matrix desired.

Spoiler

Select Show

GreekHouse says:

February 15, 2012 at 3:02 pm

This seems right.

Sorry, I totally forgot this post went up on Monday.

brianS says:

February 13, 2012 at 7:33 pm

I haven't even thought about these, but I wanted to note that the mathjax plugin rocks.

Spoiler	Select Show
With capital letters representing digits base ten, if YX is a possible score, than so is ZX for Z>=Y, because YX + 2(Z-Y)(5-pointer) = ZX. Just going up: 0 possible (0x3 + 0x5) 1 impossible 2 impossible 3 possible (1x3 + 0x5) 4 impossible 5 possible (0x3 + 1x5) 6 possible (2x3 + 0x5) 7 impossible 8 possible (1x3 + 1x5) 9 possible (3x3 + 0x5) 10 possible (0x3 + 2x5) Actually, every number after this is possible just by adding a multiple of 3 to one of 8, 9, or 10. Therefore 7 is the highest score that is not possible.

Spoiler

Select Show

Comments are closed.

WGOM

The Nation Has Problems: Vol. 8

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

Remodeled basement. Same half-baked taste.