Using your Head is Permitted

September 2007 solution

<7,345> - no partitioning exists

A 7-clique has 7*6/2=21 edges.
A 345-clique has 345*344/2=59340 edges.
59340 is not divisible by 21, making the <7,345>-partitioning problem unsolvable. It is impossible to partition a set of 59340 edges into disjoint sets each containing 21 edges.

<5,576> - no partitioning exists

Consider one vertex of the 576-clique. There are 575 edges connecting with this vertex. Now consider all 5-cliques containing the vertex. Each has 4 edges connecting with it. Because 575 does not divide by 4, it is impossible to solve this partitioning problem. The set of 575 edges cannot be partitioned into disjoint sets of size 4.

<4,256> - a partitioning exists

Here m=22 and n=m4.
We will prove the following more general theorem:

Theorem 1: If m=pk and n=ml with prime p and natural k and l, then a solution exists.

We will prove this theorem by creating an explicit partitioning solution.
If m=pk and n=ml then one can find a finite field F with m elements and a vector space U with n elements over F.
Let the n-clique's vertices be the members of U. The subsets of size m that will compose the m-cliques' vertices will be the sets in U forming affine subspaces of dimension 1.
In other words, for every two elements A and B in U, such that A isn't the zero element of U, we will use the elements Y of U satisfying Y=Ax+B, for some element x in F as vertices of an m-clique. There are clearly exactly m such elements for every choice of A and B, because there are m values that can be substituted for each x, and if two of them yield the same Y then Ax+B=Ax'+B can be solved to show that A is the zero vector. Furthermore, every edge will appear in exactly one m-clique because each edge signifies a pair of points in U and each m-clique is a line in U: through each two points passes exactly one line.

<6,781> - a partitioning exists

Here m=51+1 and n=(51*(4+1)-1)/(51-1). We will prove the more general claim:

Theorem 2: For any prime p and any naturals k and l, if m=pk+1 and n=(pk(l+1)-1)/(pk-1), then the <m,n> partitioning problem has a solution.

The simplest way to show this is by use of projective geometry. Consider the vector space (pk)l+1, minus the zero element, where any two of the remaining elements are considered equivalent if one is a scalar multiple of the other (a homothety relation). The projective space now has (pk(l+1)-1)/(pk-1) different elements and any line in it (a 2D linear subspace in the original vector space) has (p2k-1)/(pk-1), or simply pk+1, elements.

However, for all unfamiliar with projective geometry, here is a construction that doesn't require it. We will prove the theorem, instead, by means of the following definition and two lemmas.

Definition: An <m,n> partitioning will be called separable if the n(n-1)/m/(m-1) m-cliques can be partitioned into (n-1)/(m-1) subsets, each of size n/m in such a way that the vertices of the m-cliques in each subset are pairwise disjoint.

Lemma 1: The <m,n> clique partitioning problem has a solution if <m,(n-1)/(m-1)> has a solution and <m-1,n-(n-1)/(m-1)> has a separable solution.

In order to prove this, we will construct the partitioning explicitly. This is done by separating the n vertices into two sets. Set A will contain (n-1)/(m-1) vertices and set B will contain the remainder. B's separable partitioning creates (n-1)/(m-1) subsets of m-1-cliques. Arbitrarily match each subset with a unique member of A and join this member to all m-1-cliques in the subset to form m-cliques. These cliques, when united with the cliques forming the partitioning of A, are a solution to the entire <m,n> partitioning problem. All edges within A are represented, because we've included a partitioning of A. All edges within B are represented because we've included a partitioning of B. Lastly, all edges between A and B are represented, because each member of A has been assigned to m-1-cliques that have, as the union of their vertices, all of B, as is the property of separable partitionings.

Lemma 2: The partitioning presented in the proof of theorem 1 is separable.

