Two Spies

If N is 3|s1-s2| = 1 It seems like there is some kind of pattern here.
If N is 4 |s1-s2| = 3
If N is 5 |s1-s2| = 2
If N is 6 |s1-s2| = 4
If N is 7 |s1-s2| = 3
If N is 8 |s1-s2| = 3
If N is 9 |s1-s2| = 6
If N is 10 |s1-s2| = 6
If N is 11 |s1-s2| = 5
If N is 12 |s1-s2| = 5
If N is 13 |s1-s2| = 5
If N is 14 |s1-s2| = 9
If N is 15 |s1-s2| = 9
If N is 16 |s1-s2| = 7
If N is 17 |s1-s2| = 7
If N is 18 |s1-s2| = 7
If N is 19 |s1-s2| = 7
If N is 20 |s1-s2| = 7
If N is 21 |s1-s2| = 15
If N is 22 |s1-s2| = 14
If N is 23 |s1-s2| = 14
If N is 24 |s1-s2| = 10
If N is 25 |s1-s2| = 10
If N is 26 |s1-s2| = 10
If N is 27 |s1-s2| = 10
If N is 28 |s1-s2| = 10
If N is 29 |s1-s2| = 10
If N is 30 |s1-s2| = 10

Hmm, surely sometimes S1 is Bigger than S2 and Sometimes its the other way round, so sometimes the difference should be negative and sometimes positive?

Originally posted by iamatiger
Hmm, surely sometimes S1 is Bigger than S2 and Sometimes its the other way round, so sometimes the difference should be negative and sometimes positive?

That is why it is |s1-s2| or the absolute value of s1-s2.

Originally posted by tomtom232
Couldn't we just graph the positions of each spy for ever number and then use the graph to create two formula's for each "spy line?"

ex x is the amount of people in the group and y is the position of each spy.
8| s(4,8) S(7,8)
7|
6|s(1,6) S(5,6)
5| s(2,5)S(4,5)
4|s(1,4) S(4,4)
3|s(1,3)S(2,3)
2|
1|
0|------------------ ...[text shortened]... l people in the group?
Maybe there is a pattern in the amount of people between each spy.

there is no function here but this is probably because I am mapping poorly?

Hmmmm
If you look at the number of people (N) where a spy steps backwards some number (rather than forwards by 3) these numbers of people are:

reset num 1 reset 2 reset
1 5 4
2 7 6
3 11 9
4 16 14
5 24 21
6 36 31
7 54 47
8 81 70
9 122 105
10 183 158
11 274 237
12 411 355

Spy 1 reset points are very nearly equal to 3.1677195 * 1.5^X where X is the reset number

Spy 2s reset points are very nearly equal to 2.7361081 & 1.5^x

It suspicious that they are both so proportional to 1.5^x

On each move, the spy shuffles forward 3, and two are moved off the end. The chain is now N+1 long, and the spy is 2 positions closer to the end.
So, on each move the spy gets 2 positions closer to the end. If his distance to the end is odd, it will always be odd, and if it is even it will always be even (on this run)

So, distance from spy at end on Switch = N-S (S is the spy position at the switch)

If this distance is even, then the spy will end up in last position (0 from the end).
If this distance is odd, the spy will end up second from last position (1 from the end)

The even spy will be in last position after (N-S)/2 moves when the chain is (3N-S)/2 long

The odd spy will be in second to last position after (N-S-1)/2 moves when the chain is (3N - S - 1)/2 long

On the next move after this:
The even spy will be at position 2, with a chain (3N-S)/2 + 1 long
The odd spy will be at position 1 with a chain (3N-S-1)/2 + 1 long

Have to go to work now, but that's how I'm thinking at the mo.

Talzamir - Do you know if this has a solution for any N?

(other than some program like)

Solution for 3 = "12X" (1 = pos of spy 1, 2 = pos of spy 2)

Solution for N+1 = right(sol_n,2)&"X"&left(sol_n,len(sol_n)-2)

You get a very interesting pattern if you write down the pattern twice on each line, starting 3 spaces further back each time:

using A for spy 1, B for spy 2, X for martyr, and S as a spacer to keep everthing in line

SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSABXABX
SSSSSSSSSSSSSSSSSSSSSSSSSSSBXXABXXA
SSSSSSSSSSSSSSSSSSSSSSSSXAXBXXAXBX
SSSSSSSSSSSSSSSSSSSSSBXXXAXBXXXAX
SSSSSSSSSSSSSSSSSSAXXBXXXAXXBXXX
SSSSSSSSSSSSSSSXXXAXXBXXXXAXXBX
SSSSSSSSSSSSBXXXXXAXXBXXXXXAXX
SSSSSSSSSXXXBXXXXXAXXXBXXXXXA
SSSSSSXAXXXXBXXXXXAXXXXBXXXX
SSSXXXXAXXXXBXXXXXXAXXXXBXX
XXXXXXXAXXXXBXXXXXXXAXXXXB

