I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with as many people as possible. I'd like to know how many weeks we could accomplish this before we're forced to partner someone again.
More formally given a set $S$ with an even number of elements, define a "partnering" of $S$ to be a set of partitionings where each part in each partition is of size 2. The empty set is a valid partnering. The set containing any single partitioning of $S$ is a valid partnering. What the largest "partnering" we can define?
If there are $2N$ elements in $S$ then there is no partnering of size greater than $2N-1$. I've also been able to get a rough lower bound on the size of the maximal partnering. The best I've been able to do is half the size of the set but in special cases I can do a bit more. For instance if the size of the set is $2^k*N$ I can get $N+\frac{N}{2} + ... + \frac{N}{2^k}$ but that's a very special case. For powers of two this ideal since $2N-1 = N+\frac{N}{2} + ... + \frac{N}{2^k}$. Ok so for powers of two I have the answer but for other numbers I just have a lower bound.
My current method:
If you have $2N$ elements in your set you can arbitrarily split them into two groups, $A$ and $B$ of size $N$ and assign each element in each group a member of $Z_N$. Call the functions assigning these indexes $Z_a$ and $Z_b$ for the functions that assign them for each group. You can then define $N$ different partitions by first paring $a \in A$ with $b \in B$ if $Z_a(a) = Z_b(B) + k$ for each $k \in Z_n$. That gives you a partnering of size $N$ already. After those pairings have been used up you can recursively split $A$ and $B$ into two groups since no one in $A$ has been partnered with anyone in $A$ yet and likewise for $B$
Intuitively we're splitting the group in two, putting each group in a circle, and then rotating one of the circles. Then if we're lucky we can repeat the process.
Can we do any better or is this optimal? My expectation is that there must be a better result here since otherwise it would mean the size of the maximal partnering has something to do with how many times you can divide the size of the set by 2.
