Thread: Pattern

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.

Originally Posted by mathsmad

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.

I'm kind of ignorant with formal proofs and the relevant language. Therefore, I'm arbitrarily going to call any selection of 13 numbers from the above set where none of the selections have a difference of four with any other selection a "Lamp Set". (Yes, I just glanced around for a random word to use.)

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.

Originally Posted by mathsmad

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.

We can subtract 100 from each integer and thus assume that the 14 integers are chosen from the set {0,1,2,...,23,24}. Call the set of 14 integers S. Then S is the union of four sets:






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.

that was my next guess...

Thanks for the help