Two Spies

It's said that in the early days of Roman conquest the legions had trapped a group of 100 resistance fighters in a cave. They also had two spies among the 100 resistance fighters. As surrender to Romans was undesirable, the 100 came up with an alternative; mass suicide. But how? They decided to form a big circle, and then every third person would be killed by the person on his or her right and left. The slaughter would go round and round until only two people would be left, and they would then slay each other.

Example with 8 people:
1-2-3-4-5-6-7-8... #3 killed by #2 and #4
1-2-4-5-6-7-8... #6 killed by #5 and #7
1-2-4-5-7-8... #1 killed by #8 and #2
2-4-5-7-8... #5 killed by #4 and #7
2-4-7-8... #2 killed by #8 and #2
4-7-8... #8 killed by #4 and #7

#4 and #7 survive.


Obviously the spies wanted to be the last two people left alive. But where in the circle should they start when there are 100 people? How about if there are n people?

Originally posted by talzamir
It's said that in the early days of Roman conquest the legions had trapped a group of 100 resistance fighters in a cave. They also had two spies among the 100 resistance fighters. As surrender to Romans was undesirable, the 100 came up with an alternative; mass suicide. But how? They decided to form a big circle, and then every third person would be killed ...[text shortened]... d go round and round until only two people would be left, and they would then slay each other.

In the original statement of this problem, it's not in the early days but during the Judean revolt (specifically, either the siege of Jodfat or that of Massada); there are anywhere between 12 and 40 people in the cave, rarely as many as 100; and the people left over aren't spies, but the Jewish scholar and historian Josephus and his friend.

It is, in fact, well-known under the name "Josephus problem".

Richard

Indeed so. The Josephus and accomplice variant for k = 3, n = 100, or generic.

with 3 people

SSX

the third is killed and the spies survive

With 4 people we need SSX after the first one dies, so:

SXXS

With 5 people we need the 4 people answer after the first dies so:

XSXSX

With 6 people:

SXXXSX

The rule is take the two people at the end, add an X on the end of them, and put that group of 3 at the start

so for 3 to 14 it goes:

SSX
SXXS
XSXSX
SXXXSX
SXXSXXX
XXXSXXSX
SXXXXXSXX
XXXSXXXXXS
XSXXXXSXXXX
XXXXSXXXXSXX
XXXXXXXSXXXXS
XSXXXXXXXXSXXX

Hmm, not seeing any particularly obvious pattern at the moment...

If you plot the position of the spies for population sizes for n = 3 to 200 you should see a pattern.

For n = 3 , assuming a starting position for Spy#1 of 1 and Spy#2 of 2, then the desired position for the spy given n+1 is as follows :

Reveal Hidden Content

The actual position of the spy could probably be worked out based on the value of n instead of looking to the position of the spy in position n-1. Maybe a job for tomorrow.......

Andrew

I have the formula I think:

Reveal Hidden Content
Reveal Hidden Content
Reveal Hidden Content

I'm guessing there is no point hiding the formulas now? I was toying with the identical formula last night, but it isn't correct for values such as f(7,1) and f(7,2). For n=7, we want the function to return the values 1 & 4 but it returns 6 & 7. On occasion the function returns a number divisible by 3 which we know is not correct.

My previous formula works for all values of n from 3 to 200. At the risk of stating the obvious, starting at 1 and incrementing by 3 f(n) times is not the same as starting at the previous position value and incrementing by 3. Hence the iterative formula works, but the generic formula does not.

