Oxbridge admission question: how many paths are there between opposite corners of a cube?

This is one of my favourite Maths questions. I encountered it among a list of past interview questions for Oxbridge admissions: how can we get from point A to point B using the edges of the cube, without going over the same edge twice?

pic1

I encourage you to try it yourself first, as getting to the solution gave me another glimpse at the beauty of Maths problem solving. And who knows? Maybe you’ll get to a different solution than the one below…

Now, let’s take a look at my process for coming to a solution. I often look at beautiful solutions and think to myself ‘how on Earth did they come up with that?’ So, I’ll show you my exact steps.

First, we need a way of representing the road we take from A to B. Since we can represent an edge by stating its two endpoints, let’s try to label all the vertices of the cube. The natural way to do that is with the standard 3D Cartesian coordinates.

pic2

As you can see, A is chosen to be the origin of the coordinate system. Also, for ease of notation B was chosen to be the point (1, 1, 1), which can be done without changing the problem (all we are doing is re-scaling the cube to have side length 1 which doesn’t affect the number of paths).

It was at this point my friend remarked that the cube was too hard to visualise on paper, which made me realise that we don’t actually have to visualise it in 3D. The only information we need is how the points are connected together – ie. where we can move to from a given point.

So, picking a random point say (1, 0, 1), where can we move? Looking at the diagram you can see that there are three points connected to this point: (1, 1, 1), (1, 0, 0) and (0, 0, 1). From here it is not too hard to deduce that any two points are connected by an edge if their coordinates are different in exactly one place (only in x, y or z from (x, y, z)). And we can use this to show the lines in a 2D way as follows:

pic3

Next, we need some logic for the way we arrange these points in a diagram. In other words, we need more symmetry in the picture. A cube is very symmetric (48 symmetries in total – can you work them all out?) and so our 2D representation should ideally be more symmetric. This was my second attempt:

pic4

…we can do better than that. The central part in the next one is less jumbled.

pic5

Now we’re getting somewhere. Do you notice something in the middle? The path in blue looks like a crumpled hexagon – what would happen if we unravelled it?

pic6

Much better. I’d say we’re almost at the point where we can start counting the ways to get from A to B, we just have a couple of little problems to iron out…

First, B is not symmetrical in the picture. Sure, you could say this is only an aesthetic thing, but symmetry in Maths often helps us to solve things more easily so let’s try to fix it. One idea would be to add 3 ‘B’s into the picture – one for each of the nodes connected to it. But, thinking about this a little deeper, we see that because the path has to end at B – and once we are there we cannot go back – then in fact B does not need to be connected to the rest of the picture. Instead, we can just draw some EXIT signs at the nodes connected to B. Once you reach one of these points, you have two choices: either “exit” the picture through a B (only one way to do that: move to B from that point), or continue along the hexagon. This observation will be very helpful when it comes to counting paths.

Second, we are not quite sure where to go from A. There is no obvious choice for a starting move. From A to… which of the three? Thankfully, due to the symmetry of the picture (and of the problem, of course), we can simply count the ways to get from A to B with the first move being ‘A to (0, 0, 1)’ and then multiply by 3 to get the result. So, let’s do exactly that!

Given our new-found knowledge, we can make very useful simplifications to the picture. Firstly, the line from A to (0, 0, 1) can be replaced simply by an ENTRY sign at (0, 0, 1), since that is our starting move (which we do in exactly one way). Secondly, since we cannot use that first line anymore, we can simply remove it.

pic7

Now things are really starting to take shape. In this form we see that the line through the point A is equivalent to just going from (1, 0, 0) to (0, 1, 0) or the reverse (once we are in A, we cannot go back to where we came from), and so we can simply delete the point A. Also, for neatness, let’s rotate the whole diagram 60 degrees clockwise.

pic8

Perfect! I’d say we are now in a position to start counting paths – remembering that we have to multiply by 3 at the end because of the symmetry of the first move. In fact, looking at our much simplified – and very symmetric – diagram, it becomes apparent that we can also count all of the paths that start by going from the ENTRY POINT to (1, 0, 1) and then multiply by 2 at the end. I told you symmetry was going to be helpful!

The following picture should help with the counting:

pic9

It perhaps looks a little complicated so let’s break it down. Following all the arrows, or doing it on your own, you can hopefully see that by going through an edge once and starting as decided above (ENTRY to (1,0,1)), we have the following:

  • one way to get to the (1, 0, 1) EXIT
  • two ways to get to the (1, 1, 0) EXIT (ah, that pesky purple arrow!)
  • two ways to get to the (0, 1, 1) EXIT (either only on the hexagon, or using the shortcut).

In total, with the chosen start, we have 5 ways to get from A to B. But, don’t forget we need to multiply due to the symmetries that we’ve used to simplify the problem. First, multiply by 2 (we can go to (0, 1, 1) instead of (1, 0, 1) starting from (0, 0, 1)) and get 10 ways. And then multiply by 3, the number of ways to choose an ENTRY point. Thus, the actual total is 30.

ANSWER: 30 Ways to get from A to B!

Whilst we take a well-deserved moment to pat ourselves on the back for getting the right answer, let’s look at some things to take away from this problem.

  1. Even if you are asked about a cube in a problem, you mustn’t get stuck on the idea of a cube. Maths is flexible that way. You can model your cube into any other structure that keeps the important elements in place. In our case, only the ways in which the vertices were connected mattered, not the angles between the lines or anything. Thus, a graph was a fairly good choice.
  2. You can sometimes make use of the symmetry of a problem to make your life easier, as we did with the way we counted the total number of paths. Symmetry plays a very important role in Mathematics, so keep an eye out for it.

I hope you enjoyed my solution and best of luck with your own Maths problems! If you want to discuss something, leave a comment below – this place is always open to interesting solutions or remarks.

The original version of this article can be found here.

Vlad Tuchilus

Numberphile: Where Does River Water Go?

The third video in the fluid dynamics trilogy I made for Numberphile. Rivers contain 80% of pollution which ends up in the ocean, so understanding where the water goes when it leaves the river mouth is of upmost importance in the fight to clean-up our planet.

Watch part 1 on the Navier-Stokes Equations here

Watch part 2 on Reynolds Number here.

Stopping the spread of oil pollution using Maths

Following the Deepwater Horizon oil spill in 2010, scientists at the University of Cambridge have been studying underwater plumes to try to understand how the Earth’s rotation affects the spread of oil. Their experiments revealed the important role played by conservation of angular momentum after one rotation period, emphasising the importance of a rapid response to a disaster.

This video is part of a collaboration between FYFD and the Journal of Fluid Mechanics featuring a series of interviews with researchers from the APS DFD 2017 conference.

Sponsored by FYFD, the Journal of Fluid Mechanics, and the UK Fluids Network. Produced by Tom Crawford and Nicole Sharp with assistance from A.J. Fillo.

Brazil Nut Effect in Avalanches and Cereal

The brazil nut effect describes the movement of large particles to the top of a container after shaking. The same effect also occurs in avalanches where large blocks of ice and rocks are seen on the surface, and in a box of cereal where the large pieces migrate to the top and the smaller dusty particles remain at the bottom. In this video, Nathalie Vriend and Jonny Tsang from the University of Cambridge explain how the granular fingering instability causes granular convection and particle segregation, with examples of experiments and numerical simulations from their research.

 

This video is part of a collaboration between FYFD and the Journal of Fluid Mechanics featuring a series of interviews with researchers from the APS DFD 2017 conference. Sponsored by FYFD, the Journal of Fluid Mechanics, and the UK Fluids Network. Produced by Tom Crawford and Nicole Sharp with assistance from A.J. Fillo.

WordPress.com.

Up ↑