7 ms·
My Favorite Math Problem
- Scott-David 10mo ago[dead]
- mapehe 10mo agoHi 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!
- loloquwowndueo 10mo agoThe 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!
- rasse 10mo agoNice 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?
- mapehe 10mo agoWell, 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.
- praptak 10mo agoDominoes on mutilated chessboards are matchings in a bipartite graph, a well studied problem for which an efficient algorithm exists.
- CrazyStat 10mo agoI 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?
- praptak 10mo agoYes, 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.
- vorticalbox 10mo agolast year i learn about the Collatz Conjecture which i found super interesting.
- svat 10mo agoThis 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 https://mathoverflow.net/a/17328/111
- cochleari_major 10mo agoI am a big fan of the following related problem: * web ui: https://openprocessing.org/sketch/126042/ https://openprocessing.org/sketch/126042/ * Numberfile video: https://youtu.be/lFQGSGsXbXE https://youtu.be/lFQGSGsXbXE
- amelius 10mo agoThe 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.
- estomagordo 10mo agoGood point. As presented, I thought it was very easy.
- lupire 10mo agoStating 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.
- svat 10mo agoI 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 https://news.ycombinator.com/item?id=46005842
- tromp 10mo agoI 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?
- CrazyStat 10mo agoKnowing 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.
- 867-5309 10mo agodid anyone else just play what felt like a mental game of Snake in their head?
- pizzafeelsright 10mo agoI 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."
- evmar 10mo agoFrom 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.
- lacker 10mo agoA 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.
- tantalor 10mo agoWorth mentioning that the "another lattice point on that line" is not necessarily one of the five.
- stephan411 10mo agoBut it seems to be a special point too
- stephan411 10mo agoNice, thank you. I wouldn't have believed it.
- bobbylarrybobby 10mo agoWow, very cool problem. Took me a second, very satisfying to land on the solution.
- chias 10mo agoIf 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)
- EliRivers 10mo agoWhat 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.
- j2kun 10mo agoIf 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/ https://www.jeremykun.com/2011/06/26/tiling-a-chessboard/)
- jrm4 10mo agoFor 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."
- dhosek 10mo agoOne 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.)
- pretzellogician 10mo ago37 is prime. Are you sure this problem statement is correct?
- deepspace 10mo agoThe problem does not state that the numbers have to be integers. a and b happen to be 9 +- 2 sqrt(11)
- pretzellogician 10mo agoThanks! The mention that it was solved in under a second must have thrown me :-)
- fsckboy 10mo ago>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.
- I_complete_me 10mo agoThis is a very nice puzzle. I recommend looking also at the THOG problem. See https://en.wikipedia.org/wiki/THOG_problem https://en.wikipedia.org/wiki/THOG_problem.