Skip to main content
added 6 characters in body
Source Link
Daniel Weber
  • 4.9k
  • 1
  • 18
  • 33

It$\operatorname{maxquel}(k, n) = \frac{\lfloor \frac{k-1}k n\rfloor}{n-1}$. In particular, the limit as $n \to \infty$ for a fixed $k$ 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$$\lceil\frac{n}{k}\rceil$ members from $P$, so it has at least $\frac{k-1}k n - 1$$n - \lceil\frac{n}{k}\rceil = \lfloor\frac{k-1}k n\rfloor$ 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$$\frac{\lfloor\frac{k-1}k n\rfloor}{n-1}$.

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|$$\lceil\frac nk\rceil \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$$\operatorname{diff}_{P,Q}(s) = \frac{|A \setminus B|}{n-1} = \frac{n - |A \cap B|}{n-1} \le \frac{n - \lceil\frac nk\rceil}{n-1} = \frac{\lfloor\frac{k-1}k n\rfloor}{n-1}$.

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

$\operatorname{maxquel}(k, n) = \frac{\lfloor \frac{k-1}k n\rfloor}{n-1}$. In particular, the limit as $n \to \infty$ for a fixed $k$ 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$ members from $P$, so it has at least $n - \lceil\frac{n}{k}\rceil = \lfloor\frac{k-1}k n\rfloor$ new members, so the quality is $\frac{\lfloor\frac{k-1}k n\rfloor}{n-1}$.

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 $\lceil\frac nk\rceil \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 - \lceil\frac nk\rceil}{n-1} = \frac{\lfloor\frac{k-1}k n\rfloor}{n-1}$.

added 132 characters in body
Source Link
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 $\frac{n}{k} + O(1)$$\lceil\frac{n}{k}\rceil \le \frac{n}{k} + 1$ members from $P$, so it has at least $\frac{k-1}k n + O(1)$$\frac{k-1}k n - 1$ new members, so the quality is $\frac{k-1}k + O(\frac 1n)$$\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}$$\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$.

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 $\frac{n}{k} + O(1)$ members from $P$, so it has $\frac{k-1}k n + O(1)$ new members, so the quality is $\frac{k-1}k + O(\frac 1n)$. 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}$, which converges to $\frac{k-1}k$ as $n \to \infty$.

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

Source Link
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 $\frac{n}{k} + O(1)$ members from $P$, so it has $\frac{k-1}k n + O(1)$ new members, so the quality is $\frac{k-1}k + O(\frac 1n)$. 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}$, which converges to $\frac{k-1}k$ as $n \to \infty$.