Mathematical/logical problems

Factual Questions
1

Take the first five letters in the alphabet. Then create every possible two-letter combination (order disregarded; AB is the same as BA for the purpose of this problem) using only those letters. This creates ten pairs:

AB AC AD AE BC BD BE CD CE DE

Then divide them into three groups, so that Group 1 has four pairs in it, while Group 2 and 3 have three pairs each. Example:

Group 1: AB AC AD AE
Group 2: BC BD BE
Group 3: CD CE DE

First problem: Is it possible to divide them into groups so that all possible three-letter combinations can be created by picking one pair from group 1, one pair from group 2 and one pair from group 3? For example, if AB is in group 1, BC is in group 2 and AC is in group 3, the three-letter combination ABC can be created in this way.

Second problem: Is it possible to divide them into groups so that, no matter which pair you pick from group 1, you can still create a three-letter combination by picking the right pairs from group 2 and 3?

Third problem: Is it possible to divide them into groups so that both of the above are true?

I suspect the answer to all three is “no”. If so, can this be proved without actually trying all possible combinations?

2

[QUOTE=Priceguy]
Second problem: Is it possible to divide them into groups so that, no matter which pair you pick from group 1, you can still create a three-letter combination by picking the right pairs from group 2 and 3?
[/QUOTE]

You can always make a three letter combination by picking from groups 2 and 3. Do you mean “create any three-letter combination”?

Even if it’s any three letter combination, you could still achieve it by:

Group 1: AB
Group 2: AC AD AE BC BD BE
Group 3: CD CE DE

You pick any pair from group 1 (but it has to be AB), then choose BD and CE (for instance), and you can make any three-letter combination.

Perhaps you mean: Is it possible to divide them into groups so that, no matter which pair you pick from any one of the groups, you can still create any three-letter combination by picking the right pairs from the other two groups?

Also, by “create any three-letter combination”, I’m assuming the three letters just need to be contained in the six you chose. Or do you mean they must be the only letters in the six you chose (like your example of AB, BC, AC giving you ABC)?

3

[QUOTE=tim314]
Group 1: AB
Group 2: AC AD AE BC BD BE
Group 3: CD CE DE
[/quote]
There must be four pairs in group 1, three in group 2 and three in group 3.

No. I mean “Is it possible to divide them into groups so that, no matter which pair you pick from the first group, you can still create a three-letter combination by picking the right pairs from the other two groups?”.

The latter; they must contain those three letters and only those three letters.

4

[QUOTE=Priceguy]
There must be four pairs in group 1, three in group 2 and three in group 3.
[/quote]
Missed that – sorry.

The question makes more sense now that I understand they can’t include additional letters also.

5

In answer to question 1:

To be able to get any three letter combination from the groups, each group must have a pair contained in each of the 10 triples: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE

Each triple only contains three pairs.

Thus, the three pairs within a given triple must be distributed between the three groups. In other words, each group can only contain one pair from each triple.

If a group contains a given pair (say AB), then it can’t contain any pair that overlaps with that pair (e.g., AC, AD, AE, BC, BD, BE). That’s because each of those pairs shares a triple with the original pair. (And as noted, the group can only contain one pair from each triple).

Thus, a group can only contain disjoint pairs (i.e., ones that share no letters).

There aren’t three disjoint pairs in {A,B,C,D,E}. So it’s impossible to make any groups of three that satisfy the first problem.

Thus, the answer to the first and third problems is no.

6

The answer to the second problem is yes.

For instance, you can assign the groups as follows:

Group 1: AB AD BD CE
Group 2: BC CD DE
Group 3: AC AE BE

Here’s how you make a triple for each choice of pair from Group 1:

Pick AB: Make AB-BC-AC
Pick AD: Make AD-CD-AC
Pick BD: Make BD-DE-BE
Pick CE: Make CE-BC-BE

7

Thanks a lot; this was exactly the sort of thing I was looking for.

Next question: Is it possible to solve the second problem so that each letter is represented at least once in each group (in your example A isn’t represented in group 2)?

8

Is it just me, or would this be a lot easier to express as a graph problem, rather than as a combinatorics problem? In this case, you start with the complete graph on five vertices, the pairs are the edges, and the triplets are triangles.

9

[QUOTE=Chronos]
Is it just me, or would this be a lot easier to express as a graph problem, rather than as a combinatorics problem? In this case, you start with the complete graph on five vertices, the pairs are the edges, and the triplets are triangles.
[/QUOTE]
I have no clue what you just said.

10

OK, a graph is just a bunch of dots with lines between them. The dots are called vertices, and the lines are called edges. A complete graph on n vertices just means that you take that many dots, and draw lines between all of them, so a complete graph on five vertices might, for instance, look like a pentacle (or it might not; graph theory doesn’t care how the dots are arranged, just which ones are connected to each other). If we call the vertices in this case A, B, C, D, and E, then we can call the edges AB, AC, AD, etc., and your questions turn into questions about lines on a graph, rather than questions about pairs of letters.

11

[QUOTE=Priceguy]
Next question: Is it possible to solve the second problem so that each letter is represented at least once in each group (in your example A isn’t represented in group 2)?
[/QUOTE]

The answer is No.

Each letter occurs 4 total times. (E.g., A occurs in AB, AC, AD, and AE.) With three groups, this means that each group will have at least one letter that it contains twice.

Groups two and three only have 6 total letters, so if they need to contain all five possible letters they can have at most one letter that they contain twice.

In other words, groups 2 and 3 each contain one letter twice, and all the other letters once. (It can’t be the same letter contained twice in both groups, or all four instances of that letter would be used, with none left over for group one.)

So group 2 must look like:
Group 2: LM LN OP
for some assignment of A,B,C,D, and E to the variables L, M, N, O, and P.

There are two cases we need to consider:

CASE 1: MN is contained in group 1.

This won’t work, because if we choose MN from group 1, we can either choose LM from group 2 and need LN in group 3, or we can choose LN from group two and need LM in group 3. But both LM and LN are in group 2, and thus neither can be in group 3.

CASE 2: MN is contained in group 3.

We know we need an L in group 3, and it can’t pair with M or N (since it paired with them in group 2), so we’re left with either LO or LP. It doesn’t matter which we choose, since so far we only used O and P in OP, which is unchanged if we swap O and P. So we can arbitrarily choose O to be the one that pairs with L in group 3.

So group 3 contains: MN and LO. It can’t contain a second L (since two L’s were used in group 2), and it must contain a P, so it must contain either MP or NP. Again, we can choose either one arbitrarily, since so far we used MN in group three (which is symmetric under exchange of M and N), and we used LM and LN in group 2 (which together are symmetric under exchange of M and N). We’ll choose MP. So, we have:
Group 3: LO, MN, MP

Since we already specified group 2 above, and we just specified group 3, we know that all the remaining pairs are in group 1. So we have:

Group 1: LP MO NO NP
Group 2: LM LN OP
Group 3: LO MN MP

This won’t work, because if we choose NP from group 1, we can pick either LN or OP from group 2. This then requires LP or NO to be in group 3, respectively, but they’re both in group 1 instead.

So both cases fail.

12

Thanks a lot, tim. No more moving goalposts!