# Labyrinth

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! Note by Ulyana Dupletsa
6 years, 5 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Restate 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.

- 6 years, 5 months 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?

- 6 years, 5 months ago

Oops! I misread your question. I thought there were $n^2$ vertices, making sides of length $n-1$ cm. Of course, there are $(n+1)^2$ vertices, making a $n\times n$ cm square. Thus the border wall length is $4n$, and a total of $(n-1)^2$ interior vertices, so the total length of the walls is $(n+1)^2$ cm.

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.

- 6 years, 5 months ago

Thank you! Now, I have understood the problem:-)

- 6 years, 5 months ago

You are welcome. Out of interest - which University set the question?

- 6 years, 5 months ago

Scuola Normale of Pisa

- 6 years, 5 months ago

Do we know if there are any cycles (i.e squares with all four sides used)? that could change things...

- 6 years, 5 months ago

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

- 6 years, 5 months ago

Then I see three possibilities as to the intended meaning to the problem, none of which seem to make sense:

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

2. 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.

3. 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.

- 6 years, 5 months 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:-(

- 6 years, 5 months 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.

- 6 years, 5 months ago

I heard several people speak of the need for commercial printers and in-plants to do more self-marketing (Like the cobbler’s children lacking shoes, professional printers tend to put their own messaging last.)

https://printercontactsupport.com/hp-printer-support.html

https://printercontactsupport.com/canon-printer-support.html

https://printercontactsupport.com/epson-printer-support.html

https://printercontactsupport.com/xerox-printer-support.html

- 1 year, 2 months ago

What techniques work for printers to self-promote? Go for open houses and thought leader workshops to entice business. Get active on social media and share useful ideas. Get involved in industry councils and panels. And maybe next year, I’ll see you at Print 19.

https://printercontactsupport.com/kodak-printer-support.html

https://printercontactsupport.com/brother-printer-support.html

https://printercontactsupport.com/lexmark-printer-support.html

https://printercontactsupport.com/samsung-printer-support.html

- 1 year, 2 months ago

As with other brands, we asked how to protect our computer from the Spectre/Meltdown vulnerability, and how to get Cortana to respond to "Hey, Cortana." We also asked a brand-specific question about adjusting the sound presets in the Bang & Olufsen control panel.

https://printercontactsupport.com/dell-printer-support.html

https://printercontactsupport.com/ricoh-printer-support.html

https://printercontactsupport.com/panasonic-printer-support.html

https://printercontactsupport.com/kyocera-printer-support.html

- 1 year, 2 months ago