12 ms·
My Favorite Math Problem
- euske 5y agoMath is the closest thing to magic that actually exists (and we can work on).
- srvmshr 5y agoThis was covered in MIT 6.042 in in a different and bit harder way by Tom Leighton as a general proof. The problem involved tiling the Stata courtyard with L-shaped tiles. You need a bit of mathematical induction to prove such results.
- dasudasu 5y agoThe 2x1 covers a1 and b1, not a1 and a2.
- antognini 5y agoI came across one of my favorite math problems in high school and it blew my mind. ABC DEF + GHI ----- 123J Each letter represents a distinct digit 0-9. What is J? Of course you can write a short program that iterates through the possibilities. But there is also a very elegant solution that fits in a tweet. (If you don't want to try solving it, or have tried and have given up, here is the solution: https://twitter.com/joe_antognini/status/1436412147324502016 https://twitter.com/joe_antognini/status/1436412147324502016)
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- bqmjjx0kac 5y agoDoes each letter lie in [0,9] or did you mean [1,9]?
- spencerflem 5y agoThere's 10 letters including J so 0 is allowed
- bqmjjx0kac 5y agoAha, I can't count, apparently. Thanks!
- taeric 5y agoMy favorite in this line is send+more=money.
- Miiko 5y agoMine too, but you cannot solve that one in one tweet, so it does not fit the subject.
- vanboxel 5y agoThe "Math Misery" blog has several problems like this, for example http://mathmisery.com/wp/2017/04/02/cryptarithmetic-puzzle-81/ http://mathmisery.com/wp/2017/04/02/cryptarithmetic-puzzle-8...
- deleted 5y ago[deleted]
- gopalv 5y ago> there is also a very elegant solution that fits in a tweet. (If you don't want to try solving it, or have tried and have given up, here is the solution I tried to understand the tweet a couple of times, but I couldn't follow the proof from the tweet itself, so I wrote it up again with the basic axiom from the tweet as a basis + work out each step of the process. https://gist.github.com/t3rmin4t0r/a953450ac64b6868540bbce79df4e9a3 https://gist.github.com/t3rmin4t0r/a953450ac64b6868540bbce79... The original proof is elegant, because it has a single item of information (the "what") to use to solve the entire thing, but was missing the "how" for me.
- kazinator 5y agoModulo 9, a decimal integer is equal to the sum of its digits. More precisely, congruent, notated by ≡: For instance 123 ≡ 1+2+3 ≡ 6 (mod 9). We show congruences using ≡, and always have (mod N) on the far right to indicate the modulus for the congurence. More generally, if ABC is a decimal string, then we know that ABC ≡ A + B + C (mod 9). Moreover ABC + DEF + GHI must be congruent to A+B+C + D+E+F + G+H+I (mod 9). And if ABC + DEF + GHI is equal to 123J, then A+B+C + D+E+F + G+H+I ≡ 123J ≡ 1+2+3+J (mod 9). Thus: A+B+C+D+E+F+G+H+I ≡ 1+2+3+J (mod 9) Now suppose we add J to both sides: A+B+C+D+E+F+G+H+I+J ≡ 1+2+3+J+J (mod 9) OK so now we know that the left hand side A+...+J contains all elements from 0 to 9, because of the problem constraint that the letters represent unique digits. The numbers 0 to 9 add together to 45. Now 45 is congruent to 0 (mod 9). Therefore: A+B+C+D+E+F+G+H+I+J ≡ 45 ≡ 0 ≡ 6 + 2J (mod 9) We no longer care about the A+..+J; it's vanished. We solve the remaining equation: 0 ≡ 6 + 2J (mod 9) If 6 + X (mod 9) is congruent to 0, X must be one of {... -6, 3, 12, 21, 30, 39 ...}: the set of integers congruent to 3, (mod 9). If X = 2J, where J is a one-digit decimal integer, X must be an even, non-negative integer. That rules out -6, 3 and 21. It can't be 30, because J can't be 15. X must be 12, which gives J = 6.
- quietbritishjim 5y agoThat was all good, except this bit was not obvious to me: > Modulo 9, a decimal integer is equal to the sum of its digits. More precisely, congruent, notated by ≡: > For instance 123 ≡ 1+2+3 ≡ 6 (mod 9). This is the part where the parent comment's explanation was helpful.
- maest 5y agoA nuance here is that you are assuming the existence of a solution. It may be the case there are no values for A to J that can result in that equation. Iterating through all possibilities shows that the solution exists, the proof in the tweet doesn't.
- johnday 5y agoThe proof in the tweet gives steps to getting a solution, and the solution works. In what way is that not showing that the solution exists?
- Jeff_Brown 5y agoThe tweet only shows what J is, conditional on that there is a solution.
- quchen 5y agoIsn't that exactly how any constructive proof works?
- Jeff_Brown 5y agoI suppose it depends on your definitions, but most constructive proofs construct an entire solution -- that is, leaving no variables free unless the solution applies to any value of them. This only solves for J assuming the others can be solved for.
- yodsanklai 5y agoA constructive proof would exhibit a solution. In that case, it has been shown that if a solution exists, it must be that J=6. With this additional information, you can try and find the other digit and conclude the proof (or in the case there's no solution, reach a contradiction). I don't know how this type of proof is called in English but it's quite common. First come up with necessary conditions on your potential solution, and then you use these conditions to build an actual solution.
- 5y ago
- strstr 5y agoBunch of problems like this are in the book "Problem-Solving Strategies" by Arthur Engel [1], I believe even including this particular one. Fun book. [1]https://www.google.com/books/edition/Problem_Solving_Strategies/IJLzBwAAQBAJ?hl=en&gbpv=0 https://www.google.com/books/edition/Problem_Solving_Strateg...
- rodneyzeng 5y agoYeah, got this book and the problem was also a classical one.
- taeric 5y agoOr anything with Martin Gardner's name on it. All worth reading.
- romaththrow592 5y agoThis book is a classic one for kids participating in math competitions in Romania. I once had to solve a variation of this problem at a math contest when I was in 6th grade.
- deleted 5y ago[deleted]
- mcphage 5y agoThis one is my favorite, too—it really highlights what the job of a mathematician is. The board is the board, and the dominos either fit or they don’t, and it’s not clear why. But once someone adds the checkerboard shading—not changing the problem at all, but just adding a new way to look at it—suddenly the solution falls out, clear and obviously true.
- brennanpeterson 5y agoI am curious. Are all boards that have equal white and black tiles counts solvable?
- mcphage 5y agoNope—consider a black and white square, disconnected. But if they don’t have equal black and white counts, then they’re definitely not solvable.
- deleted 5y ago[deleted]
- Karliss 5y agoSlightly more interesting example which isn't disconnected is a H letter consisting of 8 blocks. 3 blocks high and 2 in the horizontal section.
- dmurray 5y agoYes, by induction. Suppose the total number of squares is 2n. Remove any domino that doesn't disconnect the board, and reduce to the problem for 2n - 2. Alternative proof: no, by example. Consider the shape made up by the X's in XXX .X. .X. XXX (All maths proofs should be presented alongside a proof of the opposite result, to allow the reader to judge which one is likely to have slipped something past you. My favourite presentation following this rule is Mental Poker [0] by the authors of RSA.) [0] https://people.csail.mit.edu/rivest/pubs/SRA81.pdf https://people.csail.mit.edu/rivest/pubs/SRA81.pdf
- willis936 5y agoMy favorite pet math problem so far is: how many times of day are all three hands on a clock equal parts apart? I have a close but wrong answer that is more interesting than the right answer. I wish I knew of a STEM periodical that accepted amateur articles because I want to do a write-up on this.
- dragonwriter 5y ago> My favorite pet math problem so far is: how many times of day are all three hands on a clock equal parts apart? Depends on the clock. (Three hand clocks can be d/h/m or h/m/s.)
- tasty_freeze 5y agoThis problem reminds me of another problem. There is a round table and two players, A and B. The players take turns placing a coin on the table in any location they desire, but coins may not overlap. The first person who is unable to place a coin loses. What is the winning first move? Answer: the winning move is for player A to place the first coin in the center of the table. After that, no matter which location player B chooses, player A can always play the 180 degree rotationally symmetric location.
- stevesimmons 5y agoI solved this in a hedge fund interview with "Consider the limiting case of a coin the same size as the table... You can only place it at the centre, and you win... Now make the coin smaller. How does the strategy change?... It can't, because of symmetry." They didn't consider it a valid solution :|
- toxik 5y agoWell, that explanation is a total cop out, so I can see why they would think that.
- Y_Y 5y agoI disagree. Arguments to symmetry like this are found all over the place, especially in the kind of geometry and physics I'm familiar with. In fact the solution I came up with when I read the problem was very similar.
- quietbritishjim 5y agoThe original comment (by tasty_freeze) was an argument to symmetry. Just saying "because of symmetry" is not a proper explanation.
- Y_Y 5y agoYou're right that it's not a proper explanation. This feels just like a case of "details are left as an exercise". This is most frustrating when you're learning a subject, and you want to be able to check the details, or you are skeptical of a claim. Inevitably though people elide things that they think the reader (who they model as similar to themselves) will immediately be able to guess based on their experience. I'm sure you can think of an equivalent situation in your field of expertise.
- Syzygies 5y agoThis same proof technique is the primary method for identifying impossible configurations for the Soma Cube puzzle: https://en.wikipedia.org/wiki/Soma_cube https://en.wikipedia.org/wiki/Soma_cube "Seven pieces made out of unit cubes must be assembled into a 3×3×3 cube. The pieces can also be used to make a variety of other 3D shapes."
- air7 5y agothis is also one of my favorite problems. Though the version that I heard doesn't mention a chess board but rather a general 8x8 (or 10x10) board. I find that this makes the problem even more beautiful because of the initial required insight to color the squares at all and the meaning gaines from it.
- sandgiant 5y agoTypeset PDF in case you don't want to LaTeX-by-eye: https://cloudflare-ipfs.com/ipfs/QmcZf4xuHEvvqrBCv2uhnyQXk5uhvbwdQrWCtjGKWepE8h https://cloudflare-ipfs.com/ipfs/QmcZf4xuHEvvqrBCv2uhnyQXk5u...
- joppy 5y agoWhat? The mathematics shows correctly on the page for me, and that PDF is missing some chessboard images...
- probably_wrong 5y agoA similar argument has been used in the more-or-less famous proof of how to assemble a lamp with Tetris-shaped components into a rectangle: https://jackmorris.xyz/2015/the-simple-proof-of-the-tetris-lamp/ https://jackmorris.xyz/2015/the-simple-proof-of-the-tetris-l...
- TrackerFF 5y agoI like the infamous Von Neumann "Fly and the trains" math/physics problem - mainly because it's very easy to solve the easy way, or you can go about it the harder way. And apparently Von Neumann did it on the spot, the harder way, almost instantaneous. It goes like this (stolen from a website - there are many variations on this): Problem: Two trains are on the same line, 60 miles apart, heading towards each other, each traveling at 30 mph. A fly that can travel at 60 mph leaves one engine flying towards the other. Upon reaching the other engine, it instantaneously turns around, and heads back to the other engine. This is repeated until the two trains crash and the fly is annihilated at the same time. Question: How far does the fly travel before it is "splatted"?
- cloudyhug 5y agoI'll try it. I hope I do not make a stupid mistake. When the first train has travelled one third of the distance separating it from the other train, the fly will have travelled two thirds of this distance, and the other train one third of the distance, in the opposite way, which means it is exactly the moment at which the fly hits the second train and turns back. Let d be the initial distance between both trains. Now we are solving almost the same problem (the speeds do not change, and the way the fly travels is irrelevant, the problem is symmetric), the only parameter changing is the distance, now being 2/3 * d. We can reason the same way ad infinitum and we identify the distance D travelled by the fly is the following: D = 2/3 d + 2/3 (2/3 d) + ... D = 2/3 d + (2/3)^2 d + (2/3)^3 d + ... D = d * {sum for n from 1 to infinity}{(2/3) ^ n} D = 3d The fly travels 3 times the distance between the trains before dying.
- maest 5y agoIndeed, doing the infinite sum is the "hard" way. The easier way is to notice that the trains will collide in 1h and the fly will be constantly be flying at a speed of 60mph for the entire time. So the fly will travel 60 miles in the alloted time.
- cloudyhug 5y agoIt means I actually made a mistake! I understand your solution. :)
- tromp 5y agoA slightly more involved version of this puzzle asks about covering all but one square of the chess board with 21 trominoes (each of size 3x1 or 1x3), since 64 = 21*3 + 1. What square remains uncovered (unique up to symmetry) ?
- lordnacho 5y agoIt's simultaneously fascinating and frustrating when you run into a problem that suits those criteria. In this case of course the hint is well disguised: if you had an unmarked board you might not think to checker it, but a checkered board is a common thing, so you might not think anything of it when someone presents it as part of the problem. Reminds me of how you find the area under exp(-x^2). Stare at it for a bit and it looks like it can't be done. But if you add another dimension to it, you find the solution. And this is what is both fascinating and frustrating. You could add a lot of things to a problem without making any progress, but there are certain things you can do that make it simple.
- mfgs 5y agoAs a start (and possibly as an equivalent proof?) you can mentally brute force it by cutting the board down to 4x4 and just visualising how the blocks might fit. It quickly becomes obvious that it's not possible.
- aqme28 5y agoWith so many of these "math puzzles," you can usually solve it by cutting it down to a trivial size and scaling it up.
- brianmcc 5y agoI thought this could be about the Monty Hall Problem, which I think is my own personal favourite. It isn't, of course, but I'll share some info here as no one else has raised it so far this thread :-) It's an interesting probability question in its own right, as it has a hugely counter-intuitive correct answer in my opinion. But the sh*storm it caused is equally interesting. Hence I will share this article which covers both aspects: https://priceonomics.com/the-time-everyone-corrected-the-worlds-smartest/ https://priceonomics.com/the-time-everyone-corrected-the-wor... A major takeaway - statistics and probability can be really tough sometimes and even world class practitioners can be caught out when intuition and mathematics clash. And a little humility is perhaps wise when trying to "correct" people, just in case...
- hdjjhhvvhga 5y agoYeah I remember when I heard about it years ago I actually wrote a simple program to show to myself that the second switching actually helps (yes, it does).
- hanche 5y agoThat’s not totally clear, due to the way the problem is often described: As a one-off event, with no clear rules for what the host will do. If there is no clear rule about what the host will do, you are still left in the dark. For example, the host may have decided beforehand (in secret) that he will open another door only if you picked the winning door. In that case, switching will lose you the prize with certainty. But yes, if it is clearly understood that the host always opens another door after you picked one, you should switch.