3
$\begingroup$

What seemed like a simple setup for a team picnic has turned into a nightmare logic puzzle.

There are 8 teams and 8 events/locations. Each event requires two teams who play against each other.

There will be 8 total timeslots, broken into morning and afternoon sessions. Four of the events will be available in the morning and the remaining four will be available in the afternoon.

With the exception of the 8th timeslot (where overlap is unavoidable) each team should face each other team only once AND each team must participate in each event.

What would the schedule look like where the above stipulations are met? Here's my best attempt so far:

          Event 1    Event 2    Event 3    Event 4
   Time 1   1v5        2v6        3v7        4v8
   Time 2   2v7        1v8        4v5        3v6
   Time 3   4v6        3v5        2v8        1v7
   Time 4   3v8        4v7        1v6        2v5

          Event 5    Event 6    Event 7    Event 8
   Time 5   3v4        7v8        1v2        5v6
   Time 6   5v7        1v3        6v8        2v4
   Time 7   #v#        #v#        #v#        #v#
   Time 8   #v#        #v#        #v#        #v#

Which leaves the following requirements without a good way to meet them:

 Team 1 needs to face Team 4
 Team 2 needs to face Team 3
 Team 5 needs to face Team 8
 Team 6 needs to face Team 7

 Team 1 needs to play Events 5 and 8
 Team 2 needs to play Events 5 and 6
 Team 3 needs to play Events 7 and 8
 Team 4 needs to play Events 6 and 7
 Team 5 needs to play Events 6 and 7
 Team 6 needs to play Events 5 and 6
 Team 7 needs to play Events 7 and 8
 Team 8 needs to play Events 5 and 8

I've can't seem to figure this out and am beginning to think that one of the requirements makes it impossible!

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm not quite sure what you are asking here - can you clarify with a question please? $\endgroup$
    – Beastly Gerbil
    Aug 17, 2016 at 14:18
  • $\begingroup$ @BeastlyGerbil the way I see it, how can each team face each other only once AND that each team plays each even only once, given there are 8 teams, 8 events, and 8 timeslots for the events to take place $\endgroup$
    – PartyHatPanda
    Aug 17, 2016 at 14:23
  • 1
    $\begingroup$ @PartyHatPanda There will be a single overlapping match due to each team only having 7 opponents, presumably during the last timeslot. $\endgroup$
    – SuperzPurez
    Aug 17, 2016 at 14:28
  • $\begingroup$ @SuperzPurez each team won't have 7 opponents though, otherwise the'd be playing each other twice - see my answer $\endgroup$
    – Beastly Gerbil
    Aug 17, 2016 at 14:45

3 Answers 3

Reset to default
1
$\begingroup$

The scheduling is

Impossible

To prove this first consider the following

Lemma 1

If we say that, in the morning, each team must play in each of the four events and at each of the four times then there exists no triplet of teams $A$, $B$ and $C$ such that $A$ has played $B$, $B$ has played $C$ and $C$ has played $A$ after the morning session has concluded.

Proof of Lemma 1

Assume the contrary.

Without loss of generality, we can schedule the three teams as follows:

              Event 1     Event 2     Event 3     Event 4    
Time 1     A v B
Time 2                       B v C
Time 3                                       C v A
Time 4

Now we see that, for example, team $C$ still needs to play Events $1$ and $4$ and at Times $1$ and $4$. They cannot play Event $4$ at Time $4$ since they cannot then play Event $1$ or at Time $1$. Hence $C$ must play Event $1$ at Time $4$ and Event $4$ at Time $1$. A similar reasoning for the other two teams allows us to further fill in the schedule as follows:

              Event 1     Event 2     Event 3     Event 4    
Time 1     A v B                                           C v
Time 2                       B v C                         A v
Time 3                                       C v A         B v
Time 4     C v             A v           B v

Again, without loss of generality, we can fill in the rest of the slots for Event $4$ with teams $D$, $E$, $F$, $G$ and $H$. We note that we are then limited to two possibilities or permutations of the teams $D$, $E$ and $F$ to fill out the timeslot Time $4$ and the choice is arbitrary (the proof works equally for both). Choosing one of these permutations, our scheduling now appears as follows:

              Event 1     Event 2     Event 3     Event 4    
Time 1     A v B                                           C v D
Time 2                       B v C                         A v E
Time 3                                       C v A         B v F
Time 4     C v F         A v D        B v E        G v H

Now we note that, for example, team $D$ must still play Events $1$ and $3$ and at times $2$ and $3$ but if they play Event $1$ at Time $2$, then they will not play either Event $3$ or at Time $3$. Hence, team $D$ must play Event $3$ at Time $2$ and Event $1$ at Time $3$. We can use a similar reasoning for teams $E$ and $F$ to further fill the grid as follows:

              Event 1     Event 2     Event 3     Event 4    
Time 1     A v B         E v F                         C v D
Time 2                       B v C       D v F         A v E
Time 3     D v E                         C v A         B v F
Time 4     C v F         A v D        B v E        G v H

Clearly, then to fill out the rest of the schedule we must have team $G$ playing team $H$ in each of the four events which is clearly disallowed. (Note: Even in the loosest interpretation of the problem, no team may play any other more than twice).

This proves the lemma.

Lemma 2

After the morning, there will be a group of four teams, none of which have played any of the others.

Proof of Lemma 2

Let $A$, $B$, $C$ and $D$ be the four teams who played team $1$ in the morning session. By Lemma $1$, no two of these teams have played each other if all the rules have been followed thus far.

