Minimalist solution to Kirkman's 15 girls' walking problem：Equivalent simplified alternative problem for 7 boys' walking

2023年11月23日 17:47

Minimalist solution to Kirkman's 15 girls' walking problem
-----Equivalent simplified alternative problem for 7 boys' walking

Liang Haisheng 2019/11

Abstract: The purpose of this paper is that the answers to the original questions so far are basically very complicated and difficult to remember. For example [1], they are inseparable from 15 numbers. Therefore, it is proposed to simplify the original Kirkman Kirkman 15 girls’ walking problem into the equivalent same week 7 Questions 1 and 2 of Boys Walking are simplified to seven numbers that are less than half of the discussion, thereby simplifying the reasoning process of Kirkman 15 Girls Walking Questions, and arriving at a very simple solution that is easy to understand and remember. Questions and answers are simplified and optimized at the same time to achieve an essential structure that analyzes the solution. In this way, even primary school students who do not understand mathematics can understand and memorize the answers.

Keywords: Kirkman, RBIBD, incomplete block design, combinatorial design

1. The problem of boys walking and the definition of rotation vector

Question 1: There is a math teacher Hansen in a boarding school. After dinner, Teacher Hansen takes 7 boys in the same dormitory for a walk every day. Teacher Hansen is thinking about a question. Seven boys walked in a row of three. Every day only three of them walked in a row, and the other four walked alone without a row. How to arrange walks within a week so that a certain boy and the other six boys have the opportunity to walk in the same row and only once?

Define a rotation vector L with a length of N and an initial value of O, expressed as LN(O)={1, 2, 3, 4, 5, 6, ....N}, 0<O<=N. Its value is l(n) =n-1. n<N
L(1) = {1, 2, 3, 4, 5, 6,....N}, L(2) = {2, 3, 4, 5, 6, 7....N, 1} , L(3) = {3, 4, 5, 6, 7, 8....N, 1, 2}, .... .... .... .... .... . ...
.... .... .... .... .... .... ....
L(N) = { N, 1, 2, 3, 4, 5, 6, ....N-1 } L(N+1) = {1, 2, 3, 4, 5, 6, .... ..N},
Define the operation algorithm L(n)+ s = L(n+ s), s is a positive integer, s 〈= N. Abbreviated as [n, s]. Define [n, s] = [m, t] as any pairwise relationship in the order of [n, s] does not coincide with any pairwise relationship in [m, t].
Let's number the seven students walking in the problem from 1 to 7. The leader’s teacher number is 0.
Let's discuss the L vector with a vector length of 7. The initial L(1) can be omitted as L ()= {1, 2, 3, 4, 5, 6, 7};
Because there are three people in a row, we use the vector L of the three states, and the position order is the arrangement order of the 7 days from Monday to Sunday. Monday Tuesday Wednesday Thursday Friday Saturday Sunday
L= {1, 2, 3, 4, 5, 6, 7}; L= {1, 2, 3, 4, 5, 6, 7}; L= {1, 2, 3, 4, 5, 6 ,7};
Such an arrangement is not feasible to repeat. Only "rotating" the second and third L satisfies the conditions for a non-repetitive problem of three people in a row every day. We get three vector permutations
Monday Tuesday Wednesday Thursday Friday Saturday Sunday
L(1)= {1, 2, 3, 4, 5, 6, 7};
L(3)= {3, 4, 5, 6, 7, 1, 2};
L(4)= {4, 5, 6, 7, 1, 2, 3}; Row 1
There are 7x6=42/2=21 combinations of pairs among seven people. There are exactly 21 kinds of three kinds of pairwise relationships every day in the above seven days.
The remaining 4 people are not in a row of three, and the 4 people in the scattered row can be expressed like this (the scattered row is helpless, because all 21 three-row combinations with a two-two relationship or above have been used up, and no two rows can be arranged without making two-by-two. The relationship is not repeated).
L(2)= L(5)= L(6)= L(7)=
Monday Tuesday Wednesday Thursday Friday Saturday Sunday
{2, 3, 4, 5, 6, 7, 1}; Row 2 {5, 6, 7, 1, 2, 3, 4}; Row 3 {6, 7, 1, 2, 3, 4 , 5}; Row 4 {7, 1, 2, 3, 4, 5, 6}; Row 5
It can be seen that the seven students every day from Monday to Sunday are neither repeated nor missing. Issue 1 is resolved.

