Secret.. Aaaaagent Man..

Suppose the country of Matristan has a network of secret agents. These agents may only contact certain other agents directly, according to the following rules:

* Each agent may contact himself or herself directly.
* Agent A may contact agents B and C directly.
* Agent B may contact agents C and D directly.
* Agent C may contact agent B directly.
* Agent D may contact Agents A and B directly.

Here’s the question: What is the least number of intermediate contacts agent C needs to contact agent A?

We can set up a network matrix that simulates these rules…

\mathbf{\Gamma} = \left[ \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{array}\right]

…where matrix position \Gamma_{ij} \geq 1 if agent i can contact agent j, or \Gamma_{ij} = 0 otherwise. Here, i represents the row and j represents the column, contacting agents A through D are represented as rows 1 through 4 respectively, and contacted agents A through D are represented as columns 1 through 4 respectively. So, for example, every agent may contact himself/herself, so \Gamma_{ii} \geq 1 necessarily, for 1 \leq i \leq 4. Another example: since agent B may contact agents B, C, and D, \Gamma_{22} \geq 1, \Gamma_{23} \geq 1 and \Gamma_{24} \geq 1, with \Gamma_{21} = 0 (i.e. agent B who is row 2 cannot contact agent A who is column 1).

How would we answer the problem? Well, each of these agents is contacting another agent in the network. If we assume each agent may contact all other agents at once per round (within our rules), and that each agent passes on messages from agents that have contacted them to agents they are contacting, then we can solve this problem pretty easily.

Take the square of \mathbf{\Gamma}:

\mathbf{\Gamma}^2 = \left[ \begin{array}{cccc} 1 & 3 & 3 & 1 \\ 1 & 3 & 2 & 2 \\ 0 & 2 & 2 & 1 \\ 2 & 3 & 2 & 2 \end{array}\right]

Well, it looks like agent C still can’t contact agent A, because \Gamma_{31} = 0. Multiply by \Gamma again:

\mathbf{\Gamma}^3 = \left[ \begin{array}{cccc} 2 & 8 & 7 & 4 \\ 3 & 8 & 6 & 5 \\ 1 & 5 & 4 & 3 \\ 4 & 9 & 7 & 5 \end{array}\right]

So now, \Gamma_{31} = 1. It took two steps for agent C to contact agent A. Of course, we could’ve found that out by inspecting the original matrix, \mathbf{\Gamma}. Agent C contacts agent B, who contacts agent D, who contacts agent A. Agents B and D are the intermediate agents.

This way is much cooler though.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: