Using your Head is Permitted

September 2007 riddle

This month's riddle comes from Oded Margalit, who describes it as "a well known design problem".

In graph theory, a pair <V,E> is called a graph if V is a set of vertices and E is a set of edges between those vertices. An edge is described by the pair of vertices it connects. A subgraph <V',E'> of a graph <V,E> is a graph satisfying that V' is a subset of V and E' is a subset of E.
A clique is a graph where E contains all possible edges between pairs of V and a k-clique is a clique that has exactly k vertices.

This month's riddle relates to the following problem:
Given a pair of numbers, <m,n>, is it possible to partition (the edges of) an n-clique into a set of m-cliques?
In other words, we are looking for a set in which each member is an m-clique, each m-clique is a subgraph of the original n-clique and each edge of the n-clique appears in exactly one member of the set.

We do not request a solution for a general <m,n> pair, but rather want to consider certain specific values of m and n.
Here are the pairs that interest us:

  1. <3,655>
  2. <4,256>
  3. <5,576>
  4. <6,781>
  5. <7,345>
For each of these, determine (with proof) whether there is a solution to the partitioning problem with these values.
The names of solvers who will prove correctly for at least 3 of the 5 pairs will be posted. (They don't necessarily need to be the first three pairs.) Separate lists will be maintained for solvers who proved for 3, 4 and all 5 pairs.

As a bonus question, try to give an exact characterization for which n the pair <3,n> can be partitioned.

List of solvers:

Three pairs:

Or Sheffet (9 September 17:50)

Four pairs:


Five pairs:

Alon Amit (15 September 16:20)

Elegant solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page