Interesting puzzle... 2

[BobRodes]

Recently, my father mentioned a puzzle. He said that one of his teachers gave it to him in school as a teenager to keep him quiet, and he has yet to solve it (at age 81). The puzzle is this:

You have 15 soldiers, marching in 5 rows of 3. The soldiers march for a total of 7 days. Each day, they must march in a row with different soldiers, such that they never march in their row of three with the same soldier on two different days.

It would seem doable, given that each soldier marches with 2 others, there are 7 days in a week, and a total of 14 companions each.

I've done some fooling around modeling out a solution in VB6, and it's proving to be quite complex. I'm interested to see what other people come up with.

 

[PHV]

Simply do a google search for:
Kirkman's School Girl Problem

Hope This Helps, PH.
FAQ219-2884
FAQ181-2886

 

[BobRodes]

Excellent, PHV. Thanks for the link.

 

[GwydionM]

Without looking at the answer, I'd see it like this.

Think in terms of columns. The third column moved down one each day, with the back rank going to the front. That's five.

Same with the second column. That's another five permutations with each of the five. 25 different, no duplicates because each has a different soldier in column 1.



------------------------------
An old man who lives in the UK

 

[guitarzan]

If I'm understanding you correctly, your algorithm doesn't follow the question... the first iteration in "third column moved down one each day, with the back rank going to the front" might look like this:

A B C	    A B O
D E F	    D E C
G H I  ==>   G H F
J K L	    J K I
M N O	    M N L

But in the question, each soldier "must march in a row with different soldiers, such that they never march in their row of three with the same soldier on two different days". But "A" marches with "B" twice...

 

[ck1999]

you could think of it from 1 person standpoint


day person a person b person c
1 Me 14 choices 13 choices
2 me 12 choices 11 choices (2 lost on day 1)
3 me 10 choices 9 choices (etc)
4 me 8 choices 7 choices
5 me 6 choices 5 choices
6 me 4 choices 3 choices
7 me 2 choices 1 choice

after 7 days there are no other choices without duplicating

ck1999