My Favorite Math Problem(bytesauna.com)
bytesauna.com
My Favorite Math Problem
https://bytesauna.com/post/my-favorite-math-problem
54 comments
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.
Stating the "opposite colored holes don't prevent tiling by dominoes" problem requires some kind of "coloring" to know which pairs of tiles are in scope for being holes.
I agree with the comment you're replying to: the original problem (in the linked post) is about an 8x8 square in which 1x1 squares at either corner are removed, and asking whether it can be tiled by 2x1 tiles. The idea of "coloring" the board and the tiles can then be presented as part of the solution -- in fact, this is a great example of how one idea (coloring) can make a problem much earlier.
I believe your comment is actually about the extension (to this problem and solution) that I posted in another comment: https://news.ycombinator.com/item?id=46005842
I believe your comment is actually about the extension (to this problem and solution) that I posted in another comment: https://news.ycombinator.com/item?id=46005842
Good point. As presented, I thought it was very easy.
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.
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
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."
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."
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!
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!
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.
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/)
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/)
I am a big fan of the following related problem:
* web ui: https://openprocessing.org/sketch/126042/
* Numberfile video: https://youtu.be/lFQGSGsXbXE
* 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.)
(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.
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.
Well, I had to write it down, but I have to write down everything these days. But from the way the problem was phrased, it was obvious you don;t have to actually find to numbers.
[deleted]
You don’t have to do all that.
If you have a+b and a-b you’ll get 2a when added together.
So knowing just the sum we can say that a is 9 in this setup.
Now we need to figure out b.
Multiplying out those you get
a^2 + ab -ab - b^2
And I get a longing for not having started this a phone.
Cancels and fill in what we know and we get 81 - b^2 = 37
b = sqrt(44) = sqrt(4)*sqrt(11) = 2sqrt(11)
If you have a+b and a-b you’ll get 2a when added together.
So knowing just the sum we can say that a is 9 in this setup.
Now we need to figure out b.
Multiplying out those you get
a^2 + ab -ab - b^2
And I get a longing for not having started this a phone.
Cancels and fill in what we know and we get 81 - b^2 = 37
b = sqrt(44) = sqrt(4)*sqrt(11) = 2sqrt(11)
None of this is required for solving the problem in your head. All that is required is the ability to add 1-digit unit fractions in your head, as the problem requests.
> the statement "you can do it in your head" generally does not entail this much complexity
It's funny that you jump to accusing OP of falsely claiming you can do it in your head, without apparently considering the alternative: that the intended solution is a simpler one than you outlined.
Trust me, you can do this in your head if you know basic high school level math, and you don't need to solve quadratic equations or keep a ton of numbers in your head at the same time.
If I ask you if 123456789 is a prime number, do you complain that it's not fair to make you perform division on such a long number?
It's funny that you jump to accusing OP of falsely claiming you can do it in your head, without apparently considering the alternative: that the intended solution is a simpler one than you outlined.
Trust me, you can do this in your head if you know basic high school level math, and you don't need to solve quadratic equations or keep a ton of numbers in your head at the same time.
If I ask you if 123456789 is a prime number, do you complain that it's not fair to make you perform division on such a long number?
>Trust me, you can do this in your head if you know basic high school level math
yeah, i guess it was a mistake to graduate from MIT undergrad and grad school in quant fields, i should have just stuck with high school math
>If I ask you if 123456789 is a prime number, do you complain that it's not fair to make you perform division on such a long number?
you tell me, is 13717421 prime?
yeah, i guess it was a mistake to graduate from MIT undergrad and grad school in quant fields, i should have just stuck with high school math
>If I ask you if 123456789 is a prime number, do you complain that it's not fair to make you perform division on such a long number?
you tell me, is 13717421 prime?
The difference between the two is that it’s clear that 123456789 can’t be prime since the sum of the digits is a multiple of 3, which doesn’t even require finding the sum since we know 1+8, 2+7 up to 4+5 are multiples of 3. I can even tell you that 43717421 isn’t prime without having to do a divisibility test on it by looking at the digits, although it is a bit more tedious than the 123456789 field.
the difference between the two is that I removed the factors of 3 from 123456789 to get 13717421. so much for your secret knowledge of a hyperspecific case.
You're still missing the point of these problems, which is to challenge you to come up with a clever proof rather than brute-force the solution.
dhosek understood the assignment by making an argument that 123456789 is composite without relying on explicit division of a 9-digit number, which most people would find rather difficult to do in their heads.
Similarly, the posted link is about tiling a mutilated chessboard with dominos. Tiling problems in general are NP-hard, so clearly this isn't something you can solve in your head _in general_, but the charm of that specific problem is that you _can_ solve it by making an insightful observation to avoid the brute force computations.
Similarly, for the puzzle you complained about: we are asked to find 1/a + 1/b where a × b = 37 and a + b = 18. The general solution is to solve a system of two linear equations which involves solving a quadratic equation, which is possible, but tedious and difficult to keep in your head, but the entire point of the question is that there is a better way to figure out the result.
dhosek understood the assignment by making an argument that 123456789 is composite without relying on explicit division of a 9-digit number, which most people would find rather difficult to do in their heads.
Similarly, the posted link is about tiling a mutilated chessboard with dominos. Tiling problems in general are NP-hard, so clearly this isn't something you can solve in your head _in general_, but the charm of that specific problem is that you _can_ solve it by making an insightful observation to avoid the brute force computations.
Similarly, for the puzzle you complained about: we are asked to find 1/a + 1/b where a × b = 37 and a + b = 18. The general solution is to solve a system of two linear equations which involves solving a quadratic equation, which is possible, but tedious and difficult to keep in your head, but the entire point of the question is that there is a better way to figure out the result.
That's only 9 digits. Determining if 12345678910 is primes would be outrageous. That's got more digits than I have fingers!
ab = 37; a+b = 18; 1/a + 1/b = b/ab + a/ab = (a+b)/ab = 18/37
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 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! :)
I know the 'fast way'. Took me a second or two to get the answer, but it is so obvious that I cannot imagine anyone trying to solve this by calculating a and b 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.
This is a very nice puzzle.
I recommend looking also at the THOG problem. See https://en.wikipedia.org/wiki/THOG_problem.
I recommend looking also at the THOG problem. See https://en.wikipedia.org/wiki/THOG_problem.
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.
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.
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 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?
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.
Proving that the solution is unique may be more subtle.
last year i learn about the Collatz Conjecture which i found super interesting.
did anyone else just play what felt like a mental game of Snake in their head?
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."
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."
> 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