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.)Originally Posted bymathsmad

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.