Combinatorics

We will call \(\displaystyle \{u_1, \ldots,u_5\}\) the \(\displaystyle u\)-girls; \(\displaystyle \{v_1, \ldots, v_5\}\) the \(\displaystyle v\)-girls; and \(\displaystyle \{w_1, \ldots, w_5\}\) the \(\displaystyle w\)-girls. Of the \(\displaystyle 35\) blocks that we obtained through the construction, \(\displaystyle 5\) have one \(\displaystyle u\)-girl, one \(\displaystyle v\)-girl, and one \(\displaystyle w\)-girl; the other \(\displaystyle 30\) have either two \(\displaystyle u\)-girls with a \(\displaystyle v\)-girl, two \(\displaystyle v\)-girls with a \(\displaystyle w\)-girl, or two \(\displaystyle w\)-girls with a \(\displaystyle u\)-girl.

A Kirkman system requires us to divide the blocks into \(\displaystyle 7\) groups of \(\displaystyle 5\) blocks such that each girl appears exactly once in each group of blocks. Since there should be \(\displaystyle 7\) groups of \(\displaystyle 5\) blocks, but there are only \(\displaystyle 5\) blocks that have a \(\displaystyle u\)-girl, a \(\displaystyle v\)-girl, and a \(\displaystyle w\)-girl, there must be at least one group of blocks (in fact, at least two) that has no block consisting of a \(\displaystyle u\)-girl, a \(\displaystyle v\)-girl, and a \(\displaystyle w\)-girl.

Consider such a group of \(\displaystyle 5\) blocks. We must have all \(\displaystyle 5\) of the \(\displaystyle u\)-girls. If no block contained more than one \(\displaystyle u\)-girl, then in order to get all \(\displaystyle 5\) \(\displaystyle u\)-girls we would have to choose only blocks that have two \(\displaystyle w\)-girls and a \(\displaystyle u\)-girl. However, this would mean that we had \(\displaystyle 10\) \(\displaystyle w\)-girls and no \(\displaystyle v\)-girls, which is not allowed. So we must choose at least one block that has two \(\displaystyle u\)-girls and a \(\displaystyle v\)-girl. Repeating the same argument with \(\displaystyle v\) or \(\displaystyle w\) taking the place of \(\displaystyle u\text{,}\) we see that we must also choose at least one block that has two \(\displaystyle v\)-girls and a \(\displaystyle w\)-girl, and at least one block that has two \(\displaystyle w\)-girls and a \(\displaystyle u\)-girl. Since we are only choosing \(\displaystyle 5\) blocks but there are these three classes of blocks, there must be some class of blocks of which we only choose one.

Without loss of generality, suppose that we only choose one of the blocks that has two \(\displaystyle u\)-girls and a \(\displaystyle w\)-girl. In order to have all \(\displaystyle 5\) of the \(\displaystyle u\)-girls, we must choose three blocks that have two \(\displaystyle w\)-girls and a \(\displaystyle u\)-girl. But this means that we have six \(\displaystyle w\)-girls, which is not allowed.

Since we are not including any trivial \(\displaystyle t-(v,t,1)\) design, we have \(\displaystyle t \ge 2\text{,}\) \(\displaystyle 3 \le k \le 14\text{,}\) and \(\displaystyle t\lt k\text{.}\)

Now

which means that

is an integer.

Furthermore, we have \(\displaystyle \binom{k-1}{t-1}\) divides \(\displaystyle \binom{14}{t-1}\text{,}\) so that \(\displaystyle \frac{(k-1)!}{(k-t)!}\) divides \(\displaystyle \frac{14!}{(15-t)!}\text{.}\) In other words,

is an integer. If we call this integer \(\displaystyle y\text{,}\) combining this with the previous paragraph tells us that \(\displaystyle k\) is a divisor of \(\displaystyle 15y\text{.}\) We can also further work with the algebra to obtain

When \(\displaystyle k=14\text{,}\) this gives \(\displaystyle y=14/(15-t)\text{.}\) Since \(\displaystyle k\) divides \(\displaystyle 15y\) and \(\displaystyle k\) is coprime to \(\displaystyle 15\text{,}\) we must have \(\displaystyle k\) divides \(\displaystyle y\text{.}\) But then \(\displaystyle y/14=1/(15-t)\) is an integer, implying \(\displaystyle t=14\text{.}\) This contradicts \(\displaystyle t\lt k\text{.}\) Thus \(\displaystyle k=14\) cannot arise.

