Can Theseus Hide From The Minotaur?

Logic Level 3

Assume a labyrinth layout in the form of chambers. In a certain labyrinth map, there are $m\times m, (m\geq2)$ , chambers in the form of a large square. Now, the chambers were labelled as $1,2,3,\ldots, m^{2}$ , row by row, from left to right. Now, say the Minotaur starts in chamber $1$ . There is a set of rules for the Minotaur to move through chambers, considering that all the chambers are interconnected.

If the Minotaur is in in chamber $n, 1\leq n \leq m^{2}$ and $n\equiv 0 \pmod{4}$ , then move to the chamber in the row above ( $\uparrow$ ).
If the Minotaur is in in chamber $n, 1\leq n \leq m^{2}$ and $n\equiv 1 \pmod{4}$ , then move to the chamber on the right ( $\rightarrow$ ).
If the Minotaur is in in chamber $n, 1\leq n \leq m^{2}$ and $n\equiv 2 \pmod{4}$ , then move to the chamber in the row below ( $\downarrow$ ).
If the Minotaur is in in chamber $n, 1\leq n \leq m^{2}$ and $n\equiv 3 \pmod{4}$ , then move to the chamber on the left ( $\leftarrow$ ).
If the directions lead the Minotaur out of the labyrinth, then the Minotaur will scroll to the chamber on the opposite end of the row or column, depending on the direction in which the Minotaur leaves the labyrinth.
There is no limit to how many times the Minotaur will move.

Say that Theseus is forced to stay in one chamber of the labyrinth. There is a chamber numbered $a$ , such that no matter what value $m$ is (i.e. the dimensions of the square), the Minotaur will never enter this chamber. Find the value $a$ .

I was doodling in my notebook, and realized something interesting.

The answer is 3.

4 solutions

Alessio Rossi
May 16, 2014

With $m = 2$ it's easy to see that $a = 3$ is the answer. Then to find out if it's really the answer I've written a small python script and I've found out that there are just 4 kind of paths:

if $m \equiv 0 \pmod{4}$ then this is the pattern
if $m \equiv 1 \pmod{4}$ then this is the pattern
if $m \equiv 2 \pmod{4}$ then this is the pattern
if $m \equiv 3 \pmod{4}$ then this is the pattern

@Nash Issa , its just a trace of the path that can be followed depending upon the value of $m$ whether $m \equiv 0 \pmod {4}$ , $m \equiv 1 \pmod{4}$ , $m \equiv 2 \pmod{4}$ , or $m \equiv 3 \pmod{4}$ . These cover all the values of $m$ and we see that in none of the cases the path seems to pass through the $3rd$ cell

Gautam Singh - 7 years ago

I dont know anything about this. can anybody help me understand this thing?

Nash Issa - 7 years ago

Correction to the $4^{th}$ bullet. I believe you meant $3 (mod 4)$ .

But the solution is correct.

Nanayaranaraknas Vahdam - 7 years ago

What is mod??

Nivedit Jain - 4 years, 7 months ago

But didn't it say n%4 = (0, 1, 2, 3), not m?

Logan Plumlee - 4 years, 6 months ago

Member Wilcox
Jul 2, 2014

The fast way is to see the minimim m is 2 and they tell you there exists a box that cannot be reached for any m. So just work a 2x2 box by hand and see that it does not get into Box 3 and then you know from the instructions there is no value of m for which it can get into Box 3.

It would be a tougher problem if they then asked you to show why it cannot reach Box 3 for larger values of m, and whether it makes any difference that the maze is square.

The general way is to see that you never reach the third square of the top row because the sequence always begins 1, then 2. As soon as you hit square 2, you move down and out of the top row so not going to hit the 3rd square.

Once you move down, there are four possibilities since the movement is based on a mod 4 calculation. The n value of the box below box 2 is not random however - it is fully determined by your choice of m.

If mod 4 of m is 0, as with a 4x4 matrix, then below Box 2 will be another n=2 and below that another box with n=2 and so on, and you get a vertical stripe.

If the mod 4 of m is 2, as with a 2x2 matrix, then it will be n=0 and quickly you get trapped moving down and up between 2 and 0.

So now the only possibilities of interest are if mod 4 of m is 1 or 3 and you begin moving left or right.

The rules are set so whether n=1 or 3, it directs you right or left and you go back into another box with n=2. And now the box below that one will again have the same n=1 or 3 as before. So you always just move diagonally down-right or down-left until you reach an edge of the maze.

When moving down-right with n=1, you always hit the bottom right corner because the maze is square. But if the bottom right has n=1 then the square just above it must have had n=2, which means the square at the start of the bottom row must be n=3. So you always end up trapped at the bottom row cycling between leftmost (n=3) and rightmost (n=1) boxes. (Note that if the maze had only 2 rows instead of being square then you could reach Box 3.)

When moving down-left with n=3, you always reach n=3 on the leftmost column, then you jump to the rightmost column. What happens then? Well if you had n=3 that must mean that mod m was 1. In that case, for all rows in the maze, the mod4 of n value in the rightmost column is always the same as the leftmost column. So you always hit another case where n=3. And so you will continue downward diagonally left and down until you eventually reach the bottom row and wrap through to the top row again.

Since the maze is square, you always wrap through into box 2 in the top row and there is no chance to hit any box in the top row other than box 2 and thus you will be in an infinite striping pattern down and to the left with wrapping, and you never hit Box 3.

Note that if the maze were not square, for example 4x5 or 8x9, then you do hit Box 3 and so being square is a necessary property.,

Kai Ott
Jul 5, 2016

Answer should be true for all m greater of equal to 2. So the maximum value for a is 4. The minotaur starts in room 1, so the possible values for a are 2, 3 and 4. Brilliant allows 3 guesses, hence you don't even have to think about the possible movements.

Aditya P. Singh
May 16, 2014

Well, this might not be the true solution, but I just took the case of a 2 X 2 square and it's pretty easy to figure out that only the box with m = 3 cannot be entered. So, hence the answer 3.

What about a $3\times 3$ square? Starting in $1$ , going to right, the minotaur reachs the $3^{th}$ chamber

Gabriel Laurentino - 7 years ago

No he doesn't. He goes right (to box 2), down (to box 5), right (to box 6), down (to box 9), right (he wraps to box 7), left (back to box 9), and he's stuck there going back and forth

Stephen Lerner - 6 years, 11 months ago

Can Theseus Hide From The Minotaur?

The answer is 3.

4 solutions

0 pending reports