0

A road is constructed with n lines (n>2) sharing exactly one point in the center. There are n cars, each at a unique endpoint.

  • Cars starts facing the center
  • Cars can move forwards and backwards, each considered 1 move.
  • Cars can't pass each other (road to narrow)
  • Cars want to finish at a different endpoint facing away from the center.

Question:

Whats the minimum moves for n cars such that every car end up in a different endpoint than they started with?

I've tried for n=3, for which I got the answer 5. Using rotation (shifted each car clock-wise), since rotation is the only option for n=3, but not for n>3 (you could also swap places etc).

Here is an image:

enter image description here

How would you approach this problem for n>3 and prove it's optimal?

Can you find a general formula for minimum moves of n cars?

Prim3numbah
  • 376
  • Are the lines of length 2? – blomp Feb 25 '24 at 14:41
  • @blomp No, I'll make an edit and fix the lines. – Prim3numbah Feb 25 '24 at 14:46
  • 1
    If you try a few more values of $n$, I think you'll find an efficient general strategy that's fairly clearly optimal. – Karl Feb 25 '24 at 15:26
  • I am unclear on what is allowed for cars to be in the same place at the same time. They cannot pass on the roads, but can they pass at the junction? Can two cars inhabit the same endpoint at a time? If the answer to both of those is "no", then I cannot see any way for the cars to move. A second question is if two cars can move at the same time, as long as they are not on the same section of road. And does that count as one move or two? – Paul Sinclair Feb 26 '24 at 18:57
  • Also, is "1 move" going all the way from one endpoint to another, or from endpoint to center? – Paul Sinclair Feb 26 '24 at 19:05

0 Answers0