5
$\begingroup$

Motivation. This question was inspired by a team management problem that arose during a school soccer tournament. There were $22$ students at the tournament. The goal of the managers was to schedule several matches, each with a different $11$-vs-$11$ students teams partition such that each pair of students is on the same team exactly once. (This was an impossible endeavour -- see comment below by Achim Krause.)

Formalization. For any set $X$ and positive integer $k$, let $[X]^k$ denote the collection of $k$-element subsets of $X$, and let $[k]:=\{0,\ldots, k-1\}$.

If $k < n$ are positive integers, we say that $n$ is $k$-splittable if there is ${\cal M}\subseteq [[2n]]^n$ such that for every $T \in [[2n]]^k$ there is exactly one $M\in {\cal M}$ such that $$T\subseteq M \;{\rm or }\; T \subseteq ([2n] \setminus M).$$ (So, $11$ is not $2$-splittable.)

Matthew Bolan's argument below elegantly establishes that if $k>1$ and $n\geq 2k$ are integers, then $n$ cannot be $k$-splittable.

Question. In light of the comments by Matthew Bolan and Achim Krause below: Let $k>1$ be an integer, and let $n\in\mathbb{N}$ with

  • $n\geq k+1$,
  • $n < 2k$ and
  • ${2n} \choose k$ is a multiple of $2{n\choose k}$.

Does this imply that $n$ is $k$-splittable?

$\endgroup$
3
  • 2
    $\begingroup$ $\binom{22}{2}=21\cdot 11$ is not a multiple of $2\binom{11}{2}=10\cdot 11$. $\endgroup$ Commented Mar 25 at 13:10
  • 3
    $\begingroup$ Suppose $n \ge 2k$. Then (by pigeonhole) in the second round there are at least $k$ students on the first team who were on a team together in round one, so we cannot even play $2$ games. $\endgroup$ Commented Mar 25 at 14:15
  • 1
    $\begingroup$ Matthew Bolan's argument also works for $n=2k-1$ $\endgroup$ Commented Mar 26 at 18:24

1 Answer 1

6
$\begingroup$

I am writing a long comment on this question because it is related to a fascinating mystery about "middle-level designs" that I have been wondering about for several years.

As written in the (now deleted AI-generated) other answer, what you are asking for is exactly a (self-complementary) Steiner $S(k, n, 2n)$ system. The well-known divisibility conditions for designs requires in this case that $$\binom{n - i}{k - i} \mid \binom{2n-i}{k-i} \qquad (0 \le i \le k).$$ Moreover, $k \ge n/2$ by the pigeonhole argument of Matthew Bolan. This is a curious case in which we can (almost) exactly solve the divisibility conditions.

