Let S consist of 16 elements of the set (1,2,3, ... , 106) so
that no two elements of S differ by 6; 9; 12; 15; 18; or 21.
Prove that at least two of
the elements of S must differ by 3.
The puzzle in fact asks us to prove that no such set of 16 elements can exist in which no two elements differ by 3, 6, 9, 12, 15, 18 or 21. The difference of 3 was separated out as special, but in fact is just one of this list.
The following program attempts to find a set of 16 such elements to contradict the assertion. It is programmed to start with the first element to be any starting point and successive elements strictly increasing. It was taking a long time to run, when I realized that once it tried and failed to find a matching set starting with the integer 1, that it was not necessary to let it try larger starting (smallest) elements, as, if such a set existed between n and 106 with n higher than 1, it could be found in the larger set from 1 to 106.
The following program did not find any with a lowest element of 1, and therefore no such set exists:
Dim crlf$, used(106), howMany, h(16)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
Text1.Text = Text1.Text & crlf & " done"
st = h(howMany) + 1
For newOne = st To 106 - (15 - howMany)
good = 1
For prv = newOne - 3 To newOne - 21 Step -3
If prv < 1 Then Exit For
If used(prv) Then good = 0: Exit For
If good Then
howMany = howMany + 1
h(howMany) = newOne
used(newOne) = 1
If howMany = 16 Then
For i = 1 To 16
Text1.Text = Text1.Text & Str(h(i))
Text1.Text = Text1.Text & crlf
used(newOne) = 0
howMany = howMany - 1
Posted by Charlie
on 2015-10-23 13:03:39