Tuesday, March 21, 2023

The Newark bridge problem

MosaicCreative ContentThe Newark bridge problem

Staff Reporter

As finals season winds down to a close, thousands of seniors will be leaving the university and moving on to the next chapter of their lives. In this article, I will attempt to provide a way for seniors to take a walk down memory lane — literally.

During your time at the university, you may have noticed that the brick paths on the Central Green are arranged in a seemingly arbitrary way. Have you ever wondered if it is possible to walk along every path on the green, using each path exactly one time?

Neither have I, but let’s figure it out anyway. 

To answer the question we need to visualize all of the paths. A good way to do this is with a graph. A graph represents relationships between objects. 

In the picture on the left, the paths on the green correspond to the black lines (edges). The dots, which are called vertices, are the junctions at which the path forks. The junction at the bottom is directly in front of Memorial Hall.

Does that actually help us though? 

With a basic idea of what might prevent us from using all of the paths, it does. Observe that each blue junction is connected to an odd number of paths.

Consider this junction connected to three paths. The blue arrows represent the direction you walk going in, and the red arrows represent the direction you walk going out. Since you can only walk down a path once, once you go into a junction, you can’t go back the same way. 

So if you tried to use every path near a junction with exactly three paths, you would inevitably run out of paths to get out. As you can see, this is an issue. Sadly, this means that it is not possible to use all of the paths.

But what if you were to ignore some of the paths?

We’ve established that a junction connected to three paths causes trouble. It turns out to be the case that any junction with an odd number of paths, all of the ones in blue, causes trouble.

Notice that every blue junction shares a path with another blue junction (see blue dashed lines). In addition, each blue junction has either one or three paths going to another blue junction. After removing those paths, each blue junction is left with an even number of paths and so all of the junctions are left connected to an even number of paths.

While it is probably not immediately clear that this means we can walk down all of the remaining paths exactly one time each and still end up back at Memorial hall, it is true. 

Can you figure out how?

(Redundant junctions have been removed)




Please enter your comment!
Please enter your name here

Check out our other content

Check out other tags:

Most Popular Articles