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:
DefDbl AZ
Dim crlf$, used(106), howMany, h(16)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
addOn
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub addOn()
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
Next
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))
Next
Text1.Text = Text1.Text & crlf
Else
addOn
End If
used(newOne) = 0
howMany = howMany  1
End If
Next
End Sub

Posted by Charlie
on 20151023 13:03:39 