Skip to main content
2 of 3
added 132 characters in body
Daniel Weber
  • 4.9k
  • 1
  • 18
  • 33

It is $\frac{k-1}k$.

For a lower bound, we can arbitrarily order the partitions and elements in each partition, and assign the $i$-th element in the $j$-th partition to the $i + j \bmod k$-th partition. By symmetry the parts in the resulting partition will all have the same size, which must be $n$. Every person remains together with at most $\lceil\frac{n}{k}\rceil \le \frac{n}{k} + 1$ members from $P$, so it has at least $\frac{k-1}k n - 1$ new members, so the quality is $\frac{k-1}k (1 + \frac{1}{n-1}) - \frac{1}{n-1} = \frac{k-1}k - \frac{1}{(n-1)k}$. As $n$ goes to infinity this goes to $\frac{k-1}k$.

For an upper bound, choose some part $A$ in $P$. Because $\sum_{B \in Q} |A \cap B| = |A|$ there must be some $B$ with $\frac nk \le |A\cap B|$. Choosing some $s \in A \cap B$, we get $\operatorname{diff}_{P,Q}(s) = \frac{|A \setminus B|}{n-1} = \frac{n - |A \cap B|}{n-1} \le \frac{n - \frac nk}{n-1} = \frac{k-1}k \frac{n}{n-1} = \frac{k-1}{k} + \frac{k-1}{(n-1)k}$, which converges to $\frac{k-1}k$ as $n \to \infty$.

Daniel Weber
  • 4.9k
  • 1
  • 18
  • 33