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: 4, Funny) by Anonymous Coward on Monday June 22 2015, @12:24PM
I want more articles in which some political party is to blame. This is just a bunch of dumb math.
(Score: 2, Funny) by Anonymous Coward on Monday June 22 2015, @01:18PM
That is why we still have slashdot! :)
(Score: 0) by Anonymous Coward on Monday June 22 2015, @01:21PM
That's not a troll; that's sarcasm.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @04:40PM
This article is just a poof that being anti (anti-slashdot) does not make content automatically better. This 'summary' is basically advertisement for the site.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @05:25PM
Yeah, we heard you the first time.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @12:46PM
(Score: 0) by Anonymous Coward on Monday June 22 2015, @12:49PM
Scratch that, I misread something in the question. It was groups of three, not thee groups.
(Score: 3, Informative) by zocalo on Monday June 22 2015, @01:44PM
UNIX? They're not even circumcised! Savages!
(Score: 1, Funny) by Anonymous Coward on Monday June 22 2015, @05:17PM
"Girl A" can only be with "Girl B" once, so you can't just swap "Girl C" for "Girl D" in the first triplet and move onto the next one.
They use those same rules in porn, don't they? Maybe we should ask someone in that industry?
(Score: 2) by davester666 on Wednesday June 24 2015, @06:30AM
I was too distracted from visualizing 15 nude ladies walking around to even bother trying to figure out how to make sure they didn't couple more than once a week.
(Score: 4, Funny) by Anonymous Coward on Monday June 22 2015, @01:11PM
Most guys couldn't get past the "walking abreast" part.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @01:17PM
Abreast doesn't mean "in a group", it means "Side-by-side". Imagine school girls walking in a big group, in lines of 3 wide. Common language in the UK, presumably not in the US?
(Score: 0) by Anonymous Coward on Monday June 22 2015, @01:37PM
I got it. But I am also letting my inner 13 year old out today :)
(Score: 2) by hemocyanin on Monday June 22 2015, @01:57PM
Totally common word in the US. The incorrect definition in TFA was totally unnecessary.
(Score: 4, Insightful) by VLM on Monday June 22 2015, @02:15PM
Its a trick question.
posed an innocent-looking puzzle
Yeah whatever. They're using words like:
young ladies
and
abreast
to distract us. Just rephrase the question to something like scheduling first person shooter videogame multi player maps such that each 3 map set doesn't have repeats... then you'll get a much less distracted answer.
(Score: 2) by Freeman on Tuesday June 23 2015, @07:29PM
If someone had made a computer game out of it, it could have been solved 20 years ago.
Joshua 1:9 "Be strong and of a good courage; be not afraid, neither be thou dismayed: for the Lord thy God is with thee"
(Score: 2) by wonkey_monkey on Monday June 22 2015, @03:12PM
It's a verbatim quote of the original puzzle, with the clarification to explain what the creator actually meant.
systemd is Roko's Basilisk
(Score: 0) by Anonymous Coward on Monday June 22 2015, @02:29PM
It is not common in the US to say 'abreast'. You are correct that 'abreast' means 'side-by-side' but in the context of the puzzle, it is correct to paraphrase 'in groups of three'.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @02:45PM
> It is not common in the US to say 'abreast'.
I guess it all depends on what circles you move in.
Your not common is my unremarkable.
(Score: 0) by Anonymous Coward on Tuesday June 23 2015, @08:39AM
Sorry, I was expelled from the Pedantry Squad at Mensa.
Now I get to talk with my neighbors: 15% teenage mothers, 46% former teenage mothers, 9% teenage fathers, 30% ex-convicts.
(Score: 4, Funny) by Anonymous Coward on Monday June 22 2015, @01:36PM
There are fifteen schoolgirls and seven rape-demons. Each demon has three tentacles...
(Score: 3, Funny) by Anonymous Coward on Monday June 22 2015, @02:12PM
Actually since each schoolgirl has 3 rapable orifices you'd need demons with 9 tentacles each
(Score: 2) by VLM on Monday June 22 2015, @02:19PM
I like that comment because it works just as well in this story as in the "1,000 Pepper Robots Sell Out in a Minute on Launch Day" story. Could probably tie it into the old story "US Says Woman will Appear on New $10 Note". Good Job AC.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @08:24PM
> 3
You're just not using your imagination.
(Score: 3, Funny) by The Archon V2.0 on Monday June 22 2015, @02:08PM
> 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.
Pah! I am surrounded by idiots! I got to day FIVE before painting myself in a corner I couldn't possibly get out of.
(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.
(Score: 0) by Anonymous Coward on Monday June 22 2015, @03:44PM
The summary should summarize the content. This "summary" is an extended advertisement for the article.
(Score: 2) by janrinok on Monday June 22 2015, @06:08PM
Advertisement? What is being sold? You mean, it draws the readers attention to an interesting article, just like every other story on this site does. You don't have to read them if you don't want to, but I found it interesting and enlightening. If maths is not your bag, pick another story. I don't understand the detail of string theory, or nuclear physics, or many other topics - but it doesn't mean I can't enjoy reading about them and learning a bit more each time I do.
[nostyle RIP 06 May 2025]
(Score: 3, Informative) by maxwell demon on Monday June 22 2015, @06:46PM
Not every advertisement is for a commercial offering.
It is written in a way that you get the relevant information only by reading the article. It doesn't summarize the article.
With a good summary, you'd only need to read that in case you are interested in the details. The summary as is gives lot of details, but not the most important information.
The following quote from the summary is a dead giveaway that it does not summarize:
A summary would have told why he was wrong. This is an advertisement right out of the textbook. "If you want to know why he was wrong, read the article."
The Tao of math: The numbers you can count are not the real numbers.
(Score: 3, Insightful) by janrinok on Monday June 22 2015, @07:21PM
OK, I can see the point that you are making.
However, to me as the submitter, I was more interested in solving the initial problem and learning a bit more about combinatorial maths. Explaining in simple terms what follows in the second half of the article would have resulted in a summary of almost the same size as the original.
I'm not going to re-edit it now (and as the original submitter that would be bending our rules a little bit), so please just ignore the last line of the 'summary'.
[nostyle RIP 06 May 2025]
(Score: 0) by Anonymous Coward on Monday June 22 2015, @10:21PM
> The summary should summarize the content. This "summary" is an extended advertisement for the article.
If you had ever submitted a story you would know it is not a summary, it is a scoop.
(Score: 3, Funny) by wonkey_monkey on Monday June 22 2015, @04:48PM
Pull out a pencil and paper, and you’ll quickly find that the problem is harder than it looks
That depends where you'd pushed 'em into.
systemd is Roko's Basilisk
(Score: 0) by Anonymous Coward on Monday June 22 2015, @07:16PM
Have they tried chalk and a chalkboard? Or better yet writing some computer code? Are there any examples of the latter available?
(Score: 2) by darkfeline on Monday June 22 2015, @11:36PM
It shouldn't be too difficult to prove that this problem is either NP-hard or not, right? Once you know that, it gives you a reference point as to how hard the problem is.
Join the SDF Public Access UNIX System today!
(Score: 0) by Anonymous Coward on Tuesday June 23 2015, @07:40AM
Indeed, using boolean logic, you can prove that without even knowing what "NP hard" means or what the problem is:
Law of the excluded middle: P or not P
Law of contradiction: not (P and not P)
Therefore: (P or not P) and not (P and not P)
Or in short: Either P or not P.
Set "P" = "this problem is NP hard"
Thus we get: This problem is either NP hard or not. q.e.d.
SCNR :-)
(Score: 1) by hopp on Tuesday June 23 2015, @05:32AM
Pigeonhole principle...