When \(\displaystyle k=13\) this gives \(\displaystyle y=\frac{14 \cdot 13}{(15-t)(14-t)}\text{.}\) Since \(\displaystyle k\) divides \(\displaystyle 15y\) and \(\displaystyle k\) is coprime to \(\displaystyle 15\text{,}\) we must have \(\displaystyle k\) divides \(\displaystyle y\text{.}\) But then \(\displaystyle \frac{y}{13}=\frac{14}{(15-t)(14-t)}\) is an integer. Since \(\displaystyle t\lt k=13\text{,}\) we have \(\displaystyle 14-t \ge 2\text{,}\) but no two consecutive integers each of which is at least \(\displaystyle 2\) are both divisors of \(\displaystyle 14\text{,}\) a contradiction. Thus \(\displaystyle k=13\) cannot arise.

When \(\displaystyle k=12\text{,}\) this gives

Now \(\displaystyle k\) dividing \(\displaystyle 15y\) implies that

is an integer. Since the numerator is not a multiple of \(\displaystyle 2^2\text{,}\) the denominator cannot be either, leaving only the possibilities \(\displaystyle t=4,8\text{.}\) Since the numerator is not a multiple of \(\displaystyle 3^2\text{,}\) the denominator cannot be either, which eliminates \(\displaystyle t=4\text{.}\) When \(\displaystyle t=8\text{,}\) the numerator of \(\displaystyle y\) is not a multiple of \(\displaystyle 5\text{,}\) but the denominator is, so this is also impossible. Thus \(\displaystyle k=12\) cannot arise.

When \(\displaystyle k=11\) this gives

Since \(\displaystyle k\) divides \(\displaystyle 15y\) and \(\displaystyle k\) is coprime to \(\displaystyle 15\text{,}\) we must have \(\displaystyle k\) divides \(\displaystyle y\text{.}\) But then

is an integer. Since the numerator is not a multiple of \(\displaystyle 5\text{,}\) the four consecutive numbers that are the factors of the denominator must be \(\displaystyle 6\) through \(\displaystyle 9\) (since \(\displaystyle t \ge 2\text{,}\) they cannot be \(\displaystyle 11\) through \(\displaystyle 14\text{,}\) and since \(\displaystyle t\lt 11\) they cannot be \(\displaystyle 1\) through \(\displaystyle 4\)). Thus, we must have \(\displaystyle t=6\text{.}\) But then the numerator is not divisible by \(\displaystyle 3^2\text{,}\) while the denominator is divisible by \(\displaystyle 3^3\text{,}\) contradicting \(\displaystyle y/11\) being an integer. Thus \(\displaystyle k=11\) is not possible.

When \(\displaystyle k=10\text{,}\) this gives

Now \(\displaystyle k\) dividing \(\displaystyle 15y\) implies that

is an integer. Since the numerator is not a multiple of \(\displaystyle 2^4\text{,}\) the denominator cannot be either. In particular, \(\displaystyle 8\) cannot be one of the factors that appears in the denominator (since some other even factor would appear with it), nor can \(\displaystyle 2\text{,}\) \(\displaystyle 4\text{,}\) and \(\displaystyle 6\) all be factors that appear in the denominator. Also, the numerator is not divisible by \(\displaystyle 3^3\text{,}\) so we cannot have \(\displaystyle 11-t=9\text{.}\) This leaves \(\displaystyle t=8\) as the only possibility. However, the numerator of \(\displaystyle y\) is not divisible by \(\displaystyle 3^2\text{,}\) so \(\displaystyle t=8\) is also not possible. Thus \(\displaystyle k=10\) is not possible.

When \(\displaystyle k=9\text{,}\) we see that

So \(\displaystyle k\) dividing \(\displaystyle 15y\) gives

