While reviewing a
lesson on union and intersection, Mrs. Putnam again asked for three students to each write down a set of numbers from {1,2,3,4,5,6,7,8,9,10}. After they had done so, she looked at their sets and told the class, "Like last time, the union of these three sets is all ten numbers, but their intersection is empty."
One student interjected to say that he saw that two of the sets have a union that was all ten numbers.
Another student noted that there were two sets whose intersection was empty.
How many triplets of sets A, B, C satisfy all the above criteria?
I shall assume that each situation reported by a student was a unique situation: that only one pair of sets had an empty intersection and that only one pair of sets had a union that consisted of all ten numbers.
The program finds the instances assuming that sets called B and C are the ones that are disjoint, having an empty intersection. The pair having the universal (1 - 10) union could be A and B, A and C or B and C.
DefDbl A-Z
Dim crlf$, groupa$, groupb$, groupc$, foundct
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For a = 1 To 5
assign "a", a
For b = 1 To 5
assign "b", b
' Text1.Text = Text1.Text & a & Str(b) & crlf
For c = 1 To 5
assign "c", c
For d = 1 To 5
assign "d", d
For e = 1 To 5
assign "e", e
For f = 1 To 5
assign "f", f
For g = 1 To 5
assign "g", g
For h = 1 To 5
assign "h", h
For i = 1 To 5
assign "i", i
For j = 1 To 5
assign "j", j
DoEvents
If isAll10(groupa$ + groupb$) Then unionct = 1: uab = 1 Else unionct = 0: uab = 0
If isAll10(groupc$ + groupb$) Then unionct = unionct + 1: ucb = 1 Else ucb = 0
If isAll10(groupa$ + groupc$) Then unionct = unionct + 1: uac = 1 Else uac = 0
good = 1
If isMutExcl(groupa$, groupb$) Then good = 0
If isMutExcl(groupa$, groupc$) Then good = 0
If unionct = 1 And good = 1 Then
'If uac = 0 Then
foundct = foundct + 1
If Rnd(1) * 50000 < 1 Then Text1.Text = Text1.Text & groupa$ & " " & groupb$ & " " & groupc$ & crlf
'End If
End If
unassign "j", j
Next
unassign "i", i
Next
unassign "h", h
Next
unassign "g", g
Next
unassign "f", f
Next
unassign "e", e
Next
unassign "d", d
Next
unassign "c", c
Next
unassign "b", b
Next
unassign "a", a
Next
Text1.Text = Text1.Text & crlf & foundct & " done"
End Sub
Sub assign(ltr$, sets)
Select Case sets
Case 1: groupa$ = groupa$ + ltr$
Case 2: groupb$ = groupb$ + ltr$
Case 3: groupc$ = groupc$ + ltr$
Case 4: groupb$ = groupb$ + ltr$
groupa$ = groupa$ + ltr$
Case 5: groupc$ = groupc$ + ltr$
groupa$ = groupa$ + ltr$
End Select
End Sub
Sub unassign(ltr$, sets)
Select Case sets
Case 1: ix = InStr(groupa$, ltr$)
groupa = Left(groupa, ix - 1) + Mid(groupa, ix + 1)
Case 2: ix = InStr(groupb$, ltr$)
groupb = Left(groupb, ix - 1) + Mid(groupb, ix + 1)
Case 3: ix = InStr(groupc$, ltr$)
groupc = Left(groupc, ix - 1) + Mid(groupc, ix + 1)
Case 4: ix = InStr(groupa$, ltr$)
groupa = Left(groupa, ix - 1) + Mid(groupa, ix + 1)
ix = InStr(groupb$, ltr$)
groupb = Left(groupb, ix - 1) + Mid(groupb, ix + 1)
Case 5: ix = InStr(groupa$, ltr$)
groupa = Left(groupa, ix - 1) + Mid(groupa, ix + 1)
ix = InStr(groupc$, ltr$)
groupc = Left(groupc, ix - 1) + Mid(groupc, ix + 1)
End Select
End Sub
Function isAll10(s$)
If InStr(s, "a") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "b") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "c") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "d") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "e") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "f") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "g") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "h") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "i") = 0 Then isAll10 = 0: Exit Function
If InStr(s, "j") = 0 Then isAll10 = 0: Exit Function
isAll10 = 1
End Function
Function isMutExcl(a$, b$)
For i = 1 To Len(b$)
If InStr(a$, Mid(b, i, 1)) > 0 Then isMutExcl = 0: Exit Function
Next
isMutExcl = 1
End Function
finds 2,455,560 tripleets where, to reiterate, sets B and C are the ones that are disjoint, having an empty intersection, while the pair having the universal (1 - 10) union could be A and B, A and C or B and C.
Note that the number 2,455,560 shouldn't be considered a final answer. What that is depends on what sort of answer you need. If you are looking for the general pattern without regard to which set is which, you should halve this, to 1,227,780, as sets B and C can be interchanged (the same pattern has been counted twice; for example
abcefghij dej ghi
is shown below as one of the answers in the sampling, but certainly
abcefghij ghi dej
was counted sometime as well). As mentioned below, 1 is symbolized a, through 10 being symbolized by j.
But, if on the other hand, you're looking to identify which of the sets is which, you need to multiply the 2,455,560 by 3 as any pair of sets could be disjoint, not just B and C. That makes the answer 7,366,680.
Instead of using numbers 1 - 10, the members are symbolized by the letters a - j, and a sampling is:
abcefghij dej ghi
adfghij bcdei j
adeghj bcefi dg
acdefgij bchij df
acdefgij bcfh degj
acdefghij cgi be
abcghij bj defi
abcdefgh cf bdehij
bcdehi abdi cefghj
bdefghij acdhj begi
bcdfghij cdgh aej
bcdefghi di aceghj
dg dei abcfghj
bcdghj ci abdefghj
abcefgij a defhj
abceghij acdef g
acij abcdef ghij
acdefghi abej chi
acdefghij abdi cef
aij acj bdefghi
aefghij acefh bdgij
acdeghi acdeh bfij
acdghij adhi bcef
abefgi abcfhj degi
abcghij abcdfgi ehj
abcdfghij abef cgi
abdf acd befghij
abcehij adeghi bcfj
abcdghi aeghj bcdfi
adeghi bfghi acdej
acdefgj fg abhij
acefghj eghj abdfi
acdefghj dej abi
afhi cgi abdefhj
adeghi cdeghi abfj
adghij egij abcdfh
abcefgh bdfgij aeh
abcdghij befgj aci
abdegij efghj abcdi
abcdfghij cdei abj
|
|
Posted by Charlie
on 2016-03-16 16:10:34 |
computer solution
