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.

  • $\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 '15 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 '15 at 19:03
  • $\begingroup$ Are the gates required to be static while you traverse the maze? $\endgroup$ – 2012rcampion Aug 20 '15 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 '15 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 '15 at 19:48

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.

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.

  • $\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 '15 at 18:51
  • $\begingroup$ @Runemoro Is it always possible to do with less than n wires? $\endgroup$ – Lampost42 Aug 20 '15 at 18:58
  • 1
    $\begingroup$ @Lampost42: Except for $3$ exits or less. $\endgroup$ – user9771 Aug 20 '15 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 '15 at 19:18
  • $\begingroup$ @Runemoro, why did you accept the answer if you were aware that a better one exists? $\endgroup$ – GentlePurpleRain Aug 20 '15 at 20:17

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)$.

  • $\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 '15 at 22:21

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy