## Cute Math Problem

This came up in a Math Ed discussion at LinkedIn.

Here A, B, and C are three finite sets.

If half of the As are Bs and half of the Bs are Cs and half of the Cs are As, then what are the maximum and minimum possible ratios of the size of A to the size of C?

I will think of the three sets as properties or types and label each element by the names of its properties, so for example AB denotes an element that is in both setA and setB

As one example, with just three elements overall, if they are of form AB AC BC, then we have two with each property, so clearly the three sets can be equal. But they don't have to be, and the question is to see how far from equality we can go.

If half of the Cs are As, then the number of As (let's call it a) is at least half as big as the number c of Cs.

ie a/c≥1/2 (or equivalently c/a≤2)

For an example of attaining the upper bound of 2 on c/a we can use the following picture with just 5 elements:

Each column in the table lists properties of one element

(and the O's are just fillers to try and make the columns line up)

four C's:...........CCCCO (and half of the C's are A's)

two A's............OOAAO (there could also be nonC A's but there don't have to be)

two B's............OOOBB (one is also an A and a C and the other is neither)

On the other hand, since half of the As are Bs we must have b≥a/2, and since half of the Bs are Cs we must have c≥b/2≥a/4

So a/c≤4 (i.e. there can't be more than four times as many As as there are Cs).

Of course, just because a/c can't be bigger than 4 doesn't mean that it can actually get that big. But it is not hard to find an example where a/c=3. eg, Using the same notation as in the previous example, consider:

CCOOOOO

OAAAAAA

BBBBOOO

So the hard part of the problem is to see if we can get the ratio a/c to be any bigger than 3 (eg 14 As and 4 Cs would give a ratio of 3.5) - and in particular can we find examples where it gets close to or even reaches the value of 4?

I believe that in fact the maximum possible value is three and I have posted a proof of that here.

October 5th, 2010 at 1:23 pm

[...] Alan Cooper has actually proved that a/c may never exceed 3 and gave an example where this bound has been achieved. The important point here is that there are 4 not 3 parameters. [...]