SoylentNews is people
SoylentNews
Wired have come up with an interesting conundrum which will keep some of you (and me) thinking for a while:
In 1850, the Reverend Thomas Kirkman, rector of the parish of Croft-with-Southworth in Lancashire, England, posed an innocent-looking puzzle in the Lady’s and Gentleman’s Diary, a recreational mathematics journal:
“Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast.” (By “abreast,” Kirkman meant “in a group,” so the girls are walking out in groups of three, and each pair of girls should be in the same group just once.)
Pull out a pencil and paper, and you’ll quickly find that the problem is harder than it looks: After arranging the schoolgirls for the first two or three days, you’ll almost inevitably have painted yourself into a corner, and have to undo your work.
[...]
Yet for more than 150 years after Kirkman circulated his schoolgirl problem, the most fundamental question in the field remained unanswered: Do such puzzles usually have solutions? Kirkman’s puzzle is a prototype for a more general problem: If you have n schoolgirls, can you create groups of size k such that each smaller set of size t appears in just one of the larger groups? Such an arrangement is called an (n, k, t) design. (Kirkman’s setup has the additional wrinkle that the groups must be sortable into “days.”)
It’s easy to see that not all choices of n, k and t will work. If you have six schoolgirls, for instance, you can’t make a collection of schoolgirl triples in which every possible pair appears exactly once: Each triple that included “Annabel” would contain two pairs involving her, but Annabel belongs to five pairs, and five is not divisible by two. Many combinations of n, k and t are instantly ruled out by these sorts of divisibility obstacles.
For the parameters that aren’t ruled out, there’s no royal road to finding designs. In many cases, mathematicians have found designs, through a combination of brute force and algebraic methods. But design theorists have also found examples of parameters, such as (43, 7, 2), that have no designs even though all the divisibility requirements check out. Are such cases the exception, mathematicians wondered, or the rule? “It was one of the most famous problems in combinatorics,” said Gil Kalai, a mathematician at the Hebrew University of Jerusalem. He recalls debating the question with a colleague a year and a half ago, and concluding that “we’ll never know the answer, because it’s clearly too hard.”
But he was wrong .... Read the full linked article for more.
Original Submission
(Score: 0) by Anonymous Coward on Monday June 22 2015, @03:33PM
"Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast.” doesn't mean what you think it means. The girls walk abreast, which means next to eachother (so not in a group, but in a row!). So they walk 3 next to each other, for 7 days, so that no 2 will walk abreast (so next to eachother) for more than one day. So 2 girls can be in twice in a row of three girls, as long as they are not next to eachother. So if the girls are numbered 1 to 15 then a day 1 group might be 1-2-3 where a day 2 group might be 1-4-3. Girls 1 and 3 are not abreast so both groups are legal.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @04:35PM
Ah ok. That makes sense. As if they can not be in the same group then the best you can do is 5 days before deadlock sets in.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @05:09PM
> So they walk 3 next to each other, for 7 days, so that no 2 will walk abreast (so next to eachother) for more than one day
Er, no. [google.com]
(Score: 0) by Anonymous Coward on Monday June 22 2015, @06:48PM
er yes...
FROM the summary "so that no two shall walk twice abreast"
Meaning (A B C) is OK for the first day but (A B D) is not OK for the second day but (A D B) is OK.
If it were not true then if you hold column1 fixed (because order does not mater then). Then rotate the second and third columns only and they can not be in the same group you would run out after 5 combinations. Because column 2 or 3 would repeat after the 5th permutation. The only way you can get to 7 is if if they can be in the same group but not next to each other ever again. Computing the upper bound on that is a bit trickier.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @09:13PM
No, that is incorrect. The rules are: 15 girls; 7 days; 5 pairwise disjoint subsets of 3 girls each per day; if two girls are in the same subset, they must not be in another subset together on a different day.
Anna-Bertha-Carla in a row on one day and Anna-Doris-Carla in a row on another day is not allowed, because Anna and Carla are in two subsets together.
There is a link to a solution in the article.