About Last Month
I'm not sure if I should post the solutions to last month's problems in plain text or not. Since you have had a month to think about these problems, I will just go ahead and post the solutions in plain text, but I'll do it after the break.
The first problem from last month is actually more than just a toy problem, it has an important use in the world of cryptography! You guys did a great job of "thinking outside of the box" on this one and found ways to bend the rules in ways I wasn't anticipating. I wanted to keep to the spirit of the application of the problem though, which was why I was somewhat picky about what was allowed. The problem is actually inspired by the Diffie-Hellman key exchange, which is a way for two parties to exchange a private key without anybody else figuring it out. The simplest solution to this problem is:
- Alice padlocks the box and sends it to Bob;
- Bob padlocks the box and sends it back to Alice;
- Alice removes her own padlock and sends it back to Bob; and finally
- Bob removes the padlock and retrieves his treasure.
In practice, we may call Alice's operation of locking the box operation A and unlocking the box will be operation A-1. Likewise, Bob's operations are B and B-1. So we are applying the operations ABA-1B-1 in that order. It is of course important that B and A-1 commute (i.e. BA-1=A-1B) or this doesn't work, which is where the difficult part of the task comes in when talking about applying these operations in a cryptographic situation--and of course we need a good way to "undo" our opreation.
The second problem is known as Conway's Soldiers after John Conway. It is possible to jump up to the fourth row, but impossible to reach the fifth. The solution presented by Conway is extremely elegant and definitely worth a read if you understand a little bit about infinite series and more particularly about geometric series. I'll give you the general idea of the proof:
- Each square in the grid gets assigned a numerical value
- Each time we jump a piece, the sums of the squares containing pieces either stays the same or decreases
- The value of our target square in the fifth rank is 1
- The value of all squares below the line is 1
- Since any finite number of pieces will have a sum less than 1 and no jump increases this sum, it is hence impossible to reach our target square
Once you have defined the numerical values of each square, it is easy to verify that the rest of the rules hold. Of course, you have to be very careful about what value gets assigned to each square to make it work!
Countability and Uncountability
I was going to write about something else, but I realized that this particular topic sort of ties in with the Conway's Soldiers problem. It's also one of the coolest ideas I was exposed to as an undergraduate mathematics major.
One thing about the solution given above is that the sum of all squares below the line is exactly 1, which implies that if we fill up the entire bottom part of the grid, then maybe we can get to the fifth rank. As it turns out, we can! The solution is weird though, since it obviously requires an infinite sequence of moves. In fact, it takes an infinite sequence of infinite sequences of moves to get it done! So how can we do this?
Well, first suppose we just have a single infinite sequence of moves. Our goal is to perform them in a finite amount of time. We will start out by performing our initial move. After half a second, we will perform our second move. After another quarter of a second our third and so forth. We can see that at time 1-2n-1 we are performing move n, so after one second is up, all of our moves have been performed.
Next, suppose we have an infinite sequence of of sequences of moves. Well, in our last example, the amount of time we took to complete the sequence of moves was arbitrary, so we can squish it down to 1/2 second, 1/4 second, or 1/2n seconds if we want. So, take our first sequence of moves and squish it down and perform them in the first half second. Take our second sequence of moves and squish it into the next quarter second. Then next sequence into the next 1/8 second and so forth. Now after a second is up, we've performed every move in every sequence of moves! Of course, we could now look at a sequence of sequences of sequences...of sequences of moves and make a similar argument. The key idea here is that I should be able to go backward and tell you exactly when each move was performed and show that it was a legal move.
So onto the idea of countability. The natural numbers are the numbers 1,2,3,... and so forth. It is clear that this is an infinite set and hence, it has more elements than any finite set. Now is where the weirdness starts. Consider only the positive even integers. This set is a subset of the natural numbers, and yet, this set has the same size! Why? We can match up the two sets one-to-one as follows:
- 1->2
- 2->4
- 3->6
- 4->8
- ...
Much like before, a key idea here is that we have to be able to go backwards and forwards. Given any natural number, I should be able to tell you what it maps to, but given any positive even number, I should also be able to tell you what number maps to it and there should only be one! Such a mapping is called a bijection. Any set which is either finite, or for which a bijection to the natural numbers exists is called countable. An interesting problem is to try and figure out what types of sets are countable. Even numbers are a bit of a surprise, since there seem to be distinctly fewer elements, but we can go the other direction too! For instance, the set of all integers is countable, which also seems weird since there seem to be many more elements than just the natural numbers. We can go even further than this though, and find some countable sets which seem much, much larger. For example:
- The rational numbers
- The algebraic numbers
- Any countable union of countable sets
- The number of books that could ever be written in English, German, Russian, Chinese, Greek, and Arabic
Given the above constraints, it may seem that almost everything should be countable. Not so! In a remarkable proof by Georg Cantor, he showed that it is impossible to come up with a bijection between the natural numbers and the real numbers. Hence, the real numbers are a "bigger" set than any of the aforementioned sets.
The above statement has not been without controversy, but is now widely accepted by the mathematical community. It is not the first such idea to be controversial in mathematics--for instance, irrational numbers and the concept of zero were both highly controversial at their conception.
It is also interesting to note that the natural numbers form the "smallest" and the real numbers form a bigger one. However, it is forever unknown whether or not the reals form the second smallest infinite set or whether there is something in between, though it is believed there is no such set in between. This is known as the continuum hypothesis.
The problems
I hope you guys are ready this week, because I'm bringing the heat! I'm going with a couple of chessboard problems. Remember to be respectful and use spoiler tags for anything resembling a solution.
1. An 8x8 chessboard has every square colored either black or white. You have two "frames"--a 3x3 and a 4x4 that you can place over any square region of 3x3 or 4x4 squares (respectively) and change the color of each square underneath the frame. Is it possible to get from any coloring to any other coloring by using these frames?
2. Given an 8x8 chessboard, it is easy to cover the entire thing with 2x1 dominoes without overlap. You may simply place them end-to-end across each row (or column). If you were to remove a single square from the chessboard, it is now clear that this is impossible--there are an odd number of total squares and each domino covers an even number of squares. Now, suppose you remove opposite corners of the chessboard. The situation is more tricky, for sure. There is no immediately apparent reason we shouldn't be able to do it, but it seems very difficult to accomplish. Is it possible?
If you finish up #2, you might start to wonder "What are necessary and sufficient conditions for the removal of squares of a chessboard such that we can cover it with 2x1 (or any other shape polyomino)?" I have an idea for the 2x1 case, but I haven't worked out a proof yet. I was also once asked to solve the case of a 12x12 chessboard with three corners removed, covered with 3x1 polyominos.
Next month's volume might be postponed or canceled because of my move. We'll see how it goes.
Mmm, countability. I love set theory (and number theory in general). I was very close (had applications filled out) to doing grad school in abstract algebra before I decided to do chemistry instead.
I believe #2 is impossible.
Extension of 2:
I may have seen this stuff before, so I don't know if I'm at an advantage.
Your first solution is correct. Below are my thoughts to your more general idea and a solution to the 12x12 case.
I'll post what I think are necessary and sufficient conditions in a separate post below.
Well this sure is an easiser way to say
That's what I meant by "tighten it up."
8x8 board for experimentation.
It probably works. I've only had a chance to test it in Chrome.
To use it, choose your frame size (default is 3x3) and click the square to act as the TOP-LEFT corner for the frame. If you mess up, either reload the page or click the play button at the top-right.
Cool!
Sean, Thanks! Did you program that?
In pieces and bits, I played with it during commmercial breaks during the HR Derby, and I did it.
So it is do-able.
Yes, I can convert the checkerboard to all black (or all white, or the inverse of it's original state), but that doesn't solve the problem as far as I can tell.
Well, I've spent about the past three hours playing with the grid Sean made. I thought I might have some insight, but then it slipped between the fingers of my brain. I think I should just start with a solid grid and perhaps induce from there that one white, 63 black can't work. I'm sure that if I had a 2x2 or 5x5, I could do it.
I did figure out how to go from solid to checkerboard (or vice versa) in 16 moves. Only using the 4x4.
Yeah. It was surprisingly easy to do once I settled on the HTML.
Until I did that, I was thinking it should be possible.
That doesn't prove that this works (although I did above), but I think that's part of the way to go.
That doesn't prove that this works (although I did above)
Be careful about the wording of the question. You need to be able to get from any position to any other position. Of course, if you can get to any position from the checkerboard position, then you can get from any position to any other position. 🙂
My mistake, I misremembered the question when I was doing it. I thought I just wanted to get everything to the same color.
But at least, now we know we can start with everything colored the same.
oops, disregard my comment above.
My thoughts for a necessary and sufficient condition for tiling an m x n board with some squares removed with dominoes below.
I'm only addressing the issue of dominoes here, not polyominoes. I have an idea for a more general necessary and sufficient condition for polyominoes, but it doesn't really seem to be as "good" as this one.
Ok, here is my more general conjecture. Prepare to first be confused, and then disappointed.
Actually, looking at AMR's example above disproves my conjecture. I have no idea what to conjecture in the more general case. I told you to prepare to be disappointed!
Nope, that can't be it, either, because I was just playing around and
Yeah, the situation becomes much, much trickier when using anything other than dominoes. This method can be used to show the lack of existence of such a tiling, but
...