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

Home > Numbers
Set Me Up Again (Posted on 2016-03-16) Difficulty: 4 of 5
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?

No Solution Yet Submitted by Brian Smith    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 1 of 1
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
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 (10)
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