L(4)= {4, 5, 6, 7, 1, 2, 3};
L’(5)= {5’, 6’, 7’, 1’, 2’, 3’, 4’};
L'(6)={6', 7', 1', 2', 3', 4', 5'}; Group 2 L(6)={6, 7, 1, 2, 3, 4, 5};
L’(2)= {2’, 3’, 4’, 5’, 6’, 7’, 1’};
L'(4)= {4', 5', 6', 7', 1', 2', 3'}; Group 3 L(7)= {7, 1, 2, 3, 4, 5, 6};
L’(7)= { 7’, 1’, 2’, 3’, 4’, 5’, 6’ };
L'(3)= {3', 4', 5', 6', 7', 1', 2'}; Group 4 L(2)={2, 3, 4, 5, 6, 7, 1 };
L’(1)= { 1’, 2’, 3’, 4’, 5’, 6’, 7’ };
L(5)= {5, 6, 7, 1, 2, 3, 4};
L(0)= {0, 0, 0, 0, 0, 0, 0} Group 5
Monday Tuesday Wednesday Thursday Friday Saturday Sunday General explanation 1
After verification, it was found that there were no repeated elements within the five groups, and there were no repeated relationships between the groups. Get a general solution. We define L’(n)= { n+7 } on the general solution, then replace all the lattice values of L’ in the above table. We get the minimalist answer
L(1)= L(3)= L(4)=
Monday Tuesday Wednesday Thursday Friday Saturday Sunday
{1, 2, 3, 4, 5, 6, 7};
{3, 4, 5, 6, 7, 1, 2}; Group 1 {4, 5, 6, 7, 1, 2, 3};
Group 2
Group 3
{12, 13, 14, 8, 9, 10, 11}; {13, 14, 8, 9, 10, 11, 12};
L’(5)=
L’(6)=
L(6)= {6, 7, 1, 2, 3, 4, 5};
L'(2)= {9, 10, 11, 12, 13, 14, 8}; L'(4) = {1 1, 1 2, 1 3, 1 4, 8, 9, 1 0}; L (7)= {7, 1, 2, 3, 4, 5, 6};
L’(7)= {14, 8, 9, 10, 11, 12, 13};
L’(3)= {10, 11, 12, 13, 14, 8, 9}; Group 4 L(2)= {2, 3, 4, 5, 6, 7, 1};
L’(1)= {8, 9, 10, 11, 12, 13, 14};
L(5)= {5, 6, 7, 1, 2, 3, 4};
L(0)= {0, 0, 0, 0, 0, 0, 0,} Group 5
The above is actually the minimalist answer to Kirkman’s girl walking question. So the same week 7 boys question 1 question 2 presented in this article simplifies the original Kirkman 15 girls question holds.
on Monday
Tuesday
Wednesday
Thursday
Friday
Saturday
Sunday
134
245
356
467
157
126
237
6 12 13
7 13 14
1 8 14
289
3 9 10
4 10 11
5 11 12
7 9 11
1 10 12
2 11 13
3 12 14
4 8 13
5 9 14
6 8 10
2 10 14
3 8 11
4 9 12
5 10 13
6 11 14
7 8 12
1 9 13
580
690
7 10 0
1 11 0
2 12 0
3 13 0
4 14 0
Kirkman's Girl's Walking Problem, known in mathematics as RBIBD. The description of the problem is: A female teacher leads 15 girls in her class to go for a walk every day. She divides these girls into 5 groups of 3 and asks if they can make A group plan of walking for 7 consecutive days, so that any two girls are assigned to one group and only one group.
Kirkman, the person who asked the original question, published his own answer in the same publication as follows (1 to 15 represents 15 girls):

