3
$\begingroup$

As a kid I had a silly dream of trying all possible ice cream pair combinations at Baskin Robbins 31 flavors. I was able to calculate there were $31\choose 2$, or 465. At a double scoop a day, that would take over a year.

But then I wondered, how much time would I save ordering only triple scoops? And what price would triple scoops have to be to make this worth it, money-wise?

Looking at the simpler general cases, say, n=4, there are 6 possible pairs: 1-2, 1-3, 1-4, 2-3, 2-4 and 3-4. We can cover them with three triple scoops.

  • 1-2-3 adds 12 13 23
  • 1-2-4 adds 14 24
  • 1-3-4 adds 34

It doesn't look like we can get all the combos in $\frac{n\choose 2}{3}$ scoops for just any value of n. If $n=1 mod 3$ then n is not even divisible by 3. But we can get close. For n=5, there are 10 possible pairs. We can cover them with four triple scoops.

  • 1-2-3 adds 12 13 23
  • 1-4-5 adds 14 15 45
  • 2-3-4 adds 24 34
  • 2-3-5 adds 25 35

For n=6, we take pairs with flavor 1 and get * 1-2-3 * 1-4-5 (note 1-6-x will cover 1-x again, so let's look elsewhere) * 2-4-6 * 3-4-6 * 2-3-5 * 1-5-6

This is 1+$\frac{n\choose 2}{3}$, or the best we can do knowing there will be one overlap.

For n=7,

  • 1-2-3
  • 1-4-5
  • 1-6-7
  • 2-4-6
  • 2-5-7
  • 3-4-7
  • 3-5-6

But there seems to be no easy way to induct to prove a general case. For instance, going from N to N+3 (or n+any odd number) means we will have to deal with overlapping triads that appear/disappear, N to N+2 means we will eventually hit 1 mod 3, and going from N to N+6 means we can't quite match up (n+1, ..., n+6) into tetrads before pairing them with (1...n). So I'm stuck.

There may be a canonical name for this sort of problem. I'd love to know it.

$\endgroup$
2
$\begingroup$

You child dream is real. It was proved by Kirkman in 1847.

We considered this problem a few years ago. We formulated it as follows. Given natural numbers $n$ and $k<n$, find the smallest number $c(n,k)$ of copies of a complete graph $K_k$, covering all edges of a complete graph $K_n$. We were interested in cases $k=3$ (as you) and $k=4$.

This problem is closely related with Steiner systems. Namely, a required cover without overlapping edges exists iff Steiner system $S(2,k,n)$ exists. In particular, for $k=3$, $S(2,k,n)$ is a Steiner triple system, which exists iff $n\equiv 1\pmod 6$ or $n\equiv 3\pmod 6$. For instance, you already constructed a Steiner triple system $S(2,3,7)$. Also such a system is depicted as the Fano plane at the linked page. Since $31\equiv 1\pmod 6$, you can perfectly realize your child dream by triple scoops without overlaps.

Concerning the general case, since a graph $K_t$ has ${t\choose 2}$ edges, we have $c(n,3)\ge \tfrac {n\choose 2}{3\choose 2}=\tfrac {n(n-1)}{6}.$ We get an upper bound for $c(n,3)$ by adding vertices to the graph $K_n$ until a Steiner system exists for $n$. It follows that $c(n,3)\le \tfrac {(n+3)(n+1)}{6}$. So, asymptotically $c(n,3)=\frac {n^2}{6}+O(n)$.

$\endgroup$

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.