Kirkman's Kidslogician series
This puzzle and the next one come from design theory. There are many possible ways to formulate them logically, so you should experiment to find one that runs reasonably efficiently. A big hint for this one is that you do best by avoiding boolean (relation) expressions altogether, except for equations and the like.
Nine children walk to school each day in three groups of three. Arrange their walks for four days (Monday to Thursday) so that, in that time, each pair of children walks together in a group just once.
This puzzle was set and solved by T. P. Kirkman in 1847. It is quoted as a motivating problem in combinatorics by P. J. Cameron `Combinatorics’, CUP 1994. Kirkman and Cameron actually refer to the analogous problem for 15 “schoolgirls” in 7 days, but that takes our solver too long when expressed in first order logic. It is known that solutions exist for any number of children congruent to 3 (mod 6). It works with boys as well—hence the gender-neutral title.
The first person, if any, to produce an honest version of the order 15 problem which completes on the solver in less than half a minute may write to me to claim a small prize. (“Honest” means, for example, no canned solutions written in. I shall be the judge of what is honest!)
For those who know some discrete mathematics, this puzzle amounts to finding a resolvable Steiner triple system of order 9 (or order 15 for the larger problem). For those who don’t, what difference does it make!
Solver
Auto Parser Results
No errors found.