Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Favorite Math Problem

mapehe.github.io

Post reply on HN
Print view View original

41–50 of 86 posts

Re: My Favorite Math Problem

#41

Post by Y_Y »

toxik wrote: post #38
stevesimmons wrote: post #36

Earlier quoted context omitted.

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

Well, that explanation is a total cop out, so I can see why they would think that.

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

Re: My Favorite Math Problem

#42

Post by Miiko »

taeric wrote: post #15
antognini wrote: post #4

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.co…

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

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

Re: My Favorite Math Problem

#43

Post by kazinator »

gopalv wrote: post #28
antognini wrote: post #4

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.co…

> 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/a953450ac64b686854…

I'm trying it with this TXR Lisp, just for fun. It uses an implementation of John MacCarthy's amb operator based on delimited continuations, which are slow.

  (defmacro amb-scope (. forms)
    ^(block amb-scope ,*forms))

  (defun amb (. args)
    (suspend amb-scope cont
      (each ((a args))
        (whenlet ((res (and a (call cont a))))
          (return-from amb-scope res)))))

  (defmacro 0-9 () '(amb 0 1 2 3 4 5 6 7 8 9))

  (defmacro val (p q r) ^(+ (* 100 ,p) (* 10 ,q) ,r))

  (compile-only
    (amb-scope
      (let* ((A (0-9)) (B (0-9)) (C (0-9))
             (D (0-9)) (E (0-9)) (F (0-9))
             (G (0-9)) (H (0-9)) (I (0-9))
             (J (0-9)))
        (amb (and (eql (+ (val A B C)
                          (val D E F)
                          (val G H I))
                       (+ 1230 J))
                  (eql 1023 (mask A B C D E F G H I J))))
        (prinl (list A B C D E F G H I J)))))
Every amb expression says: "I denote my leftmost non-nil argument which makes the remaining computation successful".

The "remaining computation" is the future computation up to returning a value from the enclosing amb-scope form. The amb-scope form succeeds if it yields a non-nil value.

We use amb to ambiguously bind A, B, C, ... to all the values from 0 to 9, amb magically selects the successful value for each one.

We also use amb to express assertions. If we assert (amb (eq 'day 'night)) then that fails: night is not day.

We simply assert the desired conditions over the variables. If there is any way for the conditions to be true, then that means there exist successful values for the variables and so all the prior ambs choose those successful values.

  This is the TXR Lisp interactive listener of TXR 272.
  Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
  Upgrade to TXR Pro for a one-time fee of learning Lisp!
  1> (compile-file "abcprob")
  t
  2> (load "abcprob")
  (0 1 2 3 4 5 8 7 9 6)
  nil
Thus

     012
     345
     879
    ----
    1236
The "all letter digits unique" is efficiently met using bits to represent a set. TXR Lisp has a mask function which calculates an integer whose binary representation has a 1 in the positions indicated by the arguments. E.g (mask 0 2) yields 6, and (mask 0 1 2) yields 7.

If mask is given 10 unique digit values---the complete set---it must produce the value #b1111111111 or 1023, the complete set mask.

We thereby avoid n squared silliness like (and (neql A B) (neql A C) ...): asserting that no letter pair is equal.

Re: My Favorite Math Problem

#44

Post by cloudyhug »

TrackerFF wrote: post #40

I 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, ea…

I'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.

Re: My Favorite Math Problem

#45

Post by maest »

antognini wrote: post #4

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.co…

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.

Re: My Favorite Math Problem

#46

Post by maest »

cloudyhug wrote: post #44
TrackerFF wrote: post #40

I 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, ea…

I'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…

Indeed, 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.

Re: My Favorite Math Problem

#47

Post by cloudyhug »

maest wrote: post #46
cloudyhug wrote: post #44

Earlier quoted context omitted.

I'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…

Indeed, 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.

It means I actually made a mistake! I understand your solution. :)

Re: My Favorite Math Problem

#48

Post by dmurray »

cloudyhug wrote: post #47
maest wrote: post #46

Earlier quoted context omitted.

Indeed, 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.

It means I actually made a mistake! I understand your solution. :)

Yeah, the distance changes by a factor of 1/3 each time (which actually makes for an easier infinite sum), not 2/3.

Re: My Favorite Math Problem

#49

Post by j7ake »

TrackerFF wrote: post #40

I 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, ea…

I think the problem here is posed in a way where there is a simple trick (because the fly flies exactly 2 times faster than one of the trains).

From the reference of a train, the other train is coming at 60 mph, which is equal to the speed of the fly.

So the problem would be equivalent to having the fly be stuck on the windshield of a 60 mph train until it collides with a train at 0 mph.

It takes 1 hour to move 60 miles at 60 mph. So the fly flies 60 miles.

If I recall in the original problem the fly flies at a different speed compared to the train (relative to the driver of the train), just to make it conceptually a little harder.

Re: My Favorite Math Problem

#50

Post by dmurray »

brennanpeterson wrote: post #25
mcphage wrote: post #9

This 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.

I am curious. Are all boards that have equal white and black tiles counts solvable?

Yes, 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

Post reply on HN