1
$\begingroup$

You have to build a maze whose exit can be changed by a computer. The maze consists of one entrance, hallways which can intersect, and $n$ exits.

The computer has several wires leaving it each controlling a set of gates, which are located in the hallways. All the gates controlled by the same wire must either be all open or all closed at the same time.

In what way should this maze be built so that the number of wires leaving the computer is the lowest possible, while being able to pick any exit?

Clarification: There cannot be more than one exit open at the same time.

Improve this question
$\endgroup$
5
  • $\begingroup$ So, there are $N$ exits, but $X$ gates, where X is however many I want? and exits and gates can be connected however I want? $\endgroup$
    – JonTheMon
    Aug 20, 2015 at 19:02
  • $\begingroup$ @JonTheMon: Yes, you can connect them how you want, and use as many gates as you want. The number of wires (sets of gates which are either all open or closed) must be the lowest possible. $\endgroup$
    – user9771
    Aug 20, 2015 at 19:03
  • $\begingroup$ Are the gates required to be static while you traverse the maze? $\endgroup$
    – 2012rcampion
    Aug 20, 2015 at 19:41
  • $\begingroup$ @2012rcampion: Yes, otherwise you could have just one wire that opens all the doors at once only when you're in front of the correct exit. $\endgroup$
    – user9771
    Aug 20, 2015 at 19:43
  • $\begingroup$ Ok. I had a solution using only two groups that work like a set of locks to ensure that only one exit can be reached with a given sequence. $\endgroup$
    – 2012rcampion
    Aug 20, 2015 at 19:48

3 Answers 3

Reset to default
2
$\begingroup$

Since there is no concept of door-toggling, I'm guessing that the minimum number of wires needed is $2 * Log_2{N}$. Normally this would be a binary choice, where you successively split the exits in half, but you need 2 wires for each split.

-Old-
Based on the stipulation on the wires (All the gates controlled by the same wire must either be all open or all closed at the same time), it looks like you're stuck at $N$ wires.

If any wire connects 2 doors, then both must be open or both must be closed at all times. So, it is impossible to open only one of them. Hence, each door must have its own wire.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Wrong, it's possible to use less than $n$ wires. The gates don't all have to be in front of the exit, they can be inside the hallways. $\endgroup$
    – user9771
    Aug 20, 2015 at 18:51
  • $\begingroup$ @Runemoro Is it always possible to do with less than n wires? $\endgroup$
    – Lampost42
    Aug 20, 2015 at 18:58
  • 1
    $\begingroup$ @Lampost42: Except for $3$ exits or less. $\endgroup$
    – user9771
    Aug 20, 2015 at 19:00
  • $\begingroup$ You almost got it, but the best choice is not $2$ but $3$. $3\log_3(n) < 2\log_2(n)$ as it's the integer closest to $e$, which is the x for which $x\log_x(n)$ is the lowest. (wolframalpha.com/input/?i=minima+x+log+x%28100%29) $\endgroup$
    – user9771
    Aug 20, 2015 at 19:18
  • $\begingroup$ @Runemoro, why did you accept the answer if you were aware that a better one exists? $\endgroup$
    – GentlePurpleRain
    Aug 20, 2015 at 20:17
2
$\begingroup$

The number of wires can be reduced the most by having the hallways form a tree starting from the entrance with one branch ending at each exit. At each layer, each branch of the tree splits into $m$ branches, so we need $m$ wires for each split.

The formula for the number of wires is $m\log_m(n)$. To find the best value for $m$, we need to find the point at which the value of this formula is the lowest:

$ \frac{d}{dm}m\log_m(n) = 0 \\ \frac{ln(m) + 1}{ln(n)} = 0\\ m = e $

Obviously, $m$ must be an integer, so we pick the nearest integer, which is $3$. This gives us that the number of wires for a maze with $n$ possible exits is $3\log_3(n)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This solution is not correct. You can do better by choosing between $2$ and $3$ branches at each level. For example, take $n=5$. This solution chooses two levels of three-way branches (i.e. $\lceil\log_3(5)\rceil=2$) for a total of $6$ doors (and $9$ possible outlets, $4$ of which are unused). However, we can choose one level with $2$ doors and one with $3$ for a total of $5$ doors (and $6$ outlets, only one of which is unused). $\endgroup$
    – 2012rcampion
    Aug 21, 2015 at 22:21
1
$\begingroup$

In general you should build the maze as a binary tree. In the case that the number of exits is an integer power of $2$, then if $2 ^ x = n$ you can get by with $2 x$ wires.

If the number of exits is not a power of $2$, then the smallest number of wires will be $n$ up to $3$ exits, and match $2 x$ where $2 ^ x$ is the next smallest power of $2$ greater than $n$.

NOTE: I posted this before seeing the edit to other solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.