There is this math problem from a university entry test I find interesting, but have some difficulty with. An integer n is given and there is a sheet of paper which is formed by n^2 squares with side of 1cm. We can draw a labyrinth with the following properties: a) the walls of the labyrinth are sides of the squares and contain the borders of the sheet; b) starting from any point on a side of the labyrinth you can arrive to the border of the sheet, moving along the sides of the labyrinth; c) any point of the labyrinth can be reached from any other point; d) every square 2x2 contains at least one side of the labyrinth inside The problem requires to prove that the total lenght of the sides of the labyrinth does NOT depend on the shape of the labyrinth. Thank you!

## Comments

Sort by:

TopNewestRestate the labyrinth conditions in terms of the vertices.

There is a wall inside every \(2\times2\) square, so every one of the \((n-2)^2\) interior vertices in the \(n\times n\) array is attached to a wall.

We can get from any part of the wall to the border of the sheet, so there is a path of walls from every one of the \((n-2)^2\) interior vertices to the border.

Any point on the labyrinth can be connected to any other point, so there must be exactly one route, following walls, from any interior vertex to the border. Otherwise two routes from an interior vertex to the border would divide the labyrinth up into non-communicating sections.

For any interior vertex \(v\), let \(d(v)\) be the distance in cm of the wall length from \(v\) to the border. Since there is only one route from any interior vertex to the border, the distance \(d(v)\) is well-defined for all interior vertices \(v\).

Every vertex \(v\) with \(d(v)=1\) can be connected to the border by adding a single wall.

Every vertex \(v\) with \(d(v)=2\) must be connected to one of the vertices \(w\) with \(d(w)=1\) by a single wall.

Every vertex \(v\) with \(d(v)=3\) must be connected to one of the vertices with \(d(w)=2\) by a single wall.

Keep on adding vertices for \(d(v) = 4,5,\ldots\), until all interior vertices have been connected. At each stage, a single wall is added to connect one new vertex to the collection of vertices already connected to the border, and there is only one choice (for any labyrinth satisfying these conditions) for the wall that has to be added to attach each vertex. Every new vertex to be attached needs a new wall.

Thus the labyrinth will consist of the four boundary walls, each of length \(n-1\) cm, and a total of \((n-2)^2\) extra walls, each of length \(1\) cm, which are used to connect the interior vertices to the border. Thus the total length of the walls of the labyrinth is \[ (n-2)^2 + 4(n-1) \; = \; n^2 \mbox{ cm.}\] If the labyrinth was based on an \(m \times n\) rectangle, the same argument would give you labyrinths of total wall length \(mn\) cm. – Mark Hennings · 4 years ago

Log in to reply

– Ulyana Zamishka · 4 years ago

Thank you so much for your help! I have just one question. Why did you wrote that the boundary walls have lenght of (n-1)cm each and not just n cm?Log in to reply

if the original array was \(m \times n\) cm, there there would be a border wall of length \(2(m+n)\) and a total of \((m-1)(n-1)\) interior vertices to be connected by adding walls, making a total wall length of \((m+1)(n+1)\) cm. – Mark Hennings · 4 years ago

Log in to reply

– Ulyana Zamishka · 4 years ago

Thank you! Now, I have understood the problem:-)Log in to reply

– Mark Hennings · 4 years ago

You are welcome. Out of interest - which University set the question?Log in to reply

– Ulyana Zamishka · 4 years ago

Scuola Normale of PisaLog in to reply

Do we know if there are any cycles (i.e squares with all four sides used)? that could change things... – Matthew Lipman · 4 years ago

Log in to reply

– Mark Hennings · 4 years ago

There cannot be a cycle, since that would mean you could not walk the labyrinth from a point inside the cycle and reach a point outside the cycle.Log in to reply

– Ulyana Zamishka · 4 years ago

It's not specified in the text of the problem!:-(Log in to reply

That was implied. Counterexample: let every square have top and bottom used and add border. Now add a random vertical edge.

The phrase total length of the sides of the labyrinth meant outside perimeter. This is just immediate from the fact that the edges of the paper are used.

They meant exactly what they said, which is obviously false. Counterexample: take all sides of the square. This satisfies the constraints. Now remove one random edge. Less length, but still valid.

Can you put the exact wording up? I think that might clarify my concern. – Matthew Lipman · 4 years ago

Log in to reply

– Ulyana Zamishka · 4 years ago

I'm afraid I can't put the exact wording since the original text is in italian and I did what I could to translate it. I found the problem contraddictory too, but unfortunately no solution was posted by the university and I do not know where to find any clarifications:-(Log in to reply