Proof of Original Conjecture

By Lemma $2$, when we come to the afternoon session, there will be a group of four teams $A$, $B$, $C$ and $D$ all of whom have yet to play each of the others while playing in each of the four events and in each of the four times.

Since we still must schedule six interactions (involving just this group of teams) in four timeslots, there must be at least two timeslots with two interactions involving just $A$, $B$, $C$ and $D$. Without loss of generality, let these be the first two, Times $5$ and $6$, and the corresponding interactions be $A$ v $B$ with $C$ v $D$ and $A$ v $C$ with $B$ v $D$.

Further, we can safely assume, while still considering all permutations, that $A$ plays $B$ in Event $5$ at Time $5$ and $C$ plays $D$ in Event $6$ at Time $5$. Then, at Time $6$, $A$ must play $C$ in Event $7$ or $8$ and $B$ must play $D$ in the other.

Now, it only remains for $A$ to play $D$ but, between them, they have already played all of the afternoon events. Hence, there is no Event in which they can both play in which one of them hasn't already. Same goes for $B$ and $C$.

Therefore, the scheduling is impossible.

Improve this answer
$\endgroup$
0
$\begingroup$

I don't think it's possible:

Consider the reduced case of four teams, four events, and four time slots. Recall that the problem allows for at most a single duplication of any matchups for any teams (e.g. 1 can play 2 twice, and 3 can play 4 twice), but that EACH team must participate in EACH event.

Let's try to construct the table as was done by the original poster:

Let's do this "time slot by time slot". We first fill in time slot 1 for event 1, arbitrarily selecting teams 1 and 2. This means that Event 2 at Time 1 consists of teams 3 and 4. This leaves us with:

        Event 1         Event 2
Time 1   1 v 2           3 v 4
Time 2
        Event 3         Event 4
Time 3
Time 4

Next, we wish to fill in Time 2: Since there are four teams and four events, no team can repeat any event. This means that that Time 2, Event 1 MUST be a matchup of 3 and 4, and Time 2, Event 2 MUST be a matchup of 1 and 2, leaving us with:

        Event 1         Event 2
Time 1   1 v 2           3 v 4
Time 2   3 v 4           1 v 2
        Event 3         Event 4
Time 3
Time 4

Now, we've already had duplicate matches, but so far it's ok--one set of duplicate matches is allowed. So let's fill in Time 3: let's arbitrarily put 1 in event 3 at that time---and they can't play 2, but let's have them arbitrarily play 3 at that time. Of course this leaves 2 against 4 in Time 3, Event 4, leaving us with:

        Event 1        Event 2
Time 1   1 v 2          3 v 4
Time 2   3 v 4           1 v 2
        Event 3         Event 4
Time 3   1 v 3           2 v 4
Time 4

Now, filling in Time 4 will leave us with the same dilemma we faced in the first half of the day---teams 1 and 3 HAVE TO be in event 4, and teams 2 and 4 HAVE TO be in event 3, leaving us with:

        Event 1         Event 2
Time 1   1 v 2           3 v 4
Time 2   3 v 4           1 v 2
        Event 3         Event 4
Time 3   1 v 3           2 v 4
Time 4   2 v 4           1 v 3

But this leaves us without having ever had the matchups 1 v 4 and 2 v 3.

I think it will also prove impossible for the 8 by 8 case but don't have a proof yet.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 4 or 5 leading spaces triggers the pre-formatted code style. $\endgroup$
    – SuperzPurez
    Aug 17, 2016 at 19:19
  • $\begingroup$ thanks gtwebb i was working on it but you're quicker than i :D $\endgroup$
    – Philip Schiff
    Aug 17, 2016 at 19:22
  • $\begingroup$ how to make the whole thing with spoilers 1) without having to put >! on each line 2) without messing up the indent of four spaces? $\endgroup$
    – Philip Schiff
    Aug 17, 2016 at 19:25
  • $\begingroup$ When you're using arguments based on MOLS, the number is extremely important. You cannot use an example of smaller size to disprove something about a larger one. Case in point: Euler's officer problem has no solution, but making the problem larger makes it soluble (in more than one way). $\endgroup$
    – Nij
    Aug 17, 2016 at 19:34
  • $\begingroup$ Hmmm I will reconsider, because you're right, expanding the problem removes the restriction you encounter when you fill in Time 2--- (e.g. that 1 will again play 2) $\endgroup$
    – Philip Schiff
    Aug 17, 2016 at 19:41
0
$\begingroup$ 


              Event 1    Event 2    Event 3    Event 4
       Time 1   1v2        1v3        1v4        1v5
       Time 2   3v4        2v4        2v3        2v6
       Time 3   5v6        5v7        5v8        3v7
       Time 4   7v8        6v8        6v7        4v8

              Event 5    Event 6    Event 7    Event 8
       Time 5   1v6        1v7        1v8        #v#
       Time 6   2v7        2v8        2v5        #v#
       Time 7   3v8        3v5        3v6        #v#
       Time 8   4v5        4v6        4v7        #v#

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Your solution has team 1 taking part in all four events during the first time slot. They can't be in 2 places at the same time, let alone 4. $\endgroup$
    – Jaap Scherphuis
    Aug 18, 2016 at 12:38
  • $\begingroup$ i knew it seemed too easy :( $\endgroup$
    – JMP
    Aug 18, 2016 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.