I have tried with a variation of
Spy(n,s) = (s + (n-3)*3) mod (n+y)
only for s=1 (I'm putting s=2 to the side for the moment to see if I can at least work out the value for one of the spies).

My initial thought was to use a value of y=-1 but this didn't work, or some sort of repeating pattern of 0,1,2 or 1,2,3 or 3,2,1 or 2,1,0 etc - to no avail.

There seems to be some sort of pattern with the values of y, but the points at which the values of y change for given values of n appear to be relatively random, as does the value of y when it deviates from the pattern. For example, for the values n=24 to 30, and the values of y=29 to 23, the modified formula returns one correct spy number. But for n=31, y=11 to get the modified formula to work. So I'm guessing this angle might be a dead end.

Starting again:
We know the first spy must be at position 1 for n=3 and this position increases by 3 each time n changes. The initial formula we both used returns the correct starting position, but applying mod n doesn't work. So either we change the mod n part to something else or we change the initial formula of s+(n-3)*3. The logical part is to look at the mod n part, but this is proving fruitless.

Originally posted by iamatiger
I have the formula I think:

[hidden] func (N,S) = (S + (N-3)*3) modulo N) [/hidden]
[hidden] Where modulo N must return N and not 0 if the number is exactly divisible by N [/hidden]
[hidden] For a circle of N people, put one spy at func(N, 1), the other at Func(N,2)[/hidden]

Hmm

SSX = 1,1: (1+0*3) mod 3 = 1; (2 + 0*3) mod 3 = 2
SXXS = 1,4: (1 + 1*3) mod 4 = 4; (2 + 1*3) mod 4 = 1
XSXSX = 2,4: (1 + 2*3) mod 5 = 2; (2 + 2*3) mod 5 = 3 oops!

Does look like it needs a rethink. you are right

I'm looking at if we can do some kind of sum using only mod(n) on a count that has no previous mods in it.

Spies are S and T to keep track of which is which

3: STX (1,2)
4 TXXS (1+3,2+3) = (4,5) mod 4 = (4,1)
5: XSXTX (4+3, 5+3+1) = (7,9) mod 5 = (2,4)
6: TXXXSX = (7+3+1, 9+3+1) = (11, 13) mod 6 = (5,1)
7: SXXTXXX = (11 + 3 + 1, 13 + 3 + 2) = (15, 18) mod 7 = (1 4)
8: XXXSXXTX = (15 + 3 + 2, 18 + 3 + 2) = (20, 23) mod 8 = (4, 7)
9: TXXXXXSXX = (20 + 3 + 2, 23 + 3 + 2) = (25, 28) mod 9 = (7, 1)
10: XXXTXXXXXS = (25 + 3 + 2, 28 + 3 + 3) = (30, 34) mod 10 = (10,4)
11: XSXXXXTXXXX = (30 + 3 + 2, 34 + 3 + 3) = (35, 40) mod 11 = (2, 7)

The first number shows how we increment the count. It seems to go up by 3 each time, plus a correction factor. The correction factor seems to possibly be incremented on the turn after a spy comes in position 1 which means it is hard to predict without use of any mods, Thoughts continue.

Your latest formula for n=6 and s=2 uses 9 as your starting point which is a direct reference to the previous spy position. If we are to make reference to the previous position, then we have a formula above.

However, the slightly modified formula:
Pos(n,s) = (n-3)*3+s+y mod n
definitely has a pattern to the values of y.

The general rule for y when s=1 is:
a) for n<12 a special case is needed (see below);
else for n>=12:
b) 1) y = 2 for any new 'run'* when the previous run ends exactly on n,
b) 2) else y = 1;
and
c) 1) for y(n-1) < 9 then y = y(n-1) + 2,
c) 2) else y = y(n-1) + 3 ;
and
d) y must be <= n {i.e. the 'run'* ends when y = n, or y would exceed n if 3 were added to the previous value of y}

*a run is defined as a sequence of increasing values of y from z to n {z being 1 or 2}.

This seems to work for cases where n = 12 to 200.

The general rule for y when s=2 is :
e) for n<10 a special case is needed (see below);
else for n>=10:
f) 1) y = 2 for any new 'run' when the previous run ends exactly on n,
f) 2) else y = 1;
and
g) 1) for y(n-1) < 8, y = y(n-1) + 2,
g) 2) else y = y(n-1) + 3;
and
h) y must be <= n.

