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. 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.
In general, I believe that the solution to this problem where you can score either \(a\) or \(b\) points is that the highest number you cannot get is \(GCD(a,b)-a-b\). In this case, that number is 7. It is pretty easy to convince yourself that you can't get seven. There are a number of ways to prove that you can get 8 or more points, but I'll use the technique of mathematical induction since it's an interesting method of proof that most people don't see unless they become math majors in college.
The idea behind induction is to show that we can do this for some small number (called the base case) and then show that if we can do it for \(n\), we can also do it for \(n+1\). In this case, our base case is \(n=8\) which we can easily do by scoring a 3-pointer and a 5-pointer. Now, suppose that we can score \(n\) points. If we scored a 5-pointer when scoring \(n\) points, then we can get \(n+1\) points by getting rid of that 5-pointer and scoring two 3-pointers instead. If we did not score a 5-pointer in the last case, then we scored at least 3 3-pointers (since \(n>7\)), so remove those from our score and replace them with 2 5-pointers for a net gain of one point.
Since we can always get from \(n\) points to \(n+1\) points, we can score any number of points bigger than 7.
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.
Characterize all matrices for which this is possible.
One of the things I like about this problem is the fact that it is seemingly complex and yet you can reduce it to simpler and simpler things and end up solving a fairly simple problem in the end.
First, let's note that if there is a 0 in a column and a non-zero entry in the same column, then it will be impossible to reduce that column to all zeros. Why? Once you get a zero somewhere, it is easy to check that you can never make that entry bigger than zero again. If it becomes negative, then you can never even make it back to zero again. So if you have a zero in some column and something bigger than zero in the same column, you're going to have to use operation #2 at some point to reduce the non-zero number to zero, making the zero entry negative and preventing you from ever getting a zero in that column again.
From here, we see that it must be necessary that our matrix contains columns that are either entirely zero or entirely non-zero. This is a necessary condition, so let's try to show it's also sufficient.
If you're able to somehow reduce a column to all zeros, note that neither operation will change that column from being all zeros (providing you don't use operation #2 on that column again). So we only need to work on reducing one column at a time. Further, note that if we get two entries in the same column to have the same value, then any time we want to use operation #1 on one of those rows, we can use it on the other and they'll still have the same value (same with if we want to use operation #2 on that column). Hence, it suffices to solve the problem for a simple \(2\times 1\) matrix. Let's assume the two entries are different $$\begin{bmatrix} a \\ b\end{bmatrix}.$$ Now, let's subtract 1 from that column until one of the numbers is 1. This gives $$\begin{bmatrix} \alpha \\ 1\end{bmatrix}.$$ Now, if we double the second row and subtract one from the column again, we get $$\begin{bmatrix} \alpha -1 \\ 1\end{bmatrix}.$$ So, we can repeat this two step process until both entries are 1 and then subtract 1 from the column and we're finished.
Note that this is slightly computationally more expensive than the way DG presented last week. Doing this to any sort of sizable matrix is going to blow up many of the entries and cause the problem to require many, many steps.
The problems
Let's do some good old fashioned number problems today.
1. Find the last three digits of \(2011^{2012}\).
2. Evaluate \(\sqrt{1 + \sqrt{ 1 + \sqrt{ 1 + \cdots } } } \)
I always hated proofs. I never learned to do them in high school so when college came around they kicked my butt. But the one kind of proof that I did understand was induction.
Problem 1.
Caught an error:
Problem 2
Edit: yep, this LaTex thing is going about as well as I expected.
I have to re-learn LaTeX every time there's one of these up.
I never learned. I set everything into equation editor in MS Word. PITA
Most of the time, you can prefix something with a backslash to get the right function and then use braces (that's { and }) for arguments. Also, you can right-click something, select 'Show Math As' and then 'TeX Commands'. That will open a window with the right TeX stuff you need.
hmmmmmm. my backslashes are disappearing.
Edit: let's try this.
(sqrt{1 + sqrt{ 1 + sqrt{ 1 + cdots } } } )
Further edit: I copied that directly from the page's source code up in Greek's text where it seems to have worked.
You need to enable LaTeX math mode first, using either $$ to set it off on its own line for \( for inline math. And then close it with $$ or \) respectively.
I did my correction before I saw this solution.
I did wait until I was about to leave work to post it though.
In answer to your last question, I think it is true as long as some divisibility criteria are satisfied. Namely, I think you need x and z to be relatively prime.