index

The agent 007

russian.htm - russian text,

agent007.zip - all programs,

The task.

The chief of intelligence, where agent 007 serves, has invented the scheme of relative shadowing of the agents

The Agent 001 watches the agent, who watches the Agent 002.

The Agent 002 watches the agent, who watches the Agent 003.

The Agent 003 watches the agent, who watches the Agent 004.

The Agent 004 watches the agent, who watches the Agent 005.

The Agent 005 watches the agent, who watches the Agent 006.

The Agent 006 watches the agent, who watches the Agent 007.

The Agent 007 watches the agent, who watches the Agent 001.

All went normally until the Agent 008 appeared. In this case it became impossible for the chief to make up the similar scheme of relative shadowing for eight agents.

1. What scheme of relative shadowing was at first (whom each agent watches)?

2. Why is the 8 agents scheme impossible?

Solution with the help of the supercompiler.

The initial Java-program:

class Agent007 {
    public static final int nofAgents = 7;

    static class State {
        int[] agents = new int[nofAgents];

        State (int[] agents) {
            for (int i=0; i<nofAgents; i++) {
                this.agents[i] = agents[i];
            }
        }
    }


    public static void main (String args[]) throws Exception {
        int[] agents = { 4, 5, 6, 0, 1, 2, 3};
        checkAndPrint (agents);
    }

    public static void checkAndPrint(int[] agents1) throws Exception {
        int[] agents = new int[nofAgents];

        for (int i=0; i<nofAgents; i++) {
            agents[i] = agents1[i];
        }  

        State s = new State (agents);

        for (int i=0; i<nofAgents; i++) {
            if (  iAgent(s, iAgent(s, i)) != next(i)) throw new Exception();
        }
        
        for (int i=0; i<nofAgents; i++) {
            System.out.println( "The agent 00" + (i+1)  +
                                " watches the agent 00" +
                                (s.agents[i] +1) );
        }
    }

    public static int iAgent(State s, int ia) throws Exception {

        for (int i=0; i<nofAgents; i++) {
            if (s.agents[ia]==i) {s.agents[ia]=i; return i;}
        }

        throw new Exception();
    }
   
    public static int next(int iAgent) {
        if(iAgent==nofAgents-1) return 0;
          else return iAgent+1;
    }

}

For the 8 agents a single change is in the operator nofAgents = 7; requierd.

The outcome of the supercompilation for 7 agents is as follows:

	public static void checkAndPrint (final int[] agents1_1)
	  throws java.lang.Exception
	{
	  final int[] agents_2 = new int[7];
	  final int agents1_0_3 = agents1_1[0];
	  agents_2[0] = agents1_0_3;
	  final int agents1_1_6 = agents1_1[1];
	  agents_2[1] = agents1_1_6;
	  final int agents1_2_9 = agents1_1[2];
	  agents_2[2] = agents1_2_9;
	  final int agents1_3_12 = agents1_1[3];
	  agents_2[3] = agents1_3_12;
	  final int agents1_4_15 = agents1_1[4];
	  agents_2[4] = agents1_4_15;
	  final int agents1_5_18 = agents1_1[5];
	  agents_2[5] = agents1_5_18;
	  final int agents1_6_21 = agents1_1[6];
	  agents_2[6] = agents1_6_21;
	  final int[] agents_34 = new int[7];
	  agents_34[0] = agents1_0_3;
	  agents_34[1] = agents1_1_6;
	  agents_34[2] = agents1_2_9;
	  agents_34[3] = agents1_3_12;
	  agents_34[4] = agents1_4_15;
	  agents_34[5] = agents1_5_18;
	  agents_34[6] = agents1_6_21;
	  if (agents1_0_3 == 0
	  ||  agents1_0_3 == 1
	  ||  agents1_0_3 == 2
	  ||  agents1_0_3 == 3
	  ||  agents1_0_3 != 4
	  ||  agents1_4_15 == 0
	  ||  agents1_4_15 != 1
	  ||  agents1_1_6 == 0
	  ||  agents1_1_6 == 1
	  ||  agents1_1_6 == 2
	  ||  agents1_1_6 == 3
	  ||  agents1_1_6 == 4
	  ||  agents1_1_6 != 5
	  ||  agents1_5_18 == 0
	  ||  agents1_5_18 == 1
	  ||  agents1_5_18 != 2
	  ||  agents1_2_9 == 0
	  ||  agents1_2_9 == 1
	  ||  agents1_2_9 == 2
	  ||  agents1_2_9 == 3
	  ||  agents1_2_9 == 4
	  ||  agents1_2_9 == 5
	  ||  agents1_2_9 != 6
	  ||  agents1_6_21 == 0
	  ||  agents1_6_21 == 1
	  ||  agents1_6_21 == 2
	  ||  agents1_6_21 != 3
	  ||  agents1_3_12 != 0) {
	    throw new java.lang.Exception();}
	  java.lang.System.out.println("The agent 001 watches the agent 005") /*virtual*/;
	  java.lang.System.out.println("The agent 002 watches the agent 006") /*virtual*/;
	  java.lang.System.out.println("The agent 003 watches the agent 007") /*virtual*/;
	  java.lang.System.out.println("The agent 004 watches the agent 001") /*virtual*/;
	  java.lang.System.out.println("The agent 005 watches the agent 002") /*virtual*/;
	  java.lang.System.out.println("The agent 006 watches the agent 003") /*virtual*/;
	  java.lang.System.out.println("The agent 007 watches the agent 004") /*virtual*/;
	  return;
	}
