This is a classic of course, but there is a lesser known extension to this problem (to be read only after this problem has been solved), which also has a beautiful "proof without words":
> an 8x8 board in which squares at opposite corners have been removed cannot be tiled with dominoes, [...]. But what if two squares of different colours are removed? Ralph E. Gomory showed that it is always possible, no matter where the two removed squares are
The problem is slightly more challenging if you don't use a chessboard, but just a grid, because then you must first come up with the idea of coloring it.
A hint (bordering on solution): each game eliminates a player. Note that this will also give a solution to a tournament where there are not a power of two entrants (ignoring byes).
From the title, I first imagined what my favorite math problem was, then clicked on the article -- and they had the same one!
For me, the reason this problem is cool is that it exemplifies mathematical thinking: superficially the problem is about placing individual dominos but the solution is about seeing the underlying structural properties. Similar to Euler realizing the bridges in Königsberg were a graph.
The content was interesting but the cookie consent and in-your-face subscription pop-ups are infuriating and annoying. Thought I’d mention it since you did go to the trouble of popping by this discussion!
A "lattice point" on the plane is a point where both coordinates are integers, like (3, 4) or (-2, -1). Prove that for any five lattice points, there will be two of them that if you connect them with a line segment, there's another lattice point between them on that line.
One of my favorites is one that you should be able to do in your head: The product of two numbers is 37, their sum is 18. What is the sum of their reciprocals?
(I happened to encounter this two times in close succession when I was getting my teaching credential: first in a teaching manual and then a day or two later, a couple teachers at the school where I was doing my student teaching were puzzling over it and thought they’d challenge me with it and I gave them the answer immediately which shocked them since they’d spent a long time on solving this with algebra and I did it in my head in less than a second. To be honest, I probably wouldn’t have been so quick at the solution without having already seen it.)
>The problem does not state that the numbers have to be integers. a and b happen to be 9 +- 2 sqrt(11)
but the problem does state that you should be able to do it in your head. who exactly should be able to formulate and reduce simultaneous equations in xy then apply the quadratic formula (with some spicy +/- to keep track of) to get an answer with an irrational number, all in their head? usually, when a problem like this is given there is a shortcut that leads to a simple, not only rational but integer, answer.
the statement "you can do it in your head" generally does not entail this much complexity, as the person who said "you can do it in your head" comes out and says after previously spending a fair amount of time working on it.
words matter, people, that's why I didn't throw in the adjective integral even though I could have.
> they’d spent a long time on solving this with algebra
I don't get it. I don't see why / how it would take any longer than a second or two to solve 'with algebra'. What does that even mean? You would just maybe write down the steps rather than doing them in your head. Is there any other way to solve the problem?
I'm pretty sure he means they did the problem by first figuring out the numbers a and b. That's the slow way. I can reveal the fast way if you want, but maybe you should think about it a bit more first! :)
What I like most about this math problem is explaining it to people who understand what I'm saying but still insist that it might be possible and they're going to do it. It's a nice lesson for me to think about and carry through life.
Knowing that the solution is unique makes this trivial to solve in a couple minutes just by scribbling on a piece of paper (I just did). It does not seem more subtle than the original.
Proving that the solution is unique may be more subtle.
Nice problem! I wonder if there is a generic way of testing such a problem with different board arrangements. For example, could you apply knot theory or another concept?
I haven’t seen this representation before—I suppose the vertices of the graph are the chessboard squares, the edges
are adjacency (white squares can only be adjacent to black squares and vice versa, which gives the bipartite-ness), and covering two squares corresponds to removing those two vertices from the graph?
Well, upon a closer look, one notices that the chessboard coloring is not necessary for the problem statement. It's kind of a hint actually as you could equally well just consider a blank 8x8 board and realize that this coloring arugment works. I just feel the problem is unreasonably difficult that way.
The coloring is kind of additional structure that is applied on the object you are working with. And I think this idea of "applying structure" is a very generic. You can solve similar combinatorial arrangement problems that way, but it goes beyond that.
I think that a nice, classic (and significantly more advanced) example is showing that plane and punctured plane (a plane with one missing point) are topologically different. The fundamental (homotopy) groups of these spaces are different, and hence the spaces cannot be continuously deformed to each other.
Somehow the spirit is the same, I feel. In this topology proof it's not a grid you are working with, but a topological space. And the structure you apply is not a coloring, but something quite abstract (a homotopy group). The idea in both cases is similar, though: You apply structure and this structure reveals something that's not easy to see directly.
The magic part is figuring out the structure that produces the data you need.
I do not care for this problem as it is not a real problem.
Kaprekar's constant is interesting. This one is not.
As for explaining complex math to children, I like to start with zero not being a real number. "If you have zero cookies why are we talking about cookies? There are none. You're now thinking of cookies, which means you have zero cookies, and if you want one then you have negative cookies."
This is a classic of course, but there is a lesser known extension to this problem (to be read only after this problem has been solved), which also has a beautiful "proof without words":
> an 8x8 board in which squares at opposite corners have been removed cannot be tiled with dominoes, [...]. But what if two squares of different colours are removed? Ralph E. Gomory showed that it is always possible, no matter where the two removed squares are
Proof/spoiler: https://mathoverflow.net/a/17328/111
The problem is slightly more challenging if you don't use a chessboard, but just a grid, because then you must first come up with the idea of coloring it.
Good point. As presented, I thought it was very easy.
For some reason this reminds me of the following teaser:
In a typical "tournament" -- say 64 teams, how many matches/games are played before declaring the final winner?
Not sure if there's a way to do spoilers here, but there's a very easy one sentence explanation that involves very close to "no math at all."
A hint (bordering on solution): each game eliminates a player. Note that this will also give a solution to a tournament where there are not a power of two entrants (ignoring byes).
Very close, as in one step of arithmetic.
From the title, I first imagined what my favorite math problem was, then clicked on the article -- and they had the same one!
For me, the reason this problem is cool is that it exemplifies mathematical thinking: superficially the problem is about placing individual dominos but the solution is about seeing the underlying structural properties. Similar to Euler realizing the bridges in Königsberg were a graph.
If you enjoy that problem you might enjoy:
Cut one corner off a chessboard. Is it possible to tile the remaining board with 3-by-1 dominoes?
(Spoiler/solution: https://www.jeremykun.com/2011/06/26/tiling-a-chessboard/)
Hi HN,
I'm Matias. I run a small business (ByteSauna) with a blog on the site. I try my best to serve well thought out content. Here's this weeks post.
Hope you enjoy it!
The content was interesting but the cookie consent and in-your-face subscription pop-ups are infuriating and annoying. Thought I’d mention it since you did go to the trouble of popping by this discussion!
A similar problem that I like.
A "lattice point" on the plane is a point where both coordinates are integers, like (3, 4) or (-2, -1). Prove that for any five lattice points, there will be two of them that if you connect them with a line segment, there's another lattice point between them on that line.
If you want to avoid "scary" math words, you could frame this as picking any 5 'corners' on a sheet of squared paper (of any arbitrary size)
Wow, very cool problem. Took me a second, very satisfying to land on the solution.
Nice, thank you. I wouldn't have believed it.
Worth mentioning that the "another lattice point on that line" is not necessarily one of the five.
But it seems to be a special point too
I am a big fan of the following related problem:
* web ui: https://openprocessing.org/sketch/126042/
* Numberfile video: https://youtu.be/lFQGSGsXbXE
One of my favorites is one that you should be able to do in your head: The product of two numbers is 37, their sum is 18. What is the sum of their reciprocals?
(I happened to encounter this two times in close succession when I was getting my teaching credential: first in a teaching manual and then a day or two later, a couple teachers at the school where I was doing my student teaching were puzzling over it and thought they’d challenge me with it and I gave them the answer immediately which shocked them since they’d spent a long time on solving this with algebra and I did it in my head in less than a second. To be honest, I probably wouldn’t have been so quick at the solution without having already seen it.)
37 is prime. Are you sure this problem statement is correct?
The problem does not state that the numbers have to be integers. a and b happen to be 9 +- 2 sqrt(11)
>The problem does not state that the numbers have to be integers. a and b happen to be 9 +- 2 sqrt(11)
but the problem does state that you should be able to do it in your head. who exactly should be able to formulate and reduce simultaneous equations in xy then apply the quadratic formula (with some spicy +/- to keep track of) to get an answer with an irrational number, all in their head? usually, when a problem like this is given there is a shortcut that leads to a simple, not only rational but integer, answer.
the statement "you can do it in your head" generally does not entail this much complexity, as the person who said "you can do it in your head" comes out and says after previously spending a fair amount of time working on it.
words matter, people, that's why I didn't throw in the adjective integral even though I could have.
You _can_ literally do this in your head, and also, it doesn't matter what the numbers are, what the product is or what the sum is.
Thanks! The mention that it was solved in under a second must have thrown me :-)
> they’d spent a long time on solving this with algebra
I don't get it. I don't see why / how it would take any longer than a second or two to solve 'with algebra'. What does that even mean? You would just maybe write down the steps rather than doing them in your head. Is there any other way to solve the problem?
I'm pretty sure he means they did the problem by first figuring out the numbers a and b. That's the slow way. I can reveal the fast way if you want, but maybe you should think about it a bit more first! :)
What I like most about this math problem is explaining it to people who understand what I'm saying but still insist that it might be possible and they're going to do it. It's a nice lesson for me to think about and carry through life.
I like this closely related and slightly more subtle problem:
Which unique square (up to symmetry) must be left if you cover the 64 squares of a chess board with 21 3x1 trominoes?
Knowing that the solution is unique makes this trivial to solve in a couple minutes just by scribbling on a piece of paper (I just did). It does not seem more subtle than the original.
Proving that the solution is unique may be more subtle.
Nice problem! I wonder if there is a generic way of testing such a problem with different board arrangements. For example, could you apply knot theory or another concept?
Dominoes on mutilated chessboards are matchings in a bipartite graph, a well studied problem for which an efficient algorithm exists.
I haven’t seen this representation before—I suppose the vertices of the graph are the chessboard squares, the edges are adjacency (white squares can only be adjacent to black squares and vice versa, which gives the bipartite-ness), and covering two squares corresponds to removing those two vertices from the graph?
Yes, and this is a generalisation of the trick from the problem described in the article.
The chessboard in the article is a bipartite graph with different number of vertices in the two groups, so it cannot have a perfect matching.
Well, upon a closer look, one notices that the chessboard coloring is not necessary for the problem statement. It's kind of a hint actually as you could equally well just consider a blank 8x8 board and realize that this coloring arugment works. I just feel the problem is unreasonably difficult that way.
The coloring is kind of additional structure that is applied on the object you are working with. And I think this idea of "applying structure" is a very generic. You can solve similar combinatorial arrangement problems that way, but it goes beyond that.
I think that a nice, classic (and significantly more advanced) example is showing that plane and punctured plane (a plane with one missing point) are topologically different. The fundamental (homotopy) groups of these spaces are different, and hence the spaces cannot be continuously deformed to each other.
Somehow the spirit is the same, I feel. In this topology proof it's not a grid you are working with, but a topological space. And the structure you apply is not a coloring, but something quite abstract (a homotopy group). The idea in both cases is similar, though: You apply structure and this structure reveals something that's not easy to see directly.
The magic part is figuring out the structure that produces the data you need.
did anyone else just play what felt like a mental game of Snake in their head?
last year i learn about the Collatz Conjecture which i found super interesting.
I do not care for this problem as it is not a real problem.
Kaprekar's constant is interesting. This one is not.
As for explaining complex math to children, I like to start with zero not being a real number. "If you have zero cookies why are we talking about cookies? There are none. You're now thinking of cookies, which means you have zero cookies, and if you want one then you have negative cookies."