15
$\begingroup$

Anita lives in a city with a peculiar road system: every road is a circle (not necessarily of the same radius). The rules of the system are simple: no sharp turns. That is, if you are at a transversal intersection, you continue on the circle you are on, whereas if you are at a tangential intersection, you have two options, continue on the same circle, or switch to the other circle. The rules, depicted in the figure below, ensure that the motion is always smooth.

depiction of the no-sharp-turns rule at transversal and tangential intersections

One day, Bose, her friend, was visiting her and he wanted a tour of the entire city. Specifically, he was fascinated by the strange road system and wanted to go through all of it. Anita was more than happy to take him around. But she didn’t want to bore him by showing the same sections of the road more than once. Can she always find a way, or is there a road system where this isn’t possible?

Example:

Consider the following system of three circular roads. The blue line shows the path Anita could take through the entire city while taking no sharp turns and avoiding repetitions.

example system of three circular roads and a path that visits all roads and avoids repetitions and sharp turns

Clarifications:

  • The road system is connected, that is, there is a path between any two points that avoids sharp turns.
  • As I said above, the circles need not have the same radius.
  • There could be more than two circles that meet at an intersection. If they all meet tangentially, then that gives more than two options for smooth motion (i.e., no sharp turns).
Improve this question
$\endgroup$
7
  • $\begingroup$ Your blue lines intersect at various points, so that means that you are repeating. Could you clarify your definition of "showing the same sections of the road more than once"? Why do these intersections not count? $\endgroup$ Commented Sep 22, 2025 at 12:07
  • $\begingroup$ @terdon. I see what you mean but a section of the road is not generically a bunch of isolated points. I think the intended meaning is conveyed as can be seen from the answers. $\endgroup$ Commented Sep 22, 2025 at 12:14
  • $\begingroup$ @terdon Boring someone isn't instantaneous - Bose will not "get bored" even if he revisits a finite collection of zero-width points, as he'll still spend zero total duration traversing a section he's already seen. 100% of the tour is spent traversing unseen roads, even when revisiting intersections. $\endgroup$ Commented Sep 22, 2025 at 13:24
  • $\begingroup$ Now one interesting consequence of this arrangement is that there's no way to leave this city to go somewhere else, or enter it from outside... $\endgroup$ Commented Sep 23, 2025 at 8:03
  • $\begingroup$ @DarrelHoffman. Flights, trains, straight roads (infinite radius circles) :P $\endgroup$ Commented Sep 23, 2025 at 12:26

3 Answers 3

Reset to default
12
$\begingroup$

Suppose we begin by

going separately around each circular road. Then we have a set of looping paths that, collectively, pass through each section of road exactly once.

Now suppose

we have such a set of paths, and two distinct paths in the set share a tangency. (Since many circles can be tangent at a single point, they might share it more than once; in that case, just pick one place along each path where it passes through that tangent point.) Each path is a loop; orient them so that they pass through that point of tangency in the same direction. Now, if one goes in through road A and out through road B, and the other goes in through road C and out through road D, we can replace A->B->...->A + C->D->...->C with A->D->...->C->B->...->A and thus combine these two loops.

If we

repeat this process as often as we can, we will end up with a set of looping paths having no common tangencies between distinct paths. This could happen because only one path remains: in that case, we're (successfully) done. Or it could happen because there are multiple paths and no tangent points common to any two of them.

In the latter case

the road system was not, as required, connected. For if you start on one of these loops, nothing you do can ever get you onto another.

So

if the road system is connected, then it is always possible to traverse the whole thing without repetitions in a single journey.

Improve this answer
$\endgroup$
3
  • $\begingroup$ +1. Different from my proof! I like this argument. $\endgroup$ Commented Sep 21, 2025 at 21:02
  • 1
    $\begingroup$ It's nice and clear but rather prosaic. I'd be interested to know how yours works. $\endgroup$ Commented Sep 21, 2025 at 21:16
  • 1
    $\begingroup$ I posted my answer. $\endgroup$ Commented Sep 21, 2025 at 23:32
14
$\begingroup$

Here’s my answer, which is different from @Gareth McCaughan’s answer.

The answer is

Yes, Anita can always do this.

Consider the graph whose vertices are the circular roads, and edges are between vertices whose circles touch (i.e., intersect tangentially). Then the connectedness of the road system is equivalent to connectedness of this graph.

First, let’s assume that this graph is a tree rooted a some vertex p. Let c1, c2, c3, … be its child vertices.

Say the car starts from the position shown in the figure below. When it reaches the intersection with c1, switch to c1. Now repeat this entire procedure for the sub-tree rooted at c1 (the resulting path is shown as dotted blue line). Once we are back at the intersection, we switch back to p and continue along it until we reach the intersection with c2. Repeat this procedure with c2, and so on, until the tour is done.

path taken by the car to complete the tour without repetitions and sharp turns when the graph is a tree

More generally,

pick a spanning tree of the graph and do the above procedure.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This is an easier to understand answer than the other one. Nice one! $\endgroup$ Commented Sep 22, 2025 at 2:58
  • $\begingroup$ What about systems where the graph is not a tree? Examples are easily constructed. $\endgroup$ Commented Sep 24, 2025 at 21:22
  • $\begingroup$ @JohnBollinger. As I said in the answer, pick a spanning tree and the apply the procedure described for a tree. $\endgroup$ Commented Sep 24, 2025 at 22:05
3
$\begingroup$

Given a tangential intersection, the line perpendicular to the tangent line divides the tangent circles into two sides. Sharp turns approach and leave from the same side, and smooth turns approach and leave from opposite sides.

Suppose we have a valid path through the city that makes a sharp turn at some intersection. Both sides of the intersection have the same number of roads, smooth turns visit exactly one road on each side, and sharp turns visit 2 roads on the same side. Therefore, the path must at some point make another sharp turn from the other side of the same intersection.

Consider the section of the path between these two sharp turns. If we reverse the direction of this entire section, then both sharp turns become smooth turns. We therefore obtain another valid path through the city with fewer sharp turns.

Given any valid path through the city, we can repeat this process until all sharp turns have been removed. This means that the original problem is equivalent to finding a valid path without restricting sharp turns.

So, ignoring this restriction, can we always find a valid path through the city? Indeed, using a fundamental result from graph theory.

The road system can be represented as a multigraph with a vertex for each intersection and an edge for each circular arc between intersections. An intersection where n circles meet tangentially is a vertex with degree 2n. Because every vertex has even degree, Euler's theorem guarantees the existence of an Eulerian circuit, which visits every edge exactly once.

Here's a sketch of a proof of the theorem:

Suppose we have a longest path with no repeated edges. Assume for sake of contradiction that this path does not visit every edge. The ending vertex has even degree, so it must be the same as the starting vertex, otherwise it would be incident to some unvisited edge that could extend the path. Because the path is a cycle that starts and ends at the same vertex, we can choose to start from any vertex in the cycle.

Because the graph is connected and the path does not visit every edge, there is some vertex v in the cycle incident to an edge not in the cycle. Then we can obtain a longer path by starting with this edge and traversing the cycle starting from v, contradicting the maximality of the path. Therefore, the path does visit every edge.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I don't think this is quite right, because you aren't allowed to take arbitrary paths through the graph. $\endgroup$ Commented Sep 21, 2025 at 20:52
  • $\begingroup$ @GarethMcCaughan Good catch! Hopefully my new explanation fixes it. $\endgroup$ Commented Sep 22, 2025 at 8:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.