1. No worries, take your time.

2. More work than I thought, I think.

3. It's much easier than it looks. Hint:
Take 2 intersecting roads, and 2 travelers. They're both heading towards the crossroads at a uniform speed (not necessarily the same). Draw a line through both travelers. Note the angle it makes with a road, either one. If the two travelers are definitely going to meet at the crossroads, what happens to this angle as they both move forward?

4. Nice. If they're going to meet, their speeds have to be proportional to the distance from the intersection point, so the shrinking triangle maintains its proportionality. The angles stay the same.

5. Yep. There's one more thing to get before the problem's solved. Add one more road to the mix, so you get three meetings and three lines. If you consider that no two meetings can occur at the same time, you should get it.

6. Originally Posted by grapes
Since Coelacanth is on vacation ( )
Well, Coelacanth was away.

7. I have a somewhat different approach to this problem, which is to turn it into a problem in three dimensions, with no moving parts

Each person's trajectory is a line through (x,y,t) space. The idea behind my solution (if it is a solution) is to show that all four people have a line in the same plane, and, since nobody is parallel to anyone else, the lines must intersect. But I need to work through the "proof" and make sure it really is a proof

8. Reason
duplicate

9. Welcome back. The place where I found this problem lists 3-4 solutions. Your approach is used in one of them.

10. Let me try this approach then.

Each person walks at a constant speed. Assuming they are walking on a flat surface, everyone follows a trajectory that is described by a straight line through (x,y,t) space.

The first person meets the second person, and does so only once. Their lines intersect at some (x12,y12,t12), and only at that point. The first person meets the third person once and only once, so their unique point of intersection is (x13,y13,t13). Similarly, the second and third person meet at the unique point (x23,y23,t23).

So here are three points. The three points are distinct, because there is no place where more than two people meet. Furthermore, the three points do not lie in the same straight line, because then all the people would be travelling together at the same rate, which contradicts two conditions in the problem (no one meets more than once, no meeting of three or more people). Three non-collinear points define a plane. So the lines through space-time travelled by the first, second, and third travellers lie in a common place. Furthermore, this place is the unique plane that contains the lines travelled by the first two.

Apply the same reasoning to the first, second, and fourth travellers, and we have that their lines lie in a common plane. But since the plane containing the lines travelled by the first two must be unique, it is the same plane that contains the lines of the first, second, and third travellers. Therefore, the lines of the third and fourth travellers lie in the same plane.

So the third and fourth travellers follow lines through space-time that lie in a common plane. The only way they could not intersect (and therefore that the travellers could not meet) would be if the two lines are parallel. If that were the case, then their paths through space-time could be described as the parameterised lines p3+v*s and p4+v*s, where s is a scalar parameter, and p3, p4, and v are three-dimensional vectors. Then their paths through (x,y) space could be described in the same way - just delete the t coordinate from the three vectors. That would mean the paths (x,y) followed by the two travellers are parallel, contradicting the problem conditions.

So the only use of the non-parallel assumption needed is that the third and fourth travellers do not have parallel paths. I think the non-parallelism of all travellers follows from the other requirements, though.

Does that look right? I think it is correct, but maybe I botched it somewhere. And I do feel it lacks intuition.

11. Relaxing the problem conditions somewhat. All we really need are:

a) All the travellers move in a constant direction, at a constant speed. Either zero of "infinite" speed is possible.

b) There are no co-travellers. It is possible for two travellers to move along the same path, but if so, they must travel at different speeds.

c) The first and second travellers meet everyone.

d) The third and fourth travellers either do not have parallel trajectories, or do not travel at the same speed (moving along parallel trajectories in opposite directions at the same speed is allowed).

I think that does it, and includes some solutions precluded by the original problem. For example, we could imagine everyone walking down the same path, but at different speeds. On person could be stationary, in which case the others must travel along the same path, at different speeds. Some travellers could even move at "infinite" speed, and therefore meet all the other travellers simultaneously at different places.

So I think my "space-time" analysis is slightly more general than the original problem

12. Oops, I forgot the assumption that there is no meeting involving more than two people. We need that. However, I think that obviates the need for the no co-traveller requirement (if the first and second travellers meet everyone, no one can have any co-travellers, or more than two people will meet). So my revised list of requirements is:

a) All the travellers move in a constant direction, at a constant speed. Either zero of "infinite" speed is possible.

b) There is never any meeting of more than two travellers.

c) The first and second travellers meet everyone.

d) The third and fourth travellers either do not have parallel trajectories, or do not travel at the same speed (moving along parallel trajectories in opposite directions at the same speed is allowed).

13. Good work Coelacanth

The problem is called, naturally, the "Four Travelers Problem". I found 5 solutions on another website.
http://www.cut-the-knot.org/gproblems.shtml