Sunday {1, 2, 3}, {4, 8, 12}, {5, 10, 15}, {6, 11, 13}, {7, 9, 14}; Monday {1, 4, 5} , {2, 8, 10}, {3, 13, 14}, {6, 9, 15}, {7, 11, 12}; Tuesday {1, 6, 7}, {2, 9, 11}, {3, 12, 15}, {4, 10, 14}, {5, 8, 13}; Wednesday {1, 8, 9}, {2,12,14}, {3, 5, 6}, { 4, 11, 15}, {7, 10, 13}; Thursday {1, 10, 11}, {2, 13, 15}, {3, 4, 7}, {5, 9, 12}, {6 , 8, 14}; Friday {1, 12, 13}, {2, 4, 6}, {3, 9, 10}, {5, 11, 14}, {7, 8, 15}; Saturday {1 , 14, 15}, {2, 5, 7}, {3, 8, 11}, {4, 9, 13}, {6, 10, 12}.
3. The number of different structures of the answer to the original girl’s walking question
I have a Kirkman Girls Walking Problem - Answer Number Theorem for the above answer
Kirkman Girls' Walking Problem: There are 15 girls in a class at a girls' school. They walk in groups of 3 every day. Ask how to arrange it during the week so that any girl can walk in the same group as other girls.
Definition 1: The 35 combinations of three people that are consistent with the solution to Kirkman’s girls walking problem are C(x,y,z), x,y,z are the codes of the same group of girls.
Theorem 1 (Kirkman Girls Walking Problem - Number of Answers in a Day Theorem 1): The maximum possible number of combinations of 5 C(x,y,z) combinations in one day that are consistent with the solution to Kirkman Girls Walking Problem is 56.
Proof: First, arbitrarily select any one of the 35 types of C in definition 1, labeled C1 (1, 2, 3), as the first layer. There are 7 types of c1 that conform to definition 1 and include 1, and conform to definition 1 and include 2. However, there are 6 types of c2 that do not contain 1. There are 6 types of c3 that meet the definition 1 and contain 3 but do not contain 1, for a total of 7+6+6=19 types.
Because C(1,2,3) has already appeared, so according to definition 1 there is no c(2,3,x), that is, there is no overlap among the above 19 types. Then select the second layer. There are 35-19=16 types of C that can be selected for the second layer that meets definition 1. Mark the selected second layer as C2(4,5,6). Suppose c that does not contain C2 but contains 4 is c4, c that does not contain C2 but contains 5 is c5, c that does not contain C2 but contains 6 is c6, then all cC2-456 that does not contain C2 but contains 4/5/6 The types are c4+c5+c6=6+6+6=18 types. Adding C2, there are 19 types of c456 including 4/5/6. According to definition 1, there are three types of c1 containing 4/5/6, labeled c1-456. There are three types of c2 that also contain 4/5/6, labeled c2-456. There are three types of c3 containing 4/5/6. 3 species are marked c3-456. c1-456 + c2-456 + c3-456 =3+3+3=9, that is, there are 9 types of c456-123 that include 4/5/6 but do not include 1/2/3. All c456 minus c456-123 is 19-9=10, that is, according to definition 1 and C2 (4,5,6), there are 10 kinds of c that cannot be arranged on the same day. That is to say, there are only (35-19)-10=6 optional types in the third layer that meet definition 1.
Finally, select the 3rd layer. Obviously, after the 3rd layer C3 is selected, the 4th and 5th layers C4 and C5 have the only choice. The following proves that according to definition 1, if there are three layers C1C2C3, then there must be the 4th and 5th layers C4C5 that meet definition 1. By contradiction, suppose that for all arbitrarily chosen C1C2C3 that satisfies Definition 1, there is no C4C5 that satisfies Definition 1. Then, since Definition 1 must have a solution condition, for a certain C1C2C3 of the solution, 4C5 exists, which means that the hypothesis does not hold. So if you select arbitrarily the 3-layer C1C2C3 that meets definition 1, then there must be a specific C4C5 in the 4th and 5th layers that meets definition 1. There are 5 layers C in a day defined as 1, and the number of possible permutations of 1 layer C in any of the 5 layers C is 5x4x3=60. The number of all possible permutations of 3 layers that meet definition 1 is selected from any 35, which is 35x16x6=3360. According to definition 1, the number of possible combinations of the selected 3 layers is 3360/60=56.
Since the above-mentioned selection of 3 layers is to determine the 4th and 5th layers, the proposition in Theorem 1 that the maximum number of possible combinations is 56 is established.
Theorem 2: (Kirkman's Girl's Walking Problem - Number of Answers in One Week Theorem 2): The maximum number of possible combinations consistent with the solution to Kirkman's Girl's Walking Problem (one week) is 240. The proof with the help of a computer program has been completed, but the manual proof has not yet been completed.
4. Trigonometric graphical transformation of general solutions
We define L’(n)= {2 n-1}, L(n)= {2 n} on the general solution
L(1)= {1, 2, 3, 4, 5, 6, 7}; L(3)= {3, 4, 5, 6, 7, 1, 2}; Group 1 L(4)= {4, 5, 6, 7, 1, 2, 3};
L’(5)= {5’, 6’, 7’, 1’, 2’, 3’, 4’};
L'(6)= {6', 7', 1', 2', 3', 4', 5'}; Group 2 L(6)= {6, 7, 1, 2, 3, 4, 5};
L'(2)= {2', 3', 4', 5', 6', 7', 1'}; L'(4)= {4', 5', 6', 7', 1' , 2', 3' }; Group 3 L(7)= {7, 1, 2, 3, 4, 5, 6};
L’(7)= {7’, 1’, 2’, 3’, 4’, 5’, 6’};
L'(3)= {3', 4', 5', 6', 7', 1', 2'}; Group 4 L(2)= {2, 3, 4, 5, 6, 7, 1};
L’(1)= {1’, 2’, 3’, 4’, 5’, 6’, 7’};
L(5)= {5, 6, 7, 1, 2, 3, 4}; Group 5 L(0)= {0, 0, 0, 0, 0, 0, 0,}
Monday Tuesday Wednesday Thursday Friday Saturday Sunday General explanation 1
5