Originally posted by iamatiger
On each move, the spy shuffles forward 3, and two are moved off the end. The chain is now N+1 long, and the spy is 2 positions closer to the end.
So, on each move the spy gets 2 positions closer to the end. If his distance to the end is odd, it will always be odd, and if it is even it will always be even (on this run)

So, distance from spy at end on S ...[text shortened]... a chain (3N-S-1)/2 + 1 long

Have to go to work now, but that's how I'm thinking at the mo.

Ok, let us consider a single spy, and break the wrap around positions into 4 possibilities:
A) Spy is at position 1 and there is an odd number in the chain
B) Spy is at position 2 and there is an odd number in the chain
C) Spy is at position 1 and there is an even number in the chain
D) Spy is at position 2 and there is an even number in the chain

A spy is an even spy if he is an even number of positions from the end. As we have already proved, on the next switch such a spy ends up at position 2, with a chain (3N-S)/2 + 1 long, where N is the initial number of people in the chain, and S is the position of the Spy.

A spy is an odd spy if he as an odd number of positions from the end. On the next switch such a spy ends up at position 1 with a chain (3N-S-1)/2+1 long.

So, for each of the possibilities above:
if A), this is an even spy, the next switch spy position will be 2, and the next switch chain length will be (3N-1)/2 + 1 long, which simplifies to 1.5N+0.5

If B), this is an odd spy, the next spy position will be 1, and the next chain length will be (3N-3)/2+1 long, which simplifies to 1.5N-0.5

if C), this is an odd spy, the next spy position will be 1 and the next chain length is an will be (3N-2)/2+1.which simplifies to 1.5N

if D), this is an even spy, the next spy position will be 2, and the next chain length will be (3N-2)/2 + 1 long, which simplifies to 1.5N

So that shows why there is a long range pattern in these switch lengths of K*log(1.5), whichever the state, the next state is about 1.5 times longer. However there is no obvious mapping to the next state A,B, C or D. Thoughts continue.

The first 83 switch states for spy one, up to the point where my spreadsheet can't represent the numbers precisely, with him in position 2 of a chain 871897780498214
men long (about 125,000 times the population of the world) are:

ABABCCCCADBCABADDBCCABADBCCCCCABCADDBCADBCADDDBADBADDDDBCABCCABCABABABADDBCABCADBAB

I can see no sign at all of any ordering, therefore I am starting to think that writing a non-recursive formula for the spy position at any position is impossible, although we can get to the nearest switch state and skip forward the right amount with a fairly short program.

Here is a program implementing the recursive mod method and my switch states method:


use strict;
use warnings;
use Time::HiRes qw( gettimeofday tv_interval);


while () {
print "Input number of resistance fighters, '0' to exit \n";
chomp (my $num_fighters = <> ) ;
last unless $num_fighters;

my @start_time = gettimeofday;
my ($spy_1_pos, $spy_2_pos) = recursive_modulus($num_fighters);
my $elapsed_time = tv_interval(\@start_time);

print "Recursive Modulus got $spy_1_pos and $spy_2_pos in $elapsed_time seconds\n";

@start_time = gettimeofday;
($spy_1_pos, $spy_2_pos) = switch_states_method($num_fighters);
$elapsed_time = tv_interval(\@start_time);
print "Switch States Method got $spy_1_pos and $spy_2_pos in $elapsed_time seconds\n";
}

sub recursive_modulus {
my $N = shift;
my @answers;
foreach my $spy_start_pos (1,2) {
my $spy_pos = $spy_start_pos;
foreach my $n_people (4 .. $N) {
$spy_pos += 3;
$spy_pos = $spy_pos % $n_people; #spy_pos mod n_people
$spy_pos = $n_people if $spy_pos == 0;
}
push @answers, $spy_pos;
}
return @answers;
}

