If a set N
9 = {1, 2, 3, 4, 5, 6, 7, 8, 9} of 9 numbers is split into two subsets, then at least one of them contains three terms in arithmetic progression.
The statement is not true for a set N
8 of 8 integers.
Seems obvious?
Prove it.
Below are the only six divisions of integers 1 - 8 into two subsets, neither of which contains an arithmetic progression (produced by the program at bottom):
1256 3478
1368 2457
1458 2367
2367 1458
2457 1368
3478 1256
Actually that was only three distinct divisions, but in any case, we can add a 9 to the first in each instance (which is the second in a different line) to produce arithmetic progressions as follows:
1256 3478 12569 contains 159
1368 2457 13689 contains 369
1458 2367 14589 contains 159
2367 1458 23679 contains 369
2457 1368 24579 contains 579
3478 1256 34789 contains 789
The sets for 8 that already have arithmetic progressions will still do so by ignoring the 9 and can indeed have more such progressions also.
DefDbl A-Z
Dim crlf$, set1(9), set2(9), s1sz, s2sz
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For d1 = 0 To 1
If d1 Then
s2sz = s2sz + 1
set2(s2sz) = 1
Else
s1sz = s1sz + 1
set1(s1sz) = 1
End If
For d2 = 0 To 1
If d2 Then
s2sz = s2sz + 1
set2(s2sz) = 2
Else
s1sz = s1sz + 1
set1(s1sz) = 2
End If
For d3 = 0 To 1
If d3 Then
s2sz = s2sz + 1
set2(s2sz) = 3
Else
s1sz = s1sz + 1
set1(s1sz) = 3
End If
For d4 = 0 To 1
If d4 Then
s2sz = s2sz + 1
set2(s2sz) = 4
Else
s1sz = s1sz + 1
set1(s1sz) = 4
End If
For d5 = 0 To 1
If d5 Then
s2sz = s2sz + 1
set2(s2sz) = 5
Else
s1sz = s1sz + 1
set1(s1sz) = 5
End If
For d6 = 0 To 1
If d6 Then
s2sz = s2sz + 1
set2(s2sz) = 6
Else
s1sz = s1sz + 1
set1(s1sz) = 6
End If
For d7 = 0 To 1
If d7 Then
s2sz = s2sz + 1
set2(s2sz) = 7
Else
s1sz = s1sz + 1
set1(s1sz) = 7
End If
For d8 = 0 To 1
If d8 Then
s2sz = s2sz + 1
set2(s2sz) = 8
Else
s1sz = s1sz + 1
set1(s1sz) = 8
End If
If found(1) = 0 And found(2) = 0 Then
For i = 1 To s1sz
Text1.Text = Text1.Text & set1(i)
Next
Text1.Text = Text1.Text & " "
For i = 1 To s2sz
Text1.Text = Text1.Text & set2(i)
Next
Text1.Text = Text1.Text & crlf
End If
DoEvents
If d8 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d8
If d7 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d7
If d6 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d6
If d5 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d5
If d4 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d4
If d3 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d3
If d2 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d2
If d1 Then
set2(s2sz) = 0
s2sz = s2sz - 1
Else
set1(s1sz) = 0
s1sz = s1sz - 1
End If
Next d1
Text1.Text = Text1.Text & crlf & " done"
End Sub
Function found(x)
If x = 1 Then
If s1sz < 3 Then found = 0: Exit Function
For i = 1 To s1sz - 2
For j = i + 1 To s1sz - 1
For k = j + 1 To s1sz
If set1(k) - set1(j) = set1(j) - set1(i) Then
found = 1: Exit Function
End If
Next
Next
Next
Else
If s2sz < 3 Then found = 0: Exit Function
For i = 1 To s2sz - 2
For j = i + 1 To s2sz - 1
For k = j + 1 To s2sz
If set2(k) - set2(j) = set2(j) - set2(i) Then
found = 1: Exit Function
End If
Next
Next
Next
End If
End Function
|
|
Posted by Charlie
on 2017-03-24 11:00:45 |
With some computer aid