Observation: If $k = n-1$ then the divisibility conditions are satisfied if and only if $n+1$ is prime. If $k < n-1$ then the divisibility conditions are probably never satisfied (i.e., I haven't proved it).

In particular, OP's example $n=11$ is not "$k$-splittable" for any $k < n$, since $n+1 = 12$ is not prime.

Indeed, let $s = n - k \le n/2$ and $j = n - i$. Then the divisibility condition is $$\frac{j!}{s!} \mid \frac{(n+j)!}{(n+s)!} = (n+s+1) \cdots (n+j) \qquad (s < j \le n).$$ If $s = 1$ and $n+1 = p$ is prime then it reduces to checking that $p$ divides $\binom{n+j}{j}$ for all $j = 1, \dots, n$, which is clear.

In the other direction, suppose $p$ is a prime factor of $n+i$ where $1 \le i \le s$. If $p \ne n+i$ then $p \le (n+i)/2 < n$. If moreover $p > s$ then the divisibility condition gives $$p \mid \frac{p!}{s!} \mid (n+s+1) \cdots (n+p),$$ which is impossible because $p$ divides $n+i < n+s+1$ and $n+i+p > n+p$. It follows that every integer in the interval $[n+1, n+s]$ is either prime or $s$-smooth. This is extremely rare for $s > 1$ and $n \ge 2s$. For $n > 15$ the only solutions I know have $s \in \{2,3\}$. For $2 \le s \le 5$, here are some case-specific arguments:

Case $s = 2$: We have $4 \mid 4!/2! \mid (n+3)(n+4)$, so $(n+1)(n+2)$ is not divisible by $4$. Since either $n+1$ or $n+2$ is $2$-smooth we must have $n+1 = 2$ or $n+2 = 2$, a contradiction since $n \ge 2s = 4$.

Case $s = 3$: We have $4 \mid 4!/3! \mid n+4$, so $n$ is divisible by $4$ and $n+2 \equiv 2 \pmod 4$. Since $n+2$ is either prime or $3$-smooth it follows that $n+2 = 2 \cdot 3^k$. Now the divisibility condition with $j=9$ and considering just the factors of $3$ gives $$3 \cdot 9 \mid (n+5)(n+8) = (2 \cdot 3^k + 3)(2 \cdot 3^k + 6),$$ which implies $k \le 1$, so $n \le 4$, a contradiction since $n \ge 2s = 6$.

Case $s = 4$: Two of $n+1, n+2, n+3, n+4$ must be prime and the other two must have the form $2\cdot 3^a$ and $2^b$, which implies that $|3^a - 2^{b-1}| = 1$. It follows that $n = 15$.

Case $s = 5$: Since $6 = 6! / 5! \mid n+6$, we have $6 \mid n$ and therefore $2 \mid n+2, n+4$ and $3 \mid n+3$. Since each of $n+1,n+2,n+3,n+4,n+5$ is supposed to be either prime or $5$-smooth, it must be that one of $n+2, n+4$ is a power of $2$, the other has the form $2 \cdot 5^k$, and $n+3$ is a power of $3$, so again the configuration contains a power of $2$ and a power of $3$ differing by $1$, so $n = 6$, a contradiction since $n \ge 2s = 10$.

One further comment on this strategy: If every integer in the interval $[n+1, n+s]$ is prime or $s$-smooth then by restricting to the even integers and dividing by $2$ we have an interval of at least $(s-1)/2$ integers $> s$ that are all $s$-smooth. This kind of problem has a long history in number theory, and for example Erdős (see Section 7 of [HT] -- thank you to Khalid Younis for this reference) proved that the longest interval of $s$-smooth integers greater than $s$ has length $O(s / \log s)$. Therefore we are done for sufficiently large $s$, and there might even be a bound in the literature somewhere that gives us a complete solution -- I haven't checked sufficiently.

Finally, let us go back to the case $s = 1$, i.e., $k = n-1$. As explained above, the divisibility conditions are satisfied if and only if $n+1 = p$ is prime. But, the divisibility conditions do not guarantee the existence of a design, they are merely necessary conditions. Thus we face the following mysterious question.

Question: Is there a Steiner $S(n-1, n, 2n)$ system whenever $n+1 = p$ is prime?

The answer is yes for $p = 2, 3$ (trivial cases), $p = 5$ ($3$-dim affine geometry over $\mathbf{F}_2$), and $p = 7$ (Witt design on 12 points, whose automorphism group is $M_{12}$). For $p \ge 11$ I believe the question is open.

As for self-complementarity, a result of Mendelsohn [M] implies that every $S(n-1, n, 2n)$ system is automatically self-complementary. Moreover, there is a $S(n-1, n, 2n)$ system if and only if there is a $S(n-2, n-1, 2n-1)$ system.

[HT] Hildebrand, Adolf; Tenenbaum, Gérald, Integers without large prime factors, J. Théor. Nombres Bordx. 5, No. 2, 411-484 (1993). ZBL0797.11070.

[M] Mendelsohn, N. S., A theorem on Steiner systems, Can. J. Math. 22, 1010-1015 (1970). ZBL0192.33305.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.