Secret Communicator Matrix

Notes on possible new logic puzzles

Secret Communicator Matrix

Postby simon_blow_snow » Wed Feb 02, 2011 6:05 pm

During the cold war era, the Soviet scientists used to develop a certain genre of secret communication devices for KGB agents to use within enemy territories.

(Note this was way before the evolution of modern cell phones and handheld computers.)


These devices (for convenience just call them "Secret Communicators" or SCs) had these properties:

1. Each SC had a unique identifier burnt in the internal chip (not unlike the CPU of modern computers).

2. Each SC, depending on their versions, had different capacities to register the identifiers of a number of "partner devices" (PDs). A white SC could register 2 PDs, a blue one 3, a green one 4 and a red SC, the most advanced version, could register up to 5 PDs. Only SCs of the same version could become PDs of each other.

3. Each SC could establish anytime anywhere (within a range of 3000 km) communication to any of its PDs in a special frequency based on the 2 identifiers on each side, which made the communication totally secured from outside parties. Again only SCs of the same version could communicate with each other.

4. Beside the direct communication between 2 PDs, each SC also had the special feature which allowed it to become a "bridge" for any 2 of its registered PDs to communicate with each other. This "bridged communication" must use a single SC as the "bridge", and the 2 communicating SCs must be PDs of that bridge.


Essentially these were the basic properties of those SCs. In every KGB mission, depending on the number of participants, all agents would all carry the same version of SCs with them. It was normally a requirement for each paricipant of a mission to be able to establish direct or bridged communication to all other participants.

After a while it became a subject of interest for KGB to determine how many participants of a mission would each SC version able to support. For example, white SCs (with a limit of 2 PDs) were known to be able to support 5 agents in any given mission. To demonstrate this, one could draw up the "Secret Communicator Matrix" (SCM) like this:


Say 5 agents are A,B,C,D,E, we arrange them as a full circle and each agent will have his immediate neighbours' SCs as PDs of his own SC. So say A can have direct communication with B,E while C can have it with B,D. Then we use "+" to represent a direct communication relationship (and "." as blanks):

Code: Select all
  A B C D E
A . + . . +
B + . + . .
C . + . + .
D . . + . +
E + . . + .


Next, we have to work out the bridged communication relationship. For example, because the SCs of B,E are PDs of A's SC, B,E can have bridged communication with each other. We use "*" to represent this relationship. Also, we use "-" to represent a "self relationship" between each agent and himself:

Code: Select all
  A B C D E
A - + * * +
B + - + * *
C * + - + *
D * * + - +
E + * * + -


As one can see, when the SCM is filled up, it means all participants of the mission can communicate to each other. Otherwise if there are holes, it means a participant cannot communicate to another one, then a higher version of SCs would be necesary to be used in the mission.


To make another demonstration, let's try 8 agents (A,B,C,D,E,F,G,H). This time we show that the blue SCs (with a limit of 3 PDs) are enough to establish communications among everyone. The method is to arrange them in a full circle again and have the SCs of each agent register the SCs of his immediate neighbours as well as his directly opposite agent:

Code: Select all
  A B C D E F G H
A . + . . + . . +
B + . + . . + . .
C . + . + . . + .
D . . + . + . . +
E + . . + . + . .
F . + . . + . + .
G . . + . . + . +
H + . . + . . + .


Then we fill in the bridged communication and self relationships:

Code: Select all
  A B C D E F G H
A - + * * + * * +
B + - + * * + * *
C * + - + * * + *
D * * + - + * * +
E + * * + - + * *
F * + * * + - + *
G * * + * * + - +
H + * * + * * + -


Once again, the SCM is filled up, so everyone can communicate to everyone.


Is it possible to work out all the possible numbers of agents each SC version can support?
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Thu Feb 03, 2011 4:59 am

I will start on the white SCs (WSCs), with a limit of 2 PDs each. As previously demonstrated, WSCs can support 5 agents, and obviously any number lower than 5.

However, it can be proved that WSCs cannot support 6 or more agents. Here is the proof:

For any particular agent, say A, his WSC gives him direct communications to 2 other agents. Each of these 2 agents can have no more than 1 other PD on their WSCs, so A can have bridged communications to a maximum of 2 more other agents. Therefore a WSC only allows A to establish communications with 4 other agents in total. If there are 6 or more agents, at least 1 agent will be "out of reach" from A's standpoint.

