5 ms·

I 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 d

I 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 ago
Does each letter lie in [0,9] or did you mean [1,9]?
- spencerflem 5y ago
  There's 10 letters including J so 0 is allowed
  - bqmjjx0kac 5y ago
    Aha, I can't count, apparently. Thanks!
taeric 5y ago
My favorite in this line is send+more=money.
- Miiko 5y ago
  Mine too, but you cannot solve that one in one tweet, so it does not fit the subject.
vanboxel 5y ago
The "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 ago
  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). 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 ago
    That 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 ago
A 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 ago
  The 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 ago
    The tweet only shows what J is, conditional on that there is a solution.
    - quchen 5y ago
      Isn't that exactly how any constructive proof works?
      - Jeff_Brown 5y ago
        I 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 ago
        A 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

deleted 5y ago

[deleted]

deleted 5y ago

[deleted]

bqmjjx0kac 5y ago

Does each letter lie in [0,9] or did you mean [1,9]?

spencerflem 5y ago
There's 10 letters including J so 0 is allowed
- bqmjjx0kac 5y ago
  Aha, I can't count, apparently. Thanks!

taeric 5y ago

My favorite in this line is send+more=money.

Miiko 5y ago
Mine too, but you cannot solve that one in one tweet, so it does not fit the subject.

vanboxel 5y ago

The "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 ago
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). 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 ago
  That 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 ago

A 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 ago
The 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 ago
  The tweet only shows what J is, conditional on that there is a solution.
  - quchen 5y ago
    Isn't that exactly how any constructive proof works?
    - Jeff_Brown 5y ago
      I 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 ago
      A 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