8 people in 4 teams with different pairs in each team each day for 7 days without repeated pairs or anyone being in the same within 3 days

Ok I am a Scout Leader and on our 7 day summer camp we have 8 Leaders and will have the Scouts in 4 different patrols or teams.

I want to set up a rota for the Leaders so that they can be assigned to help the Scout Patrols for a day in pairs.

I want all the Leaders to work with every other Leader for a day which I know is possible as there are 28 different pairings with 8 people and helpfully there are 7 days and 4 patrols making 28 spaces to allocate to the 28 pairs.

I also want to make sure each Leader helps with each Patrol at least once, again this is not too hard to achieve (its basically an 8 team round robin tournament at 4 grounds) but the stumbling block I am having is that ideally I do not want any Leader to help with the same Patrol without at least a 2 day gap (e.g. help Monday and not back there until Thursday). I am not sure this is possible but I certainly do not want any Leader helping with the same patrol on consecutive days if i can help it.

I do have a Maths degree but its well over 10 years since I completed it now and I do not work in Mathematics so I am unfortunately very rusty on this kind of thing but I am sure there must be a logical way of solving this rather than just trial and error.

Sorry if I have posted in the wrong place or not made my question clear enough

• I think you'll struggle on the 2-day gap, given the leader re-pairing. But everything else should be feasible. – Joffan Jul 5 '16 at 17:29

Do you mean something like this?

AB CD EF GH

CE FG AH BD

DG EH BC AF

BF DA EG CH

AC GF DH BE

DE BH CF AG

BG DF AE HC

• This is very good, and satisfies most conditions, but has flaws too: FH and CG don't pair up. – Empy2 Jul 5 '16 at 19:23
• True.Thoug I don't think that all of the conditions can be satisfied, I will maybe try to write a proper proof or run a brute-force script. In my oppinion the problem is far more interesting than it looks like. – Ria Jul 5 '16 at 19:40

This is the Social Golfer Problem.

day 1: 12 34 56 78
day 2: 57 68 13 24
day 3: 46 17 28 35
day 4: 38 25 47 16
day 5: 14 67 23 58
day 6: 26 48 15 37
day 7: 45 36 27 18

Edit -- I've made some changes for the other constraint.

• This has Leader A helping Patrol 1 seven days in a row. – Empy2 Jul 5 '16 at 17:22
• Just needs a little patrol shuffling... Ed? – Joffan Jul 5 '16 at 17:28
• The pairings within each day will need some shuffling around, yes. – Ed Pegg Jul 5 '16 at 17:50
• If it were that simple I would not have sought out this forum to solve it. I know all the 28 pairing combinations and I can fairly easily arrange them so every Leader visits every patrol. Its doing that whilst at the same time trying to keep gaps between any Leader revisiting a patrol which makes this difficult – Peter Andrews Jul 5 '16 at 20:04

This is my best attempt, mainly by trial and error

AB CD EF GH

FH AE CG BD

CE GB DH AF

EH DF AG CB

GF AC BH ED

BE GD CF AH

I think I have every pair and everyone visits each patrol and I have at least avoided anyone remaining at the same patrol 2 days running.

I would still love to know if their is a more mathematical way to get a solution

I have two flaws: The seventh day involves a repetition, and C doesn't supervise Patrol 1.

FG EH DB AC
AH BG CF DE
BE CD AG HF
FD AE HB GC
AB CH DG EF
HD GE AF BC

I have seen two different ways to organize the leaders. The first is Ed's, in which pairs such as A and B play a special role: In round two, A pairs C and B pairs D, but in round 3 they swap, so A pairs D and B pairs C. The seven days are:

$$\begin{array}{cccc}AB&CD&EF&GH\end{array}$$ $$\color{blue}{ \begin{array}{cccc}AC&BD&EG&FH\\ AD&BD&EH&FG\end{array}}$$ $$\color{green}{\begin{array}{cccc}AE&BF&CG&DH\\ AF&BE&CH&DG\end{array}}$$ $$\color{red}{\begin{array}{cccc}AG&BH&CE&DF\\ AH&BG&CF&DE\end{array}}$$ During three consecutive days, a patrol must have six different leaders. It turns out that these days must be either two of one colour and one of another colour; or the black day and one each of two colours. The possible day order is then either

black, red, green,green,blue,blue,red; or
green,red,green,black,blue,red,blue

or a similar arrangement with different colours. However, when leaders are assigned patrols for the first three days, it becomes impossible to assign them for the fourth day.
Another arrangement of leaders uses a 2x4 rectangle. A stays in the $1,1$ spot, and the other leaders cycle through the other spots. Each column gives a pairing. The arrangement is this:
$$\begin{array}{cccc}AH&BG&CF&DE\\ AG&HF&BE&CD\\ AF&GE&HD&BC\\ AE&FD&GC&HB\\ AD&EC&FB&GH\\ AC&DB&EH&FG\\ AB&CH&DG&EF\end{array}$$ Three consecutive days can only give each patrol six different leaders if two of the days are consecutive rows, and the other is either two rows later or two rows earlier. So, for example, R1,R3,R4,R6,R7,R2 is possible, but R5 cannot be fitted in.