Saturday, June 22, 2019

combinatorics - Draw a line through all doors


I saw the following problem on 4chan and couldn't solve it:


enter image description here


It's very likely to be some kind of troll (no solution).


I'm hoping to see some rigorous proofs that disprove the existence of such a line.




Answer



It is impossible.


Quite the same problem is "Seven Bridges of Königsberg", it was solved (proven) by Euler.




  1. Suppose you have drawn such a line and follow it from one room to another. Since you must use each door you must have a look at each room out of 5. What are these rooms?




  2. There will be 3 (at least) rooms you always go through - if you enter it you always exit it later.
    Indeed, 1 (at most) room you can start at, and another 1 (at most) room you can finish at, but others you must go through: $5-1-1 = 3$.





  3. Since you use each door exactly once, the mentioned 3 rooms must have an even number of doors, since you entry them the same number of times you exit them. But you have only 2 rooms with an even number of doors, the others have 5 doors. So you could not draw such a line.




No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...