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

Home > Just Math
A set of subsets (Posted on 2018-01-17) Difficulty: 4 of 5
Create a collection of ten distinct subsets of S = {1, 2, 3, 4, 5, 6} such that:

1. each subset contains three elements,
2. each element of S appears in five subsets, and
3. each pair of elements from S appears in exactly two subsets.

Please explain how you did it.

No Solution Yet Submitted by Ady TZIDON    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 2 of 2 |
For the sake of reducing or eliminating trivial variations, I start with the first two subsets being 123 and 124, as 1 and 2 must appear together twice, and it might as well be along with 3 and along with 4.

As the next two subsets from the below list of the 20 possible subsets both contain 1 and 2, the next subset chosen must be from the 5th onward, etc.

I had the computer to the gruntwork with a recursive algorithm, checking that no pair appear more than twice and no individual number appear more than 5 times. This is a sufficient check, as ten subsets will necessarily contain 30 digits, which is five times the six available digits, and there will be 30 digit pairs, which is twice the three available pairs in each subset times the ten subsets.

The possible subsets:

123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456

The possible sets of subsets that include 123 and 124:

123 124 135 146 156 236 245 256 345 346 
123 124 136 145 156 235 246 256 345 346 

One might say the above two are also trivial variations, as they merely interchange 5 and 6. One would then assume that all trivial variations involve mere replacements by some replacement set of digits; there should be 6!; however doing so only recreates the same sets in many instances. In increasing lexicographic order, they reduce to:

123 124 135 146 156 236 245 256 345 346 
123 124 136 145 156 235 246 256 345 346 
123 125 134 146 156 236 245 246 345 356 
123 125 136 145 146 234 246 256 345 356 
123 126 134 145 156 235 245 246 346 356 
123 126 135 145 146 234 245 256 346 356 
124 125 134 136 156 235 236 246 345 456 
124 125 135 136 146 234 236 256 345 456 
124 126 134 135 156 235 236 245 346 456 
124 126 135 136 145 234 235 256 346 456 
125 126 134 135 146 234 236 245 356 456 
125 126 134 136 145 234 235 246 356 456 

All start with 12x and 12y (concatenation of 1 and 2 with x and y, not multiplication), as each pair is required to appear twice including this lowest pair.  The 12 sets are 2*C(4,2) as a given pair of triplets 12x and 12y occur twice each with x and y chosen from 3, 4, 5 and 6.

Note that in the program below, while the pairUsed array is 6x6, only those elements where the subscripts are in ascending order are used, as each subset has its members in ascending order. So we never have a case where separate occurrences are added to different elements of the array.

DefDbl A-Z
Dim crlf$, subset$(20), usedNum(6), setOfSets(10), hist$(10), pairUsed(6, 6)


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 avail$ = "123456"
 For i = 1 To 4
 For j = i + 1 To 5
 For k = j + 1 To 6
   setNo = setNo + 1
   subset(setNo) = Mid(avail, i, 1) + Mid(avail, j, 1) + Mid(avail, k, 1)
   Text1.Text = Text1.Text & subset(setNo) & crlf
 Next
 Next
 Next
 
 setOfSets(1) = 1
 setOfSets(2) = 2
 hist(1) = "123": hist(2) = "124"
 usedNum(1) = 2
 usedNum(2) = 2
 usedNum(3) = 1
 usedNum(4) = 1
 pairUsed(1, 2) = 2
 pairUsed(1, 3) = 1
 pairUsed(2, 3) = 1
 pairUsed(1, 4) = 1
 pairUsed(2, 4) = 1
 
 addOn 3
 
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

Sub addOn(wh)
  Dim saveusednum(6), savepairused(6, 6)
  
  DoEvents
  If wh = 3 Then st = 5 Else st = setOfSets(wh - 1) + 1
  For i = st To 10 + wh
    trial$ = subset(i)
    For j = 1 To 6
     saveusednum(j) = usedNum(j)
     For k = 1 To 6
       savepairused(j, k) = pairUsed(j, k)
     Next
    Next
    
    good = 1
    
    setOfSets(wh) = i
    hist(wh) = subset(i)
    For j = 1 To 3
      usedNum(Val(Mid(subset(i), j, 1))) = usedNum(Val(Mid(subset(i), j, 1))) + 1
      If usedNum(Val(Mid(subset(i), j, 1))) > 5 Then good = 0: Exit For
    Next
    If good Then
      For j = 1 To 2
      jj = Val(Mid(subset(i), j, 1))
      For k = j + 1 To 3
       kk = Val(Mid(subset(i), k, 1))
        pairUsed(jj, kk) = pairUsed(jj, kk) + 1
        If pairUsed(jj, kk) > 2 Then good = 0: Exit For
      Next
      If good = 0 Then Exit For
      Next
      If good Then
        If wh = 10 Then
          For j = 1 To 10
            Text1.Text = Text1.Text & hist(j) & " "
          Next
          Text1.Text = Text1.Text & crlf
        Else
          addOn wh + 1
        End If
      End If
    End If
    
    
    For j = 1 To 6
     usedNum(j) = saveusednum(j)
     For k = 1 To 6
        pairUsed(j, k) = savepairused(j, k)
     Next
    Next
  Next i
End Sub


  Posted by Charlie on 2018-01-17 11:37:00
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 (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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