Stories
Slash Boxes
Comments

SoylentNews is people

posted by cmn32480 on Monday June 22 2015, @12:21PM   Printer-friendly
from the i-failed-calculus-twice dept.

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

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 0) by Anonymous Coward on Monday June 22 2015, @03:44PM

    by Anonymous Coward on Monday June 22 2015, @03:44PM (#199452)

    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

    by janrinok (52) Subscriber Badge on Monday June 22 2015, @06:08PM (#199529) Journal

    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.

    • (Score: 3, Informative) by maxwell demon on Monday June 22 2015, @06:46PM

      by maxwell demon (1608) on Monday June 22 2015, @06:46PM (#199542) Journal

      Advertisement? What is being sold?

      Not every advertisement is for a commercial offering.

      You mean, it draws the readers attention to an interesting article, just like every other story on this site does.

      It is written in a way that you get the relevant information only by reading the article. It doesn't summarize the article.

      You don't have to read them if you don't want to, but I found it interesting and enlightening.

      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:

      But he was wrong .... Read the full linked article for more.

      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

        by janrinok (52) Subscriber Badge on Monday June 22 2015, @07:21PM (#199550) Journal

        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'.

  • (Score: 0) by Anonymous Coward on Monday June 22 2015, @10:21PM

    by Anonymous Coward on Monday June 22 2015, @10:21PM (#199620)

    > 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.