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

 A set of subsets (Posted on 2018-01-17)
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.

Comments: ( Back to comment list | You must be logged in to post comments.)
 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)

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

Text1.Text = Text1.Text & crlf & " done"

End Sub

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
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

 Search: Search body:
Forums (0)