This seems to work for cases where n= 10 to 200.

Example values of y for the values n, s1 & s2:
3; 0; 0
4; 0; 0
5; 0; 1
6; 1; 2
7; 2; 4
8; 4; 6
9; 6; 8
10; 8; 1
11; 10; 3
12; 1; 5
13; 3; 7
14; 5; 9
15; 7; 12
16; 9; 15
17; 12; 1
18; 15; 3
19; 18; 5
20; 1; 7
and so on...the pattern seems to stick but coding it may be an issue......

The points at which the runs start (at either 1 or 2, depending on the rule above) for s=1 are the following values of n: 6, 12, 20, 32, 50, 77, 118, 179..... etc.

And the points at which the runs starts (at either 1 or 2, depending on the rule above) for s=2 are the following values of n : 5, 10, 17, 28, 43, 67, 102 & 154 and so on.

However, an issue with this method is we are still referring to the previous value of y so it is not yet non-iterative.

Andrew

I'm wondering if using mod at all confuses the issue.

we can generate the numbers without use of mod with a rule like:

Define N as length of chain, initial value 3
A spy at the start of the line is at position 1
for the start positio we have N=3, a Spy at 1 and a spy at 2
Then:

if spy_pos(N) is less than N-1 (with first pos = 1) then
Spy_pos(N+1) = Spy_Pos(N) + 3
Else
Spy_Pos(N+1) = spy_Pos(N) - N + 2
end if

Then we just need a mathematical formula that reproduces this rule using only N as its input.

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|---------------------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11

You need to plot more points, probably.

edit:What if you plot the difference between each spy position vs the amount of total people in the group?
Maybe there is a pattern in the amount of people between each spy.

SSX
SXXS
XSXSX
SXXXSX
SXXSXXX
XXXSXXSX
SXXXXXSXX
XXXSXXXXXS
XSXXXXSXXXX
XXXXSXXXXSXX
XXXXXXXSXXXXS
XSXXXXXXXXSXXX

In this, the S goes down diagonally, one down three to the right, until it catches up with the "A8-H1 diagonal", at which point it starts over - at 1st position if on the previous line the next to last was S, or 2nd or the next-to-last was S on the previous line.. so that too is a case of one down, three to the right, just wrapping around. Does that apply throughout?

Originally posted by talzamir
SSX
SXXS
XSXSX
SXXXSX
SXXSXXX
XXXSXXSX
SXXXXXSXX
XXXSXXXXXS
XSXXXXSXXXX
XXXXSXXXXSXX
XXXXXXXSXXXXS
XSXXXXXXXXSXXX

In this, the S goes down diagonally, one down three to the right, until it catches up with the "A8-H1 diagonal", at which point it starts over - at 1st position if on the previous line the next to last was S, or 2nd or ...[text shortened]... o is a case of one down, three to the right, just wrapping around. Does that apply throughout?

Yes.

If a spy is not the last or the second to last, he moves three to the right. Otherwise:
A spy at the end moves to second from the start, and we add one to the end, so he he has moved "3 to the right"

A spy second from the end moves to the start and we add one to the end, so he has moved 3 to the right too.

Of course, "one down, three to the right" needs the previous positions of the spies. We are searching for a way to predict the spies positions at any N without needing to know the previous positions.

It is complex because for spies near the end, "one down, three to the right" gives a move specific to a particular value of N.

Here is a list of the positions of the 2 spies for varying sizes of groups:
https://docs.google.com/document/d/1j80N-et1GAuq3PGpDrOLDde6RYg_W2eBBT9qEbV4nu0/edit?hl=en_US

By showing the spy positions over a large enough sample, you can see the pattern.

@talzamir : If you want an iterative formula, we already have one per my first post above. I reckon the spy number is crucial to solving this in a non-iterative way (assuming it can be done).

Andrew

P.S. message me with your e-mail address if you can't open the document above and I will e-mail it to you.