Consider Groups I and II consisting of positive integers from 1 to 7, where:

Group I = {1,2,4,7} and, Group II = {3,5,6}

It is observed that the sum of any two numbers of either group is either greater than the largest number or is in the other group.

For example, 1 and 2 belong to the first group whose sum (3) belongs to the second group. Also, 3 and 5 belong to the second group, whose sum (8) is greater than the largest number (6) in the second group.

Can you come up with arrangement of the first eight positive integers, that is from 1 to 8 inclusively, that satisfies the same two properties?

Start by wondering where 1 and 2 go.
Suppose they are in different groups.  We then have to decide where 3 goes.  Putting 3 with 1 forces 4 and 6: {1,3,6} and {2,4,5} and then the 7 cannot be placed.  Putting 3 with 2 forces 5 and 6: {1,5} and {2,3,6} and then the 4 cannot be placed.  So 1 and 2 are in the same group.

Putting 1 and 2 in the same group forces 3 but not 4.
If 4 goes with 1 and 2 it forces 5 and 6:
{1,2,4} and {3,5,6} which forces 8 which forces 7:
{1,2,4,8} and {3,5,6,7} <---- Solution
If 4 goes with 3 it forces 7 which forces 5 and 6
{1,2,7} and {3,4,5,6} but now 8 cannot be placed.

Incidentally it appears eight is the largest this problem can go since 9 cannot be placed.

This solution works as long as the word 'or' is inclusive since the sum of 3 and 5 is 8 with is greater than the largest member of the group and also a member of the other group.

Posted by Jer on 2013-01-29 15:12:40