You're reading: Posts Tagged: combinatorics

CLP reads “Non-sexist solution to the ménage problem”

I rediscovered this nice paper by Kenneth P. Bogart in my Interesting Esoterica collection, and decided to read through it. It turned out that, while the solution presented is very neat, there’s quite a bit of hard work to do to along the way. I’m not particularly experienced with combinatorics, so the little facts that the paper skips over took me quite a while to verify.

Once I was happy with the proof, I decided to record a video explaining how it works. Here it is:

I probably made mistakes. If you spot one, please write a polite correction in the comments.

From the Mailbag: Golfing Combinatorics

Sam’s dad is in a mathematical conundrum – so she’s asked Katie, one of our editors, if maths can save the day.

From the Sartorial Arts Journal, New York, 1901Dear The Aperiodical,

My dad is going away on a golfing holiday with seven of his friends and, since I know a little bit about mathematics, he’s asked me to help him work out the best way to arrange the teams for the week. I’ve tried to work out a solution, but can’t seem to find one that fits.

They’ll be playing 5 games during the week, on 5 different days, and they’d like to split the group of 8 people into two teams of four each day. The problem is, they’d each like to play with each of their friends roughly the same amount – so each golfer should be on the same team as each other golfer at least twice, but no more than three times.

Can you help me figure it out?

Sam Coates, Manchester

Information and Inference: new journal with free content for two years

The Institute of Mathematics and its Applications has launched a new journal, Information and Inference: a Journal of the IMA. This aims to

publish high quality mathematically-oriented articles, furthering the understanding of the theory, methods of analysis, and algorithms for information and data.
Articles should be written in a way accessible to researchers in the associated topics in pure and applied mathematics, statistics, computer sciences, and electrical engineering. Articles are published in, but not limited to: information theory, statistical inference, network analysis, numerical analysis, learning theory, applied and computational harmonic analysis, probability, combinatorics, signal processing, and high-dimensional geometry.

According to the website, “all content will be free to access for the first two years of publication of the journal”. You can sign up for free email table of contents alerts.

The first paper, ‘The masked sample covariance estimator: an analysis using matrix concentration inequalities‘, has been made available for advanced online access.

More information: Oxford Journals: Information and Inference: a Journal of the IMA.

Like everybody else, you too can be unique. Just keep shuffling

The first take-home lesson of this note is that you too can be unique. You’ll have to keep shuffling to get there, but it is an attainable goal.

Several years ago it dawned on me that the number of possible ways to order or permute the cards in a standard deck of size $52$ was inconceivably large. Of course it was — and still is — $52!$. That’s easy enough to scribble down (or even surpass spectacularly) without understanding just how far we are from familiar territory.

A 17×17 4-colouring with no monochromatic rectangles

Described on The Math Less Traveled

Why I like some bad maths stories

My two most recent posts here have been about a story reporting a coincidence as more exceptional that it is and ‘bad maths’ reported in the media. Both are examples of mathematical stories being reported in a way that is not desirable. Somehow, though, I like the whist story and dislike the PR equations. I have been thinking about why this might be the case.

The PR-driven, media-friendly but meaningless equations from the first article are annoying because they present an incorrect view of mathematics and how mathematics can be applied to the real world. Applications of mathematics are everywhere and compelling, yet the equations in these sorts of equations seem to present little more than vague algebra. The commissioned research with seemingly trivial aims I find more difficult because, as commenters on that article pointed out, it is really difficult to decide what is trivial. Still, reporting that a biscuit company has commissioned research into biscuit dunking is either meaningless PR or else a matter of internal interest, and certainly nothing like what I expect mathematicians do for a living.

Coming back to our Warwickshire whist drive: what do I like about this story? It too presents incorrect information about mathematics and the real world, claiming that the event, four perfect hands of cards dealt, is so unlikely that it is only likely to happen once in human history (and it happened in this village hall!).

I think the difference is that the mathematics used, combinatorics and probability, appear to be correctly applied. The odds quoted, 2,235,197,406,895,366,368,301,559,999 to 1, are widely reported and I see no reason to doubt them.

The problem, then, is one of modelling assumptions. Applying a piece of mathematics to the real world involves describing the scenario, or a simplified version of it, in mathematics, solving that mathematical model and translating the solution back to the real world scenario. In this case, the description of the scenario in mathematics assumes that the cards are randomly distributed in the pack. This modelling assumption, rather than the mathematics, is where the error lies.

The result is still a bad maths news story, presenting a mathematical story as something other than what it is, but while the PR formulae are of little consequence, this incorrect application of a correct combinatorial analysis is something we can learn from.

Google+