//-----------------------------  11 sec - JScp version 0.1.22

Now we write the answer

The agent 001 watches the agent 005,

The agent 002 watches the agent 006,

The agent 003 watches the agent 007,

The agent 004 watches the agent 001,

The agent 005 watches the agent 002,

The agent 006 watches the agent 003,

The agent 007 watches the agent 004.

The outcome of the supercompilation for 8 agents is as follows:

 
	public static void checkAndPrint (final int[] agents1_1)
	  throws java.lang.Exception
	{
	  final int[] agents_2 = new int[8];
	  final int agents1_0_3 = agents1_1[0];
	  agents_2[0] = agents1_0_3;
	  final int agents1_1_6 = agents1_1[1];
	  agents_2[1] = agents1_1_6;
	  final int agents1_2_9 = agents1_1[2];
	  agents_2[2] = agents1_2_9;
	  final int agents1_3_12 = agents1_1[3];
	  agents_2[3] = agents1_3_12;
	  final int agents1_4_15 = agents1_1[4];
	  agents_2[4] = agents1_4_15;
	  final int agents1_5_18 = agents1_1[5];
	  agents_2[5] = agents1_5_18;
	  final int agents1_6_21 = agents1_1[6];
	  agents_2[6] = agents1_6_21;
	  final int agents1_7_24 = agents1_1[7];
	  agents_2[7] = agents1_7_24;
	  final int[] agents_38 = new int[8];
	  agents_38[0] = agents1_0_3;
	  agents_38[1] = agents1_1_6;
	  agents_38[2] = agents1_2_9;
	  agents_38[3] = agents1_3_12;
	  agents_38[4] = agents1_4_15;
	  agents_38[5] = agents1_5_18;
	  agents_38[6] = agents1_6_21;
	  agents_38[7] = agents1_7_24;
	  throw new java.lang.Exception();
	}
//--------------------------------------  39 sec - JScp version 0.1.22

The answer: the task has no solutions.

It is not meaningful to start up the source program for 8 agents - it will always give out

Exception in thread "main" a java. lang Exception

In lines

for (int i=0; i < nofAgents; i ++) {

if (iAgent (s, iAgent (s, i))! = next (i)) throw new Exception ();

}

there is multiplying substitution to itself and matching of the result to substitution

(0 1 2 3 4 5 6)

Algebraic solution.

Let's write the required scheme of relative shadowing by the way of substitutions on 8 letters. On a condition of the task a^2 = (1 2 3 4 5 6 7 8).

The square of any substitution is an even permutation. The substitution, which was obtained is odd. The inconsistency means impossibility of solution of the second task.

In case of the first task we have a^2 = (1 2 3 4 5 6 7) = b.

The substitution b has property b^7 = e , where e is identical substitution.

b^8 = b, thus b = a^2, therefore it is possible to take a = b^4 = (1 5 2 6 3 7 4).

The answer: