Show that if 14 distinct integers are chosen from the sequence 100,101,102,103,...,123,124, there must be two of them whose difference is four.

Printable View

- May 14th 2005, 03:41 PMmathsmadPattern
Show that if 14 distinct integers are chosen from the sequence 100,101,102,103,...,123,124, there must be two of them whose difference is four.

- May 27th 2005, 05:19 AMwilInelegant demonstrationQuote:

Originally Posted by**mathsmad**

Start by grouping the numbers in sets of 4:

100,101,102,103

104,105,106,107

108,109,110,111

112,113,114,115

116,117,118,119

120,121,122,123

124

A simple starting selection process is to select all numbers in the odd rows. This gives us a Lamp Set. Let's look at the pattern of our selections (1 means selected, 0 means not):

1111

0000

1111

0000

1111

0000

1

In a Lamp Set, we must not select two numbers vertically adjacent to each other. To modify the selections while maintaining a Lamp Set, we can flip all the selections in any of columns 2, 3 and 4:

Columns 2 and 4 flipped:

1010

0101

1010

0101

1010

0101

1

Columns 2, 3 and 4 flipped:

1000

0111

1000

0111

1000

0111

1

Column one can't be flipped, because that would only leave us 12 numbers selected:

0000

1111

0000

1111

0000

1111

0

All possible Lamp Sets can be produced by choosing to flip or not three times. Therefore, there are only 2^3 = 8 possible Lamp Sets.

Now, there are no Lamp Sets where a 14th selection can be made without it being vertically adjacent to one of the Lamp Set selections, and thus having a difference of four with that selection. Since a 14-member selection set with no two selections having a difference of four can be found, 14 selections made from the source set must always include at least two selections with a difference of 4.

I'm not really used to proofs yet, so while there's probably a more elegant way to show this, the above is sufficient. - May 27th 2005, 06:44 AMhpeQuote:

Originally Posted by**mathsmad**

That is, S0 is the subset of integers in S that are divisible by 4, S1 is the subset that has a remainder equal to 1 when divided by 4, and so on. The union of these sets is S, and any two of these sets have an empty intersection.

Suppose now that the assertion is false. Then no two integers in S and no two elements of S0, S1, S2, S3 have a difference of 4. Thus S0 can have at most 4 elements (since otherwise there would be two numbers in S0 with a difference of 4), and S1, S2, S3 can each have at most 3 elements, for the same reason. Put together,

can have no more than 4+3+3+3 elements, contradicting the assumption that S has 14 elements. - May 28th 2005, 01:15 AMwilyeah!
that was my next guess... :)

- May 28th 2005, 02:05 PMmathsmadThanks for the help
Thanks for the help