sub switch_states_method {
my $N = shift;
my @answers;
foreach my $spy_start_pos (1..2) {
my ($spy_pos, $last_spy_pos) = ($spy_start_pos, $spy_start_pos);
my ($chain_length, $last_chain_length) = (3,3);
while ($chain_length <= $N) {
$last_chain_length = $chain_length;
$last_spy_pos = $spy_pos;
my $odd_num_in_chain = $chain_length % 2; #0 if even, 1 if odd
if ($odd_num_in_chain) {
if ($spy_pos == 1) {
#odd num in chain and spy pos is 1
$spy_pos = 2;
$chain_length = 1.5*$chain_length + 0.5;
}else{
#odd num in chain and spy pos is 2
$spy_pos = 1;
$chain_length = 1.5*$chain_length - 0.5;
}
}else {
$chain_length = 1.5*$chain_length;
#spy position does not change;
}
}
my $num_left = $N - $last_chain_length;
push @answers, $last_spy_pos + 3*$num_left;
}
return @answers;

And here are the results from some runs:
It's pretty clear that the switch states method is scaling with log(n_people) whereas recursive modulus scales with n_people

I'm stopping thinking about this now, it seems I've gone as far as I can go.

Input number of resistance fighters, '0' to exit
3
Recursive Modulus got 1 and 2 in 0 seconds
Switch States Method got 1 and 2 in 4.5e-005 seconds
Input number of resistance fighters, '0' to exit
4
Recursive Modulus got 4 and 1 in 5.1e-005 seconds
Switch States Method got 4 and 1 in 4.8e-005 seconds
Input number of resistance fighters, '0' to exit
10
Recursive Modulus got 10 and 4 in 5.7e-005 seconds
Switch States Method got 10 and 4 in 5.5e-005 seconds
Input number of resistance fighters, '0' to exit
100
Recursive Modulus got 58 and 91 in 0.000148 seconds
Switch States Method got 58 and 91 in 7.1e-005 seconds
Input number of resistance fighters, '0' to exit
1000
Recursive Modulus got 226 and 604 in 0.00104 seconds
Switch States Method got 226 and 604 in 9.1e-005 seconds
Input number of resistance fighters, '0' to exit
10000
Recursive Modulus got 8923 and 2692 in 0.01 seconds
Switch States Method got 8923 and 2692 in 0.000107 seconds
Input number of resistance fighters, '0' to exit
100000
Recursive Modulus got 59905 and 92620 in 0.061135 seconds
Switch States Method got 59905 and 92620 in 4.8e-005 seconds
Input number of resistance fighters, '0' to exit
1000000
Recursive Modulus got 265157 and 637798 in 0.393022 seconds
Switch States Method got 265157 and 637798 in 5.8e-005 seconds
Input number of resistance fighters, '0' to exit
10000000
Recursive Modulus got 9232277 and 3093025 in 3.718212 seconds
Switch States Method got 9232277 and 3093025 in 6.5e-005 seconds
Input number of resistance fighters, '0' to exit
100000000
Recursive Modulus got 63442642 and 95675152 in 37.114123 seconds
Switch States Method got 63442642 and 95675152 in 7.7e-005 seconds
Input number of resistance fighters, '0' to exit
1000000000
Recursive Modulus got 305463824 and 672612260 in 371.391242 seconds
Switch States Method got 305463824 and 672612260 in 0.000103 seconds
Input number of resistance fighters, '0' to exit

Originally posted by iamatiger
I can see no sign at all of any ordering, therefore I am starting to think that writing a non-recursive formula for the spy position at any position is impossible..

Yes I came to the same conclusion.

Yep, on a local level it is predictable - position moves 3 forward each go, but on a long distance level the recursive modulus makes it random and unpredictable. Luckily, because each regular part is 1.5 times longer than the last, it is possible to pre-compute compute the regular parts, and only work out the non regular parts explicitly, which gives the technique solving it in log(n) time.

Here a the shorter but somewhat more obfucticated version of the perl log(n) solution:

foreach my $spy_start_pos (0..1) {
my ($spy_pos, $last_spy_pos, $chain_length, $last_chain_length) = ($spy_start_pos, $spy_start_pos, 3, 3);
while ($chain_length < $N) {
my $odd_chain = $chain_length % 2;
chain_length *= 1.5;
$chain_length += 0.5 - $spy_pos if $odd_chain;
$spy_pos = !$spy_pos if $odd_chain;
($last_chain_length, $last_spy_pos) = ($chain_length, $spy_pos) if $chain_length <= $N;
}
push @answers, $last_spy_pos + 1 + 3*($N - $last_chain_length);
}

Originally posted by iamatiger
Yep, on a local level it is predictable - position moves 3 forward each go, but on a long distance level the recursive modulus makes it random and unpredictable. Luckily, because each regular part is 1.5 times longer than the last, it is possible to pre-compute compute the regular parts, and only work out the non regular parts explicitly, which gives the t ...[text shortened]... $N;
}
push @answers, $last_spy_pos + 1 + 3*($N - $last_chain_length);
}

And here's how spy 0 works it out by hand:

Spy 1, my start position is 0
Length is 3, its an odd chain,
Multiply by 1.5: Length is 4.5
My Position is 0, and it was an odd chain so add 0.5, chain length is 5
as it was an odd chain, flip my position to 1
It's still an odd chain
Multiply by 1.5, length is 7.5
My position is 1 and it's an odd chain, so take 0.5, chain length is 7
as its an odd chain, flip my position to 0
It's still an odd chain
Multiply by 1.5, chain length is 10.5
My position is 0 andit was an odd chain, so add 0.5, chain length is 11
as it was an odd chain, flip my position to 1
It's still an odd chain
Multiply by 1.5, chain length is 16.5
My position is 1 and it was an odd chain, so take 0.5, chain length is 16
As it was an odd chain, flip my position to 0
Its an even chain now
Multiply by 1.5, chain length is 24
Its still an even chain
Multiply by 1.5, chain length is 36
It's still an even chain
Multiply by 1.5, chain length is 54
It's still an even chain
Multiply by 1.5, chain length is 81
the next multiply will take it over 100, so we stop there.

I'm currently at position 0, so my calculation is now
0 + 1 + 3*(100-81) = 58
Ok, I need to stand at position 58