Again, we will construct the subsets explicitly. In theorem 1, the partitioning was to all affine subspaces of dimension 1. The subsets we search for here are all quotient spaces of the linear subspaces of dimension 1.
Plainly, we will group together all m-cliques that share the same A. (Or, equivalently, whose As are scalar multiples of one another. These must be pairwise disjoint, because the m-cliques in each subset represent parallel lines in U, and parallel lines do not intersect.

Armed with these new lemmas, we are now able to prove theorem 2. We will prove this by induction over l. First, if l=1 then the claim degenerate to the trivial <m,m> question, which obviously has a partitioning.
Next, let us assume that we already have a partitioning for <m,n'=(pk(l+1)-1)/(pk-1)> and we want to create a solution for <m,n=(pk(l+2)-1)/(pk-1)>. Note that n-n'=pk(l+1), so the <m,n-n'> partitioning problem has a separable solution according to lemma 2. Using these two known partitionings, the desired partitioning is given by lemma 1.

<3,655> - a partitioning exists

Here n=(34+1)*23-1. We will prove the following more general theorem:

Theorem 3: If n=(3k+1)2l-1, for naturals k and l, then the <3,n> clique partitioning problem has a solution.

To do this, consider the following lemma:

Lemma 3: If <3,x> has a clique partitioning solution, then so does <3,2x+1>.

The proof of this lemma is by use of lemma 1. In order to comply with the conditions of lemma 1, we must be able to present a separable partitioning for the <2,x+1> problem. Note that x must be odd (or else <3,x> would not have had a solution, for the same reason as <5,576>). We will show that <2,2k> has a separable partitioning for any natural k, so necessarily also for k=(x+1)/2. This is done by the following well-known algorithm: Let the 2k elements be denoted by the numbers 0 through 2k-1. for the i'th subset, choose all pairs a and b satisfying a+b = i (mod 2k-1) with both a and b smaller than 2k-1. This pairs all except ik (mod 2k-1) and 2k-1, so these two are paired together as well. This can easily be ascertained to be a valid separable partitioning.

The proof of the theorem is by induction on l, starting from the solution for n=3k, which was guaranteed by theorem 1, then stepping from l to l+1 by use of lemma 3.

The Bonus Question

The answer is that <3,n> can be partitioned if and only if n is equal (mod 6) to either 1 or 3. This was first shown by Thomas Kirkman in 1846.

For m=3 there are many "expansion laws" of the sort presented by lemma 3, that allow us to create new solutions from existing ones. In order to prove the claim, here are two such laws that we will make use of:

Lemma 4: If <3,a> and <3,b> each has a partitioning solution, then so does <3,(a-1)b+1>.

To prove this, let (a-1)b elements be the pairs (x,y) with x in (mod a-1) and y in (mod b). First, add the following two types of triangles (=3-cliques):

Next, add a new element, z, and connect it to the following triangles: {(u,y),(v,y),z} if {u,v,a-1} is part of the solution for <3,a>.

Lemma 5: If <3,a> and <3,b> each has a partitioning solution, then so does <3,(a-1)(b-1)/2+1>.

Let (a-1)(b-1) elements be denoted by the triplets (u,v,w) with u in (mod (a-1)/2), v in (mod (b-1)/2) and w in {0,1}, and choose a <3,b> partitioning for the numbers in (mod b) that includes all triangles of the form {x,x xor 1,b-1} for x<b-1. This can be achieved with any partitioning simply by renaming the elements. Also, let us define one additional element z.

Now, let us use the following three types of triangles:

It is easy to verify that all edges have been covered exactly once in this way.

With these two lemmas, it is possible to prove the main claim. To do this, let us first note that the condition n=1 or 3 (mod 6) is clearly a necessary one, for the same reasons as those stated in the proof that showed that neither <7,345> nor <5,576> has a partitioning solution.

Next, let us construct an explicit construction for all n of the form 6k+3. Let us describe all elements by a pair (x,y), where x in {0,1,2} and y in {0..2n}. We will use two types of triangles: {(0,y),(1,y), (2,y)} and {(x,y), (x,z), (x+1 mod 3,(y+z)*(n+1) mod (2n+1))} with yz.
It is easy to verify that together these two types of triangles cover every edge of the clique exactly once.

The remaining problems are of the form <3,6k+1>. We claim that all of these have partitionings. We will show this by proving that no <3,n> partitioning problem of this form can be the one with the lowest n that has no partitioning solution. First, consider lemma 4 with a=6l+3 and b=3. This leads to solutions to all n such that n=18l+7. Reversing the roles of a and b, we get partitioning solutions also to all n=12l+7. Next, using the fact that the <3,13> clique-partitioning problem has a solution (a fact that can be ascertained by trial and error), and substituting a=6l+3, b=13 into lemma 5, we get that all <3,n> problems with n of type 36l+13 have partitioning solutions.
These, together, indicate that if there is a lowest number, n, of the form n=6k+1, for which the <3,n> clique-partitioning problem has no solution, it must be of the form 36l+1. However, if it is the lowest such number, then <3,6l+1> has a partitioning solution, meaning that we can substitute a=6l+1, b=13 into lemma 5, proving that <3,n> must have a partitioning, too, contradicting the assumption that a lowest number, n, of the form n=6k+1, exits, for which the <3,n> clique-partitioning problem has no solution.

Summing all conclusions, this proves the claim that the <3,n> clique partitioning problem has a solution if and only if n is equal (mod 6) to either 1 or 3.

Q.E.D.

If you're interested to read more about this type of construction, a slight generalization of the concept is known as a Steiner System. Steiner Systems, in turn, are special cases of Block Designs.

Back to riddle

Back to main page