Maths prize for 13 October 2015: a Ramsey puzzle

childrens_parties_banner

If you have a group of four people, it’s possible to have no subgroup of three all of whom know each other, and simultaneously no subgroup of three none of whom know each other. If there are five people at a party, is it possible that the party includes no subgroup of three who all already know each other, and no subgroup of three all of whom didn’t know each other before the party? If there are six, is that possible?

The prize was won by Joan Onokhua, who produced the best partial solution.


Solution: Suppose a blue line connecting two people shows they already know each other, and a red line that they don’t.

This diagram (or the same diagram with blue and red swapped) shows you can have a party of five without any subgroup of three who all know each other, or all don’t known each other (i.e. without an all-blue or an all-red triangle). A similar but simpler diagram shows you can have a party of four like that.

Dinner5

If you have six people, however, then there must be an all-blue or an all-red triangle.

Proof: Each person has five connections (blue or red) to the other people. So each must have at least three connections of the same colour, say red. For example, here A has three red connections to B, C, and D.

Untitled

If the BC, BD, and CD connections are all blue, then BCD form an all-blue triangle. If one of those three connections is red, then the two red-connected people plus A form an all-red triangle. One way or another, you must get an all-same-colour triangle.  ▇

For more, click here.

Another proof of the same sort shows that there must be at least four numbers in order (increasing or decreasing) in a list of ten, however jumbled-up?

Go through the list from the left. Take the first number. Cross it out in colour 1. Go along the list crossing numbers out in red (colour 1) if they’re smaller than the last crossed-out number.

When finished, take the first not-crossed-out number, cross it out in magenta (colour 2), and do a similar process to make a decreasing sequence of numbers crossed out in colour 2.

Repeat with blue (colour 3) and green (colour 4), etc., until all numbers are crossed out. Either one of those coloured decreasing sequences is at least four numbers long, and we’re done; or there must be at least four of them.

If there are at least four, then take the biggest green number. There must be some blue number less than it to its left, or it would have been crossed out with blue.

That blue number must have a magenta number less than it to its left, or it would have been crossed out with magenta.

And that magenta number must have a red number less than it to its left.

We’ve made an increasing (as you read to the right, or decreasing as you read to the left) sequence of four.  ▇

Example:

9247630815

Can you generalise? How many numbers must be in order within a list of n2+1 numbers, however jumbled up? How many in a list of 101 numbers?

The party problem does not generalise so easily. You have to have 18 at the party to ensure that there is either a group of four who all know each other, or a group of four who were all previously strangers; but so far, no-one knows how big the party must be to ensure that there is either a group of five who all know each other, or a group of five who were all previously strangers to each other.

The number is not smaller than 43, and not bigger than 49, but so far we don’t know beyond that.

Click here for more, including a proof of another simple result in the same area: if you have five points in a plane, and no three are in the same straight line with each other, then there must be four among them which form a convex quadrilateral. (This result is called the Happy Ending Theorem, because the mathematicians Esther Klein, who posed the problem, and George Szekeres, who solved it, got married to each other soon after).

That simple problem, too, has an unsolved generalisation. The guess is that if you have 1+2k−2 points in a plane, and no three are in the same straight line with each other, then there must be k among them which form a convex k-agon. No-one has yet managed to prove it, as Ron Graham explains in this video:

Frank_final_500

All these are problems of “Ramsey theory”, part of a larger field called combinatorics. Ramsey theory shows that in any large enough structure there has to be a minimum of order. We see patterns among the stars in the sky because however jumbled up they were, there would still be some patterns. Another simple Ramsey-theory result is that if you list ten different numbers, however much you jumble them up, either at least four will be in increasing order or at least four will be in decreasing order.

Frank Ramsey died (from liver problems) at the age of 26; but had already done enough to have a whole branch of maths named after him, as well as making big contributions in probability theory, economics, and philosophy, and translating an important and difficult philosophy book from German into English.

Frank Ramsey was a militant atheist, but his brother Michael Ramsey became Archbishop of Canterbury. Michael wrote of Frank: “He was interested in almost everything. He was immensely widely read in English literature; he was enjoying classics… he was very interested in politics, and well-informed; he had got a political concern and a sort of left-wing caring-for-the-underdog kind of outlook about politics”.

Frank Ramsey was also, by all accounts, a cheerful and sociable type. He married and had two children.