Then replace all the grid values of L and L’ in the above table. We get the "odd and even solution"
L(1)= L(3)= L(4)=
L’(5)= L’(6)= L(6)=
L’(2)= L’(4)= L(7)=
L’(7)= L’(3)= L(2)=
L ’( 1 ) = L(5)= L(0)=
on Monday
268 91112 3 7 14 13 5 4 1 10 0
{2, 4, 6, 8, 10, 12, 14};
{6, 8, 10, 12 14, 2, 4}; Group 1 {8, 10, 12, 14, 2, 4, 6};
{9, 11, 13, 1, 3, 5, 7};
{11, 13, 1’, 3, 5, 7, 9}; Group 2 {12, 14, 2, 4, 6, 8, 10};
{3, 5, 7, 9, 11, 13, 1};
{7, 9, 11, 13, 1, 3, 5}; Group 3 {14, 2, 4, 6, 8, 10, 12};
{13, 1, 3, 5, 7, 9, 11};
{5, 7, 9, 11, 13, 1, 3}; Group 4
{4, 6, 8, 10,
{1, 3, 5, 7, {10, 12, 14, 2, {0, 0, 0, 0,
Monday Tuesday Wednesday Thursday Tuesday Wednesday
4 8 10 61012 11 13 14 1312 592 7114 176 398
3 12 0 5140
12, 14, 2}; 9, 1 1, 1 3};
4, 6,
0, 0, Friday Saturday
Thursday
81214 134 9136 51110 720
8 }; Group 5
0, } Sunday
odd-even solution
Friday Saturday Sunday

10 14 2 356 11 1 8 7 13 12 940
12 2 4 1446 578 7910 13 3 10 1512 9 1 14 1132 11 6 0 1380
Let’s look at the bottom line, 1 10 0-》3 12
Grid rotation. Then we can draw five triangles marked with 14 equal scales in a circle to represent the conclusion of this odd and even solution.

0-》5 14 0 Monday, Tuesday and Wednesday are the rotation of two squares and two squares. the other four lines

This picture shows Monday’s position. The ones with zeros in the bottom row are 1 10 0. We treat the numbers in the outer circle as a movable turntable. Then, if the number turntable rotates two grids clockwise, the ones with zeros in the bottom row are the corresponding triangles of 13 8 0 It's on Sunday, one day back. In the same way, turn the digital dial two spaces clockwise to get the Saturday position, and so on, after turning it seven times, it will return to the original position of Monday.
Return to the general explanation of the three sections 1
L(1)= {1, 2, 3, 4, 5, 6, 7}; L(3)= {3, 4, 5, 6, 7, 1, 2}; Group 1 L(4)= {4, 5, 6, 7, 1, 2, 3};
L’(5)= {5’, 6’, 7’, 1’, 2’, 3’, 4’};
L'(6)={6', 7', 1', 2', 3', 4', 5'}; Group 2 L(6)={6, 7, 1, 2, 3, 4, 5};
L’(2)= {2’, 3’, 4’, 5’, 6’, 7’, 1’};
L'(4)= {4', 5', 6', 7', 1', 2', 3'}; Group 3 L(7)= {7, 1, 2, 3, 4, 5, 6};
L'(7)= {7', 1', 2', 3', 4', 5', 6'}; L'(3)= {3', 4', 5', 6', 7' , 1', 2' }; Group 4 L(2)={2, 3, 4, 5, 6, 7, 1 };
L'(1)= {1', 2', 3', 4', 5', 6', 7'}; L(5)= {5, 6, 7, 1, 2, 3, 4}; L(0)= {0, 0, 0, 0, 0, 0, 0,} Group 5
Monday Tuesday Wednesday Thursday Friday Saturday Sunday General explanation 1
We also draw five triangles according to general solution 1. The difference is that the number wheel can be divided into two parts of two circular circles, one part is the seven numbers 1,23,4,5,6,7 of L. The other part is the seven numbers 1' of L', 2', 3', 4', 5', 6', 7'. I boldly make a conjecture that all the solutions to different triangle positions in rotation cover various answers to Kirkman's girls' walking problem (triangular geometric solution) .

It can be seen that there are nails in 7 equal parts on each of the two outer rings of the disk, a total of 14 nails. Adding the nail in the center of the circle, there are 15 nails. Five different colored rubber bands are placed around the spikes at the top corners of the corresponding triangles. By rotating the two disks, various triangular combinations can be obtained. As shown in Figure 6

Complete text.
The next topic is to demonstrate that all solutions to Kirkman's walking problem can be decomposed into the above 7-7 groupings.

この記事が気に入ったらサポートをしてみませんか？