0

Thanks in advance for helping me with this routing problem. It's for a digital instrument I'm building, six sine-wave oscillators that feed back into each other in a kind of recursive web.

Here's the mission:

You have six modules. Each module connects to three other modules, and is connected to by three other modules: i.e. each module has three outputs and three inputs. A module never connects to itself, or to the same module $2+$ times. So $1$ might connect to $234$, but not to $123, 233,$ etc.

Here's the hard part:

  1. If module $X$ connects to $Y, Y$ cannot connect back to $X$. If $1$'s output port connects to $2$'s input port, $2$'s output cannot connect back to $1$'s input. So there can only be one connection between a pair of modules.

  2. The connection scheme is a consistent pattern. If $1$ connects to $234, 2$ should connect to $345$, etc. I'm looking for a patterned web of connections between six modules where no module connects to a module that connects back to it.

I don't know if this is possible. Perhaps it's a breeze and I'm just not seeing it. In any case, thanks for your help!

Chiranjeev_Kumar
  • 3,061
  • 16
  • 30
rachMiel
  • 1
  • What do you mean by consistency? Why can't you just complete your current scheme? i.e. 3 -> 456, 4 -> 561, 5 -> 612 and 6 -> 123. Or are feedback loops of length > 2 not allowed, i.e. 1 -> 3 -> 6 -> 1 would cause a problem? – Dominik Aug 11 '15 at 14:50
  • I'm sure there would be those who would downvote this comment to $-\infty$ for suggesting this, if that was possible, but why not write a simple computer program that generates the proposed web of connections (as strings "1->234", say), if there are valid solutions? The space of possible combinations is sufficiently small that computational efficiency and running time wouldn't be much of a problem. I'm all for solving problems and challenges in their full mathematical glory, for many reasons, but sometimes a quick-and-diry program is all that one needs. – wltrup Aug 11 '15 at 14:55
  • Dominik: Thanks! If I used the 1 -> 234 scheme, 1 would go to 4, and 4 would go back to 1 (4 -> 561). – rachMiel Aug 11 '15 at 14:56
  • witrup: How would you get the program to create patterned solutions ... rather than random ones? – rachMiel Aug 11 '15 at 15:03
  • I don't understand what you mean by "patterned" solutions. You have a set of constraints so the program would try every possible assignment in succession, rejecting those that violate any of the constraints. – wltrup Aug 11 '15 at 15:05
  • I mean solutions that have a consistent pattern in terms of what modules each module connects to. This is a consistent pattern 1->234, 2->345, etc. This is inconsistent: 1->234, 2->341, etc. – rachMiel Aug 11 '15 at 15:15

2 Answers2

0

This is impossible. There are $6$ modules, so for each module there are only $5$ other modules, to which a total of $6$ connections are to be made, no two to the same module.

joriki
  • 238,052
  • Sorry, I don't understand. (It's been a looooooooooong time since I brushed up on my math skills.) Try again?

    Also: What is the minimum number of modules needed to make the task doable, 7?

     – rachMiel Aug 11 '15 at 15:16
  • @rachMiel: From any given module, you want to make $6$ connections, $3$ inputs and $3$ outputs. No two of them are supposed to be the same. So you'd need $6$ other modules to connect to in order to establish these $6$ different connections to $6$ different modules. But there are only $5$ other modules, so that's impossible. Yes, $7$ should work. – joriki Aug 11 '15 at 15:19
0

Not possible. Looking at the picture below, you can see that no matter how you assign the integers $\{1,2,3,4,5,6\}$ to the modules (represented by dots), the module marked with an $X$ has no third available module to connect to.

enter image description here

wltrup
  • 3,983