please empty your brain below
My attempt...

Let's start from Stn (but similar will apply if you start from Enf).

You can only move to Mrt.

If you then move to Lam or Crd, Kng becomes a dead end so you have to move to Kng.

You can only move to Wns.

If you move to Kns or Lam, Rch becomes a dead end so you have to move to Rch.

You can only move to Hms.

If you move to Elg or Kns, Hns becomes a dead end so you have to move to Hns.

You can only move to Hdn and then Elg and then Brt.

If you move to Kns or Cam, Hrw becomes a dead end.

If you move to Hrw, Kns becomes a dead end.

No other moves available and so the problem can't be solved.

Regards

dg writes: I completely agree.

zin92 | 27.11.17 - 9:27 a.m. | #

Not sure if it counts as a proof, but you have to get in and out of each corner, and out (or in) to each of Enfield and Sutton. If you connect them all up, it is impossible to get in and out of Kingston as there is only one connection left to an unused borough, Westminster.

Andrew | 27.11.17 - 9:29 a.m. | #

Oh, pipped. I think I am saying the same thing as zin92.

Andrew | 27.11.17 - 9:30 a.m. | #

First note, as others have done that you have to start at Enfield and finish at Sutton (or vice versa)

Then all you have to do is look at:

Rdb Hvg
Nwm Bar
Grn Bxl

and bear in mind you can't start or finish there.

For Hvg you have to go in via Rdb and out via Bar (or vice versa). Similarly for Bxl you have to go in via Bar and out via Grn (or vice versa). This forces the
Rdb-Hvg-Bar-Bxl-Grn sequence.

There is now only one way in or out of Nwm which forces you to visit Tow twice.

So, not possible.

Pedantic of Purley | 27.11.17 - 9:41 a.m. | #

@pedantic of Purley

I disagree that there's only one way in or out of Nwm. You can go in from either end of the Rdb-Hvg-Bar-Bxl-Grn sequence, and out via Tow.

Mark | 27.11.17 - 9:53 a.m. | #

Isn't this essentially a narrow variant of the Seven Bridges of Königsberg?

Without thinking about this too much, I might expect it to be possible if you skip any one borough adjacent to an odd number of boroughs, leaving an even number of boroughs with an odd number of adjacencies.

Or something. I haven't properly woken up yet and would rather speak in vague sweeping generalities than actually, y'know, put some effort into this.

Chris | Homepage | 27.11.17 - 9:56 a.m. | #

@Chris Almost. In this example we need to pass through each vertex (borough) once rather than each edge (bridge, boundary) once. Hence we need to find a Hamiltonian path rather than an Euler tour(/walk).

As this is a Hamiltonian path problem, there is no rule that states if one can or cannot be found.

It's definitely impossible to do an Euler tour with the diagram DG has got as at least one vertex (that's not the start or end) has an odd number of connections.

robbaker292 | Homepage | 27.11.17 - 9:58 a.m. | #

Mark,

Doh. Of course.

Pedantic of Purley | 27.11.17 - 10:51 a.m. | #

Here's my impossibility proof.

Consider Hdn, which is somewhere in the middle of the path. Going one way from it, you must go Elg - Brt (reason below), and going the other way you must go Hns - Hms - Rch - Wns (same reason). This all leaves Kns with only one neighbour (Wst). QED.

The reason for the "must" in most cases, is that when you arrive adjacent to a 2-neighbour borough, you must step into it, else you will leave that 2-neighbour borough unvisited. (And having stepped, you have only one possible out-move). Of the ones I mentioned, Rch and Kng are 2-neighboured.

(The reason forcing Elg-Brt is the Elg-Hms is impossible as it would isolate Hns).

Malcolm | 27.11.17 - 11:02 a.m. | #

In which case, you can use the argument presented by Mark to argue that in fact you can ignore

Rdb Hvg
Nwm Bar
Grn Bxl

completely since if a solution is possible without them, then a solution will be possible with them by since there must be either a Hck-Tow link or a Tow-Lsh link that can be replaced by Mark's sequence.

Pedantic of Purley | 27.11.17 - 11:03 a.m. | #

I realise I have restated the proof already given by zin92. Summary "it's all about Kingston". Which may have some bearing on the next question.

Malcolm | 27.11.17 - 11:08 a.m. | #

There may be other sticking points, but Kensington is certainly one of them.
This is because, apart from the two end points, every borough must be connected to exactly two others. Finding just one counter-example will be enough to disprove the conjecture that the puzzle can be solved.

Each "corner" has only two neighbours and must be connected to both of them if a path is to be found passing through that borough.
Two of Kensington's four neighbours (Hms and Wns) are each connected to two corner boroughs (Kns/Rmd, and Rmd/Hns), and thus have both their connections spoken for. This means that any route through Kensington must pass from Brent to Westminster.

But Brent has to be connected to Harrow, as the latter is a corner borough. Brent must also be connected to Ealing, as Ealing cannot be connected to Hammersmith (which is connected to two corner boroughs).

Since Brent, Hammersmith nor Wandsworth all have to be connected to two other boroughs, none of them can be connected to Kensington, thereby showing that there is at least one borough (other than the end points) which cannot be connected to exactly two others - QED

timbo again | 27.11.17 - 11:10 a.m. | #

(Apologies if I was misleading people, but I was confusing Kng with Kns. So I meant "If you connect them all up, it is impossible to get in and out of *Kensington* as there is only one connection left to an unused borough, Westminster.")

Andrew | 27.11.17 - 1:11 p.m. | #

Which is what I think three or four other people have said now in slightly different ways :)

Andrew | 27.11.17 - 1:13 p.m. | #

Here's my proof.

First, colour the squares alternately.

the crash location, beneath the bridge, east of St John's

Any route from Enfield to Sutton must go alternately blue/green/blue/green/etc.

There are an odd number of boroughs, so the 33rd borough must be the same colour as the 1st.

But Enfield and Sutton are different colours, so it's impossible.

diamond geezer | Homepage | 27.11.17 - 2:00 p.m. | #

Oh, that is neat. So does it become possible if we move Enfield (or Sutton) one place to the left (or to the right)?

dg writes: Move Sutton one place to the left and yes, it can be done.

Andrew | 27.11.17 - 8:22 p.m. | #











TridentScan v2.10.0 | Privacy Policy