14. Originally Posted by Coelacanth
So the third and fourth travellers follow lines through space-time that lie in a common plane. The only way they could not intersect (and therefore that the travellers could not meet) would be if the two lines are parallel. If that were the case, then their paths through space-time could be described as the parameterised lines p3+v*s and p4+v*s, where s is a scalar parameter, and p3, p4, and v are three-dimensional vectors. Then their paths through (x,y) space could be described in the same way - just delete the t coordinate from the three vectors. That would mean the paths (x,y) followed by the two travellers are parallel, contradicting the problem conditions.
Is this a complicated way of saying their projections onto the (x,y) plane intersect?

15. Originally Posted by Coelacanth
For example, we could imagine everyone walking down the same path, but at different speeds. On person could be stationary, in which case the others must travel along the same path, at different speeds. Some travellers could even move at "infinite" speed, and therefore meet all the other travellers simultaneously at different places.
This is excellent!

16. The most elegant solution is Rob Fatland's one: http://www.cut-the-knot.org/4travelers/RobFatland.shtml. It's the one I was giving hints about. Have a look.

17. Originally Posted by PraedSt
Is this a complicated way of saying their projections onto the (x,y) plane intersect?
Probably If the lines are parallel in (x,y,t) space, then there projections onto the (x,y) plane are parallel, which is prohibited - therefore, they must not be parallel in (x,y,t) space. The reverse, if they are parallel in (x,y) space, then they are parallel in (x,y,t) space, does not follow.

Originally Posted by PraedSt
This is excellent!
Many thanks.

Originally Posted by PraedSt
The most elegant solution is Rob Fatland's one: http://www.cut-the-knot.org/4travelers/RobFatland.shtml. It's the one I was giving hints about. Have a look.
In fact, I wouldn't mind if we kept this one open a bit, in case grapes (or anyone else) wants to try an alternate solution. Mine, while I'm pretty sure it's correct, has a bit of an abstract mathematical feel for a problem with such an intuitive feel about it.

Also, I wonder if my last condition in the generalisation of the problem can be improved. The first three are simple and elegant - and then there is the fourth. Blech.

18. Originally Posted by Coelacanth
Also, I wonder if my last condition in the generalisation of the problem can be improved. The first three are simple and elegant - and then there is the fourth. Blech.
You could word it differently. "The third and fourth travelers have different velocities".
ETA: Actually, by using "velocity" you could collapse it further, couldn't you? 4 travelers, each with constant, different velocities. 1 and 2 meet everyone.
Last edited by PraedSt; 2011-Nov-25 at 02:00 PM.

19. Originally Posted by PraedSt
You could word it differently. "The third and fourth travelers have different velocities".
ETA: Actually, by using "velocity" you could collapse it further, couldn't you? 4 travelers, each with constant, different velocities. 1 and 2 meet everyone.
That would definitely simplify it. We still need the condition that no meeting is three or more travellers, though.

The velocities do have to be different, but I think for all but the third and fourth travellers, this can be derived from the other conditions.

20. I should add that Newton vs. relativity makes absolutely no difference at all.

21. I have a problem idea, but I need to make sure I know how to solve it

22. Originally Posted by Coelacanth
That would definitely simplify it. We still need the condition that no meeting is three or more travellers, though.

The velocities do have to be different, but I think for all but the third and fourth travellers, this can be derived from the other conditions.
Four people traveling at constant velocity, 1 and 2 meet everyone. If 3 and 4 aren't on parallel paths, they will meet.

This works even for three-dimensional velocities, since the meetings constrain it to a plane.

23. Originally Posted by grapes
Four people traveling at constant velocity, 1 and 2 meet everyone. If 3 and 4 aren't on parallel paths, they will meet.
Still need the no-three-people-meeting-simultaneously condition.

Originally Posted by grapes
This works even for three-dimensional velocities, since the meetings constrain it to a plane.
I think it works for four and higher dimensional velocities also

24. OK, C, what's the next problem?

25. Originally Posted by grapes
OK, C, what's the next problem?
I have had extreme difficulty accessing the site (see my signature).

I do have a problem, but I don't know the answer myself, and it is taking me longer than I thought to solve it, so maybe I should think of a new problem. I will try to do that quickly.

26. If you're thinking of submitting the IP problem, I think it is NP complete. From what I've seen.

27. Originally Posted by grapes
If you're thinking of submitting the IP problem, I think it is NP complete. From what I've seen.
Bugger. I'll have to think of a new one then.

I'll try to do it quickly.

28. OK, I don't have time to work out the solution to the problem I want to ask. So I'll ask another.

The domain of this problem is the rational numbers. Prior to my experience at this board and another, I would have thought ideas like rational numbers or real numbers were well understood, but I now realise that is not the case. People using their own homemade number systems may have different solutions to this problem than the one I am looking for.

What number is a perfect square, and remains a perfect square when increased or decreased by 5? In other words, find a value of x such that the square roots of x, x+5, and x-5 are all rational numbers.

29. X = 4.

30. Square root of four is rational (both of them, in fact), and square root of nine also. But I'm not so sure about the square root of -1.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•