Page 51 - tmp
P. 51
Kirkman’s schoolgirl problem
Nikolina Marković
Center for talented youth Belgrade II, Belgrade, nikolinam98@gmail.com
so that h−1 must be divisible by k. if the quotient is marked
1. Introduction by p, i.e. p = , after a short transformations we get:
v = g ∙ k (1)
Kirkman’s problem falls within the area of so-called
“recreational mathematics” and it reads as follows: 15 On the fixed and rotating disc, shown in Figure 1, where the
schoolgirls walk to the school every day in five groups of triangles and dots are marked, we have the solution for
three girls, it is necessary to make a weekly schedule of v=15. Indicated triangles are actually the required triplets
groups so that each pair of schoolgirls is in the same group and therefore, they can’t be compatible. The initial position
only once. In order to solve this and similar, practical where the numbers and dots on both discs overlap, gives the
problems, it is required the knowledge of the combinatorics arrangement of triplets for the first day. The arrangement
methods of the finite groups. Solution of the problem leads for the next six days, we will get by rotating the upper disc
to the so-called Steiner triple system, named after the works for the two units in any direction. This means that point 1 at
of Jacob Steiner. The aim of the present study is to find the the rotating disc should coincide respectively with the
solution for the Kirkman’s problem and its connection with numbers 3, 5, 7, 9, 11, 13 on the fixed disc (or in reverse
the block design and Steiner triple system. order, whatever).
2. Work methods
The problem can be solved by research in many different
ways, but only those types of solutions that are of practical
and theoretical interest are those that are based on the
methodology of mathematics. Firstly, we set the algebraic
conditions for the solution of the problem. The second
approach is to properly generalize the problem and
understand it through solving the simple examples. Some of Figure 1-Solution for v=15
the solutions are presented by using the fixed and rotating The most important application of the Kirkman’s problem
disc. Then, subject to certain rules, we edit a group of 15 is in the development of the basic theory of block designs,
elements and form triplets. We define a block design, with which I was occupied with in the final part of my
Steiner triple system and parameters of Kirkman’s triple paper.
system.
4. Conclusion
3. Research results
Kirkman’s schoolgirl problem does not require the
It doesn’t need much to realize that finding the solution is knowledge of many abstract mathematical methods. For its
not so trivial. solution, it is necessary to know the basic combinatorics
methods of finite groups, and its implementation has
Since the number of girls is positive integer v, and they,
according to the conditions of the task, have to walk every generated the elementary theory of block design.
day in g rows, where each of them consists of k girls, it is
obvious that
5. Literature
v = g ∙ k (1)
Each girls walks with k − 1 different companion every h [1.] D. Cvetković, S. Simić, Kombinatorika i grafovi,
days, therefore she walks with each of hers companions v − Belgrade, 2006
1. Algebraic expression of this condition is: [2.] G. Berman, K. D. Fryer, Introduction to
Combinatorics, New York-London 1972
v − 1 = h (2)
[3.] M. Petković, Zanimljivi problemi velikih
From these two equations we get: matematičara, Belgrade, 2008
[4.] The Astronomic Journal, Cyclic solutions of the
g =h − (3)
school-girl puzzle, vol. VI, 1859-1861.