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.
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)$.