Conclusion: WSCs can support communications for 2 to 5 agents but no more.

Also, generalizing this result, SCs with a limit of N PDs can support no more than 1 + N + N*(N-1) = 1+N^2 agents. Therefore:
  • White SCs (WSCs) can support no more than 1+2^2=5 agents.
  • Blue SCs (BSCs) can support no more than 1+3^2=10 agents.
  • Green SCs (GSCs) can support no more than 1+4^2=17 agents.
  • Red SCs (RSCs) can support no more than 1+5^2=26 agents.

However, these are just the upper bounds. In practice is it really possible for say, GSCs to support 17 agents? It will need to be explored.
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby dyitto » Fri Feb 04, 2011 6:35 am

simon_blow_snow wrote:BTW, if you have some spare time, I would like your (and other programming experts') help to my "Secret Communicator Matrix" problem posted in the "Inventors' studio" forum. That problem starts relatively trivially but gets more complicated real quick as the size grows bigger. I think a program will help a lot but I am not that good in programming. So please have a look, thanks!

You could also have asked here in this topic, sooner or later I would have read it.

I doubt it will be 'spare time'.



Actually you're looking for undirected graphs with the following properties:

- No more than a given number n of edges are connected to each of the nodes;
- The distance between any two of all nodes is no more then two steps.

Given n you want to know the maximum number of nodes where these properties hold.

Is this a correct and complete summary?
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: Secret Communicator Matrix

Postby simon_blow_snow » Fri Feb 04, 2011 5:52 pm

dyitto wrote:
simon_blow_snow wrote:Actually you're looking for undirected graphs with the following properties:

- No more than a given number n of edges are connected to each of the nodes;
- The distance between any two of all nodes is no more then two steps.

Given n you want to know the maximum number of nodes where these properties hold.

Is this a correct and complete summary?

Yes it seems graph theory is one possible approach to this problem.

But I am looking for more than simply the maximum number of nodes for each SC versions, but the actual connection arrangements. That's why the matrices.

It will get much more difficult to work out the actual arrangements for more nodes. For example, try to connect 14 GSCs (4 PDs @) altogether. Or 19 RSCs (5 PDs @) altogether. They are not even close to the upper bounds (17 & 26 respectively) but I doubt one can do it manually without the aid of a program. I would love to be proven wrong though!
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Fri Feb 04, 2011 6:05 pm

Last time I did the SCMs for 5 WSCs (2 PDs @) and 8 BSCs (3 PDs @). Let me quickly do 6 BSCs and 7 BSCs:

(From now on I will use "0","1","2" to replace "-","+","*" for easier manipulation.)

For 6 BSCs, arrange them in a circle and each BSC links directly to the two neighbours and the opposite one:

Code: Select all
  A B C D E F
A . 1 . 1 . 1
B 1 . 1 . 1 .
C . 1 . 1 . 1
D 1 . 1 . 1 .
E . 1 . 1 . 1
F 1 . 1 . 1 .


Code: Select all
  A B C D E F
A 0 1 2 1 2 1
B 1 0 1 2 1 2
C 2 1 0 1 2 1
D 1 2 1 0 1 2
E 2 1 2 1 0 1
F 1 2 1 2 1 0


For 7 BSCs, arrange 6 of them (A to F) in a circle like before and then put the remaining one (G) at the centre. A to F links directly to the two neighbours, B,C,E,F links to the opposite one while A,D boih links to G:

Code: Select all
  A B C D E F G
A . 1 . . . 1 1
B 1 . 1 . 1 . .
C . 1 . 1 . 1 .
D . . 1 . 1 . 1
E . 1 . 1 . 1 .
F 1 . 1 . 1 . .
G 1 . . 1 . . .


Code: Select all
  A B C D E F G
A 0 1 2 2 2 1 1
B 1 0 1 2 1 2 2
C 2 1 0 1 2 1 2
D 2 2 1 0 1 2 1
E 2 1 2 1 0 1 2
F 1 2 1 2 1 0 2
G 1 2 2 1 2 2 0


Think this is easy? Now try to answer the following 2 questions:

1. Is it possible to connect 9 BSCs altogether? If yes how? If not why?

2. Is it possible to connect 10 BSCs altogether? If yes how? If not why?
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 05, 2011 12:06 am

[Edit:]

Withdrawn

A bunch of incorrect assumptions which don't help the thread...
Last edited by BryanL on Sun Feb 06, 2011 11:31 am, edited 5 times in total.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 05, 2011 12:37 am

[edit:] More incorrect stuff
Last edited by BryanL on Sun Feb 06, 2011 11:32 am, edited 2 times in total.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Sat Feb 05, 2011 3:44 am

BryanL wrote:The above is not correct. I am no mathematician, but will try and explain it with the maths I know.

First of all, thanks for the response Bryan. It is reassuring that at least someone is interested in this topic and that is great.

However, I find it quite surprising that while you claim that you are no mathematician, you sound so confident in your arguments that my theory is not correct.

Well, the beauty of this problem is, if you think something is not possible, then I can very quickly show you are wrong by providing a working example.

You seem to fall into the (wrong) assumption that lining up the nodes (agents) in a circle and adding additional links is the *only* way to connect them altogether. Well I must say you cannot be more wrong in this. The fact is, there are various ingenious structures to connect the agents together, many of them are out of the range of an ordinary mind and really stretch one's imagination. I will gradually introduce them one by one, hope you will all be patient with me.

BryanL wrote:
2. Is it possible to connect 10 BSCs altogether? If yes how? If not why?

Even worse...

When you said that max x for BSCs was 10, you showed the case for x = 8. It should have been apparent that the matrix was fully populated. But if you had tried to show x = 10 for BSCs, you would have seen that it wasn't possible.

For x : x < max x, x odd or even, there are just more ways of establishing a link between some of the agents.

Interestingly, for the x odd case, at least one agent will have n - 1 direct links but 2n - 1 bridged links.

Okay, then I guess you will be real shocked after studying the following SCM carefully:

Code: Select all
  A B C D E F G H I J
A . 1 . . 1 1 . . . .
B 1 . 1 . . . . 1 . .
C . 1 . 1 . . . . . 1
D . . 1 . 1 . 1 . . .
E 1 . . 1 . . . . 1 .
F 1 . . . . . 1 . . 1
G . . . 1 . 1 . 1 . .
H . 1 . . . . 1 . 1 .
I . . . . 1 . . 1 . 1
J . . 1 . . 1 . . 1 .


Code: Select all
  A B C D E F G H I J
A 0 1 2 2 1 1 2 2 2 2
B 1 0 1 2 2 2 2 1 2 2
C 2 1 0 1 2 2 2 2 2 1
D 2 2 1 0 1 2 1 2 2 2
E 1 2 2 1 0 2 2 2 1 2
F 1 2 2 2 2 0 1 2 2 1
G 2 2 2 1 2 1 0 1 2 2
H 2 1 2 2 2 2 1 0 1 2
I 2 2 2 2 1 2 2 1 0 1
J 2 2 1 2 2 1 2 2 1 0

I will elaborate on this structure later.
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 05, 2011 6:41 am

simon_blow_snow wrote:
BryanL wrote:The above is not correct. I am no mathematician, but will try and explain it with the maths I know.

First of all, thanks for the response Bryan. It is reassuring that at least someone is interested in this topic and that is great.

However, I find it quite surprising that while you claim that you are no mathematician, you sound so confident in your arguments that my theory is not correct.

To tell the truth, after reading your setdoku stuff, I was quite surprised that you could be so wrong - which manifested as a nagging doubt in my mind that maybe I was wrong. But I am happy to put my thinking forward and learn otherwise. If I hadn't, I probably wouldn't have paid enough attention to this stuff and not gained anything...

Well, the beauty of this problem is, if you think something is not possible, then I can very quickly show you are wrong by providing a working example.

You seem to fall into the (wrong) assumption that lining up the nodes (agents) in a circle and adding additional links is the *only* way to connect them altogether. Well I must say you cannot be more wrong in this. The fact is, there are various ingenious structures to connect the agents together, many of them are out of the range of an ordinary mind and really stretch one's imagination. I will gradually introduce them one by one, hope you will all be patient with me.

Hey, Newtonians took a long time to accept relativity.

Okay, then I guess you will be real shocked after studying the following SCM carefully:

Code: Select all
  A B C D E F G H I J
A . 1 . . 1 1 . . . .
B 1 . 1 . . . . 1 . .
C . 1 . 1 . . . . . 1
D . . 1 . 1 . 1 . . .
E 1 . . 1 . . . . 1 .
F 1 . . . . . 1 . . 1
G . . . 1 . 1 . 1 . .
H . 1 . . . . 1 . 1 .
I . . . . 1 . . 1 . 1
J . . 1 . . 1 . . 1 .


Code: Select all
  A B C D E F G H I J
A 0 1 2 2 1 1 2 2 2 2
B 1 0 1 2 2 2 2 1 2 2
C 2 1 0 1 2 2 2 2 2 1
D 2 2 1 0 1 2 1 2 2 2
E 1 2 2 1 0 2 2 2 1 2
F 1 2 2 2 2 0 1 2 2 1
G 2 2 2 1 2 1 0 1 2 2
H 2 1 2 2 2 2 1 0 1 2
I 2 2 2 2 1 2 2 1 0 1
J 2 2 1 2 2 1 2 2 1 0

I will elaborate on this structure later.

As soon as I created a diagram and started filling in the bridged links I could see where it was going...

I must say, that when making this comment above

BryanL wrote:A (perhaps redundant) point on the possible x max agents given nSC, limiting max x. There is more than one bridged path between any two agents A, Z, for n > 2, Z > C. E.g. A can see D through E but can also see D through A - 1.

I was kinda thinking what if there was an arrangement where if the redundancy was removed, so that there was only one way to connect each node or some of them, there could be more nodes / links - and thus more agents for a given n. Not being able to see or conceive another arrangement, I charged on...
Last edited by BryanL on Sun Feb 06, 2011 11:35 am, edited 1 time in total.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Sat Feb 05, 2011 7:33 am

simon_blow_snow wrote:
Code: Select all
  A B C D E F G H I J
A . 1 . . 1 1 . . . .
B 1 . 1 . . . . 1 . .
C . 1 . 1 . . . . . 1
D . . 1 . 1 . 1 . . .
E 1 . . 1 . . . . 1 .
F 1 . . . . . 1 . . 1
G . . . 1 . 1 . 1 . .
H . 1 . . . . 1 . 1 .
I . . . . 1 . . 1 . 1
J . . 1 . . 1 . . 1 .


Code: Select all
  A B C D E F G H I J
A 0 1 2 2 1 1 2 2 2 2
B 1 0 1 2 2 2 2 1 2 2
C 2 1 0 1 2 2 2 2 2 1
D 2 2 1 0 1 2 1 2 2 2
E 1 2 2 1 0 2 2 2 1 2
F 1 2 2 2 2 0 1 2 2 1
G 2 2 2 1 2 1 0 1 2 2
H 2 1 2 2 2 2 1 0 1 2
I 2 2 2 2 1 2 2 1 0 1
J 2 2 1 2 2 1 2 2 1 0

An image is justified here

Image
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Sat Feb 05, 2011 4:14 pm

Bryan, once again thanks for the nice replies. Also thanks for your image, but if I might say there can be a couple of more elegant ways to graphically present this arrangement. (Say, in terms of symmetry and structure.) I am a bit too lazy to actually make the graphics here but hopefully can share some of them later.

To test your understanding so far, try answering this again:

1. Is it possible to connect 9 BSCs altogether? If yes how? If not why?
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Re: Secret Communicator Matrix

Postby BryanL » Sun Feb 06, 2011 7:03 am

simon_blow_snow wrote:To test your understanding so far, try answering this again:

1. Is it possible to connect 9 BSCs altogether? If yes how? If not why?

I spent a little time and tried a few arrangements and came up blank. I won't say it can't be done. If there is a way please enlighten us.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Sun Feb 06, 2011 9:25 am

I am happy to continue with this as there is something to learn. But i am left wondering if you already know the possible orderings or do you genuinely seek some to rattle the cage with to find the possibilities?

I came across a graph called the Petersen Graph which is (I believe) just a reordering of your 10 node BSC with only the direct connections.

Here are the adjacency matrices

Code: Select all
   A B C D E F G H I J
A  . 1 . . . . . . 1 1
B  1 . 1 . . 1 . . . .
C  . 1 . 1 . . . 1 . .
D  . . 1 . 1 . . . . 1
E  . . . 1 . 1 . . 1 .
F  . 1 . . 1 . 1 . . .
G  . . . . . 1 . 1 . 1
H  . . 1 . . . 1 . 1 .
I  1 . . . 1 . . 1 . .
J  1 . . 1 . . 1 . . .

   A B C D E F G H I J
A  0 1 2 2 2 2 2 2 1 1
B  1 0 1 2 2 1 2 2 2 2
C  2 1 0 1 2 2 2 1 2 2
D  2 2 1 0 1 2 2 2 2 1
E  2 2 2 1 0 1 2 2 1 2
F  2 1 2 2 1 0 1 2 2 2
G  2 2 2 2 2 1 0 1 2 1
H  2 2 1 2 2 2 1 0 1 2
I  1 2 2 2 1 2 2 1 0 2
J  1 2 2 1 2 2 1 2 2 0

It leads to a much nicer symmetric diagram with a central node which is what I think you were after.

I can also see that 3d and more is the way to get maximum nodes.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby BryanL » Sun Feb 06, 2011 11:22 am

simon_blow_snow wrote:
dyitto wrote:
simon_blow_snow wrote:Actually you're looking for undirected graphs with the following properties:

- No more than a given number n of edges are connected to each of the nodes;
- The distance between any two of all nodes is no more then two steps.

Given n you want to know the maximum number of nodes where these properties hold.

Is this a correct and complete summary?

Yes it seems graph theory is one possible approach to this problem.

But I am looking for more than simply the maximum number of nodes for each SC versions, but the actual connection arrangements. That's why the matrices.

It will get much more difficult to work out the actual arrangements for more nodes. For example, try to connect 14 GSCs (4 PDs @) altogether. Or 19 RSCs (5 PDs @) altogether. They are not even close to the upper bounds (17 & 26 respectively) but I doubt one can do it manually without the aid of a program. I would love to be proven wrong though!

Maybe it could be shown by the exact cover algorithm whether there is or isn't an arangement for a given n with x agents.

I haven't the time or energy to try and work out the possible rows and constraints. I do however already have the code as it applies to sudoku and it wouldn't be hard to apply it to this problem if someone worked out the constraints. Tarek seemed to do ok with setdoku but never gave enough info for me to follow and I wasn't interested enough to try and nut it out or reinvent the wheel...

One point about exact cover. If it is applicable, then for any solutions it finds, the arrangements will be part of the solution.
BryanL
 
Posts: 247
Joined: 28 September 2010

Re: Secret Communicator Matrix

Postby simon_blow_snow » Sun Feb 06, 2011 7:00 pm

BryanL wrote:I spent a little time and tried a few arrangements and came up blank. I won't say it can't be done. If there is a way please enlighten us.

Okay I will try to type up the lengthy answers for 9/10 BSCs and reveal it soon.

BryanL wrote:I came across a graph called the Petersen Graph which is (I believe) just a reordering of your 10 node BSC with only the direct connections.

Exactly. The Petersen Graph is the unique arrangement for 10 BSCs to connect altogether. Any solution one can come up with must be isomorphic (in Sudoku sense) to it.

BryanL wrote:It leads to a much nicer symmetric diagram with a central node which is what I think you were after.

The one with central node is one possible graphical representation to the Petersen Graph. A more popular representation is to lay them out in two layers of 5 nodes, and connect the outer layer as a pentagon, the inside layer as a pentagram (star pentagon), and then connect the 5 links between corresponding nodes in each layer.

There is also a third graphical representation which resemble a tree structure. That was the one I said I would elaborate later.

BryanL wrote:I can also see that 3d and more is the way to get maximum nodes.

I don't quite understand this statement. Do you mean "3d" as "3-dimentional"? I only think of them in 2-dimensional sense. Of course, many graphs of the connection arrangements are non-planar, but I still try to present them in 2D only.
User avatar
simon_blow_snow
 
Posts: 85
Joined: 26 December 2010

Next

Return to Inventors' studio