All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Must differ by 3 (Posted on 2015-10-23) Difficulty: 2 of 5
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.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer proof | Comment 1 of 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 A-Z
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 2015-10-23 13:03:39
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information