being an integer. Since the numerator is not divisible by \(\displaystyle 2^5\text{,}\) the denominator cannot be either. In particular, \(\displaystyle 8\) cannot appear as one of the factors in the denominator (or two other numbers divisible by \(\displaystyle 2\) would also appear as factors), so the only possibility is \(\displaystyle t=8\text{.}\) However, if we take \(\displaystyle k=9\text{,}\) \(\displaystyle t=8\text{,}\) and \(\displaystyle i=2\text{,}\) the necessary condition is \(\displaystyle \binom{7}{6}=7\) divides \(\displaystyle \binom{13}{6}\text{,}\) which is not true. Thus, \(\displaystyle k=9\) is not possible.

When \(\displaystyle k=8\text{,}\) we calculate

Since \(\displaystyle k\) divides \(\displaystyle 15y\) and \(\displaystyle k\) is coprime to \(\displaystyle 15\text{,}\) we must have \(\displaystyle k\) divides \(\displaystyle y\text{.}\) But then

Since the consecutive factors in the denominator include \(\displaystyle 8\) and at least two other even numbers, this implies that the numerator should also be a multiple of \(\displaystyle 2^5\text{,}\) but it is not. Thus \(\displaystyle k=8\) is not possible.

When \(\displaystyle k=7\) we see that

Since the consecutive factors in the denominator include \(\displaystyle 6\) and \(\displaystyle 9\text{,}\) if they also include another multiple of \(\displaystyle 3\) then the numerator must be divisible by \(\displaystyle 3^4\text{,}\) but it is not. This leaves the possibility that \(\displaystyle t=4\) so the factors in the denominator are \(\displaystyle 4\) through \(\displaystyle 11\text{,}\) but this is divisible by \(\displaystyle 5^2\text{,}\) which the numerator is not. Thus, \(\displaystyle k=7\) is not possible.

If \(\displaystyle k=6\) then

So \(\displaystyle k\) dividing \(\displaystyle 15y\) gives

being an integer. The numerator is not divisible by \(\displaystyle 2^8\text{,}\) so the denominator cannot be either; in particular it cannot include as factors all of the even integers from \(\displaystyle 4\) through \(\displaystyle 10\) as well as one other. This leaves the possibilities \(\displaystyle t=2\) and \(\displaystyle t=4\text{.}\) If \(\displaystyle t=2\) then \(\displaystyle y=14/5\) which is not an integer, and similarly if \(\displaystyle t=4\) then we have \(\displaystyle y=\frac{14\cdot 13\cdot 12}{5\cdot 4\cdot 3}\) which is not an integer. So \(\displaystyle k=6\) is not possible.

If \(\displaystyle k=5\) then

The numerator is not divisible by \(\displaystyle 2^9\text{,}\) so the denominator cannot be either; in particular, the denominator cannot include all of \(\displaystyle 4\text{,}\) \(\displaystyle 6\text{,}\) \(\displaystyle 8\text{,}\) \(\displaystyle 10\text{,}\) and \(\displaystyle 12\) as factors in the product. This leaves only the possibility \(\displaystyle t=4\text{.}\) If \(\displaystyle k=5\) and \(\displaystyle t=4\) then \(\displaystyle i=0\) gives \(\displaystyle \binom{5}{4}=5\) divides \(\displaystyle \binom{15}{4}=1365\) which is true; \(\displaystyle i=1\) gives \(\displaystyle \binom{4}{3}=4\) divides \(\displaystyle \binom{14}{3}=364\) which is true; \(\displaystyle i=2\) gives \(\displaystyle \binom{3}{2}=3\) divides \(\displaystyle \binom{13}{2}=78\text{,}\) which is true; \(\displaystyle i=3\) gives \(\displaystyle \binom{2}{1}=2\) divides \(\displaystyle \binom{12}{1}=12\text{,}\) which is true. Thus a \(\displaystyle 4-(15,5,1)\) design could exist, but this is the only possibility with \(\displaystyle k=5\text{.}\)

When \(\displaystyle k=4\) we have

The denominator includes \(\displaystyle 3\text{,}\) \(\displaystyle 6\text{,}\) \(\displaystyle 9\text{,}\) and \(\displaystyle 12\text{,}\) so is divisible by \(\displaystyle 3^5\text{,}\) but the numerator is not. Thus, \(\displaystyle k=4\) is not possible.

If \(\displaystyle k=3\) then \(\displaystyle 2 \le t\lt k\) implies \(\displaystyle t=2\text{.}\) We know these parameters are possible, as these are the parameters of a Steiner triple system.