Almost 150 years ago the game 15-puzzle was invented and quickly gain lots of popularity. The rules are quite simple – you start with a board with 15 numbered pieces as in the image below, where the pieces are ordered according to their numbers, except the 14 and 15 pieces which switch positions. Given this board we are allowed to slide into the missing place any one of the pieces next to it, how many times that we want, and we win if we manage to get all the pieces in the right order.
This game became very popular during the 1880 and there was even a cash reward for anyone who can solve it. However, no matter how many people tried, no one could solve it, which is not surprising since it is unsolvable (what is surprising, it that it was proved to be unsolvable in 1879). Indeed – this game has a game invariant which doesn’t change when using legal moves and the initial state (with 14, 15 switched) and the ordered state have different invariants, so it cannot be solved.
In this post we will see, as mathematicians, how to even start thinking about this problem, and eventually get to this game invariant.
One of the thing I really love in mathematics is how different subjects, which at least when starting to learn mathematics seem far apart, can come together in interesting ways. While the first reaction of many people might be that it just makes it more complicated, I always thought that it is the other way around. This means that I can use everything that I know from all of the different subjects, instead of using just my knowledge from a single subject. More over, it is almost always interesting to see the same problem from several points of view, each one with its own tools and ideas, and see how they all connect.
In this post, I want to share one such problem with you. Originally, I knew it from the algebra point of view, and that alone can fill several posts. However, along the way I have heard about this interesting new geometric proof, which connects this already interesting problem to even more field in mathematics. And the best thing, as many problems, it has a very humble beginning with a theorem we all learn about in high school – the Pythagorean theorem.
For the Hebrew speaking people – a video version of this post can be found here.
In the previous post we learned about the mediant, which is the “wrong” way to add rationals : . While this operation is not well defined, and depends on the presentation of the rational numbers and not just their values, we saw that it still has interesting properties, and in particular where and . Moreover, if we start with and add their mediants to get , and then repeat the process by adding the mediants of each subsequent pair , and continue repeating it again and again, then we get all of the rationals in .
In the previous post we tried to keep the math elementary as possible. In this post we will go a little bit more advanced and take a look at this operation from several mathematical perspectives.
One of the things that I love about Mathematics, is how one can come across a mathematical problem or a phenomenon which you can look at from several points of views, each one different, yet they all combine together to form an interesting story. It can be a story that grows with you as you learn more and more advanced mathematics, or a story that lets you connect different parts of mathematics.
The story, which is the focus of this post and the next one, is a story of such a problem around the operation which takes two positive rational numbers and “returns” the wrong way to add them: . This story starts from the most elementary mathematics there is, and goes all the way to the most advanced, and on the way it introduces many interesting concepts in mathematics.
Taking a final exam in a course is not really a celebration cause for most students, but it is just not as fun to be on the other side as exam checkers. It can easily take several days to grade the answers for the same question for hundreds of students. The exam checkers would probably tell you that by just reading a few lines from the answer they know if it is going to be (mostly) correct or not, however they still need to read all of it just to be sure. These couple of lines can still be misleading – a good start can still lead to a complete failure, and a bad start might eventually, somehow, get most of the details right.
So maybe when checking exams we cannot really do it, but are there problems where reading only few lines from a proof is enough to determine its correctness? As it turns out, certain problems have innate structures that makes them more “stable” than others – if you write a “wrong” solution for them, then you can see it almost everywhere, so reading just a few lines will be enough.
One of the best examples for this kind of problem is the linearity testing. Suppose that someone claims that a function is linear, and to prove it they show that for all . What Blum-Luby-Rubinfeld (BLR) showed that in a sense it is enough to know that one of this conditions (chosen randomly) is true to conclude that all of them are true with high probability. In this post we will try to see what is so important about linearity, and which structures hides in this problem, to make this miracle happen.
In the previous post we considered a simple domino game where we needed to cover a board with dominos. We wanted to find a way such that if a board couldn’t be covered, then we could prove it easily, and this led us to the definition of the game invariants. These are “elements” that do not change as the game progresses, so if the initial and final state have different invariants, then we could not reach from one to the other.
In this post, we will deal with a new game – the Peg Solitaire – and see if and how we can find such invariants for this game.
Sudoku is a simple game that was invented more than a century ago, but only started to get famous about 20 years ago, and suddenly it started appearing in the game sections of many papers, you could buy booklets full of Sudokus, there are Sudoku websites, applications and many more.
If you ever played Sudoku, you know that it can sometimes be very hard to solve, and it can become even harder when we start to use other variants of the game, like larger Sudoku with blocks. While it can be hard and time consuming to solve, in general the sudoku games that you see in the game sections are not impossible to solve. More over, once you solve a Sudoku puzzle, it is very easy to prove to other people that you know the solution – just show them the solution and they can check its validity quickly. However, what happens if you are given a Sudoku puzzle that can’t be solved? How can you even check that it can’t be solved, and if you know that it is unsolvable, can you easily prove it to other people?
The goal of this series of posts (next one is here) is to consider games like Sudoku (though a bit simpler), and try to learn how to find and use tools to show that in some cases they are unsolvable.
We have now seen in the previous two posts a few results about prime numbers. In the first one, we saw why primes are so important and used Euclid’s proof to show that there are infinitely many primes. Moreover, we conjectured that if and are coprime, then there are infinitely many primes with . And to top it all, we also conjectured that they are evenly distributed among the integers which are coprime to .
Writing conjectures down is much easier than actually proving them, and in order to do this, in the second post we reproved the fact that there are infinitely many primes, this time using Euler’s proof. The main idea was to consider the infinite sum and to show that it diverges to infinity and therefore there are infinitely many primes.
The set of prime numbers has very little structure that we know of, and actually what we are trying to do is to find some of this structure. For that, we moved step by step to worlds with more structure, in which we have many more tools that can be used to tackle this problem – from the set of prime numbers to the integers (which have addition and multiplication) and from there to the real numbers (which also have a metric, derivatives, integrals, etc). Then, if we are lucky enough, we can prove this claim in the world of real numbers and pull it back to the integers and then back to the prime numbers. In this post, we will find the last step which will allows us to go to even smaller sets of primes, according to their equivalent classes modulo , and prove Dirichlet’s theorem:
THEOREM: For any coprime integers, there are infinitely many primes with .
In the previous post we saw why primes are so important, and used Euclid’s proof to show that there are infinitely many primes. We further conjectured that not only there are infinitely many primes, they are also “nicely” distributed among the integers.
More precisely, if we fix some integer , then for every we can ask how many primes are there such that . If and are not coprime, then we showed that there is either zero or one such primes, so the infinitely many primes that we already know exist are equivalent to mod where the are coprime to . The conjecture was that not only the union over these is infinite, but for each the number of primes is infinite (which is Dirichlet’s theorem for primes in arithmetic progression), and more over, in a sense we have “the same” infinite in each of those . While we could generalize a bit Euclid’s proof to some other cases, it becomes really complicated quite fast.
Trying to look for other methods, we mix our prime numbers with a bit of calculus, and turn to Euler for some help.
The prime numbers are one of those basic, yet mysterious, sets in mathematics, that while we know much about them, there are still many interesting open questions waiting to be answered, including probably the most well known conjecture in mathematics – the Riemann conjecture.
While this conjecture, and the attempts at its solution, use very advanced mathematics, even the most basic questions about the prime numbers already have many interesting results and lead to interesting tools, and in this post and the next two (here and here), we will try to understand some of these just by trying to “count” primes.