3
$\begingroup$

A group of 8 golfers would like to play in teams, split into two teams of 4, with a different arrangement of teams on each of 5 consecutive days; they would like each pair of players to be on the same team on at least 2 but no more than 3 of the days.

I've established computationally that there are no solutions which fit these criteria; however, I'd like to be able to prove it's not possible by finding the correct combinatorial design and showing that for these values it can't be done; I'd also be interested to know if it would be possible with more golfers, or more days.

I don't know much about design theory, although from what I can see of block designs, many of the examples given allow for setups where each pair occurs in a given number of blocks; the situation where there are two teams isn't covered, since even if I choose blocks of size 4, a pair not being contained in a block isn't the same as both those players being in the other team; it seems I'd need a particular type of block design, possibly a tournament model, but they seem to be more aimed at pairing up competitors rather than teams. Any ideas what I'm looking for?

$\endgroup$
0
$\begingroup$

This is not a complete solution. I'm working on it.


On each day, there are two teams of four golfers. Each team of four corresponds to six distinct pairs of players who are on the same team that day. This means that, over the five days, the total number of (not necessarily distinct) pairs of players on the same team is exactly $$5\cdot 2 \cdot \binom{4}{2} = 60$$

The total number of distinct pairs is $$\binom{8}{2}=28$$

Each of these distinct pairs is allowed to show up in the overall count of $60$ at least $2$ times and at most $3$ times.

This means that exactly four of the pairs show up $3$ times, and the rest show up only twice. In other words, four distinct pairs of golfers share a team three times, and the other $24$ pairs of golfers are only on the same team twice. These numbers $4$ and $24$ are the solutions $x$ and $y$ to this simple system of equations

\begin{align} x+y&=28\\ 3x+2y&=60 \end{align}

But we also know that every golfer is on a team on each of the five days. This means that each golfer is included in $3$ pairs (of golfers on the same team) each day. We use this first to confirm the total number of pairs (dividing by $2$ to adjust for overcounting) as $$\frac{3 \cdot 5 \cdot 8}{2}=60$$

Now the four pairs that have multiplicity $3$ can be all distinct, or there could be at least one golfer who appears in at least two of these pairs. But the fact that each golfer plays the same number of days implies that all multiplicity-$3$ pairs are distinct. In other words, all $8$ golfers are included in exactly $1$ pair that has multiplicity $3$.

$\endgroup$
2
  • $\begingroup$ This is great - I've managed to determine this, and used it in my computational approach. It gives you a very constrained problem, and I'm not surprised there are no solutions. Let me know if you get any further! $\endgroup$ – Katie Steckles Feb 13 '15 at 17:26
  • $\begingroup$ @KatieSteckles I've tried a few things and I can't come up with a nice way to finish the problem - it does narrow down the possibilities a lot though, so maybe brute force for the rest of them (as I assume you did?) is the best approach... $\endgroup$ – Zubin Mukerjee Feb 13 '15 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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