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!

#HelpMe!

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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.

Mark Hennings - 7 years, 9 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?