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

 Matching pegs (Posted on 2016-06-08)
There are 20 garments on a clothes line each garment supported by two pegs.
The pegs were randomly picked out of a set of 20 green and 20 red pegs.

What is the probability that n garments are supported by two pegs of the same colour?

Provide a list for 21 possible values of n.

Source: Australian Joe Kupka

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer assisted solution | Comment 1 of 2
While the puzzle asks merely for the total of garments whose pegs match, regardless of whether the match is two reds or two greens, for subsequent conditional match probabilities after a given garment's pins are chosen, it matters whether the matches up to that point have all been one color or various stages in between that situation and an even mix.  Just to take one example, If the first 20 pins and therefore the first 10 garments had all green, then the rest would be assured of being matches.  However, if the first 10 garments had all had matching pins for each garment, but half the garments had red matches and the other half green, the probability of non-matches in subsequent choices would be noticeably reduced.

In going through the 20 generations of pin choices for the 20 garments, it is necessary to keep track of the probabilities of the number of green matches and of red matches.  The mixed color garments are of course the generation number minus the green-matched minus the red-matched. Two red vs green grids are kept so that old values do not interfere with the new values from one generation to the next (garment). Though we are not tracking the mismatches, we do need to calculate that probability as that results in the number of red matches and green matches staying the same for the next generation and therefore its probability in the next generation of probabilities is multiplied by the probability of the newly included garment being a non-match.

After pegs for all 20 garments have been selected (20 generations of probabilities), the grid looks like this:

`              both green     \bothred       0        1         2         3         4         5         6         7         8         9        10 0  0.0000076 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000  1  0.0000000 0.0007226 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000  2  0.0000000 0.0000000 0.0138207 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000  3  0.0000000 0.0000000 0.0000000 0.0921378 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000  4  0.0000000 0.0000000 0.0000000 0.0000000 0.2620169 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000  5  0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.3458623 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000  6  0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.2161639 0.0000000 0.0000000 0.0000000 0.0000000  7  0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0617611 0.0000000 0.0000000 0.0000000  8  0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0072376 0.0000000 0.0000000  9  0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0002681 0.0000000 10  0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000013 1`

The number of green matched pairs must, of course, at the end equal the number of red matched pairs.  That's not the case of course during intermediate stages.

As a check the program printed the total of the above numbers and it is indeed

1

The probabilities, lined up below, were taken by adding diagonals on the above diagram.  As red matches must equal green matches, there can't be an odd number of garments with matched pegs.

n    probability

0  0.0000076068365
1  0.0000000000000
2  0.0007226494628
3  0.0000000000000
4  0.0138206709760
5  0.0000000000000
6  0.0921378065064
7  0.0000000000000
8  0.2620168872527
9  0.0000000000000
10  0.3458622911735
11  0.0000000000000
12  0.2161639319834
13  0.0000000000000
14  0.0617611234238
15  0.0000000000000
16  0.0072376316512
17  0.0000000000000
18  0.0002680604315
19  0.0000000000000
20  0.0000013403022

1 done

the 1 representing another check: that these numbers add to 1.

Unfortunately, the grid is too big to dimension in UBASIC, so to get a version in which the probabilities are given in rational fraction form, I had to rewrite using a user-defined Type fraction in VB.  The resulting equivalent tables, and verification of totals as being 1, are:

` 0  262144/34461632205 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1  1  0/1 4980736/6892326441 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1  2  0/1 0/1 10584064/765814049 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1  3  0/1 0/1 0/1 211681280/2297442147 0/1 0/1 0/1 0/1 0/1 0/1 0/1  4  0/1 0/1 0/1 0/1 6615040/25246617 0/1 0/1 0/1 0/1 0/1 0/1  5  0/1 0/1 0/1 0/1 0/1 1323008/3825245 0/1 0/1 0/1 0/1 0/1  6  0/1 0/1 0/1 0/1 0/1 0/1 165376/765049 0/1 0/1 0/1 0/1  7  0/1 0/1 0/1 0/1 0/1 0/1 0/1 330752/5355343 0/1 0/1 0/1  8  0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 38760/5355343 0/1 0/1  9  0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 12920/48198087 0/1 10  0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 323/240990435 1/1`

For reference below, I've placed the decimal equivalents from above, to the right, manually:

` 0 262144/34461632205    0.0000076068365 1 0/1                   0  2 4980736/6892326441    0.0007226494628 3 0/1                   0  4 10584064/765814049    0.0138206709760 5 0/1                   0  6 211681280/2297442147  0.0921378065064 7 0/1                   0  8 6615040/25246617      0.2620168872527 9 0/1                   0 10 1323008/3825245       0.345862291173511 0/1                   0 12 165376/765049         0.216163931983413 0/1                   0 14 330752/5355343        0.061761123423815 0/1                   0 16 38760/5355343         0.007237631651217 0/1                   0 18 12920/48198087        0.000268060431519 0/1                   0 20 323/240990435         0.00000134030221/1 done`

Being the rational numbers, they are exact.

Program 1 -- decimal fractions

DefDbl A-Z
Dim crlf\$, oldgrid(), newgrid()

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

ReDim oldgrid(10, 10)
oldgrid(0, 0) = 1
For garm = 1 To 20
ReDim newgrid(10, 10)
For red = 0 To garm - 1
If red <= 10 Then
For green = 0 To garm - 1 - red
If green <= 10 Then
tused = 2 * (garm - 1)
tsupply = 40 - tused
nonpaired = tused - 2 * red - 2 * green
rsupply = 20 - 2 * red - nonpaired / 2
gsupply = 20 - 2 * green - nonpaired / 2
If rsupply >= 0 And gsupply >= 0 Then
If tsupply <> rsupply + gsupply Then
Text1.Text = Text1.Text & "error"
Exit Sub
End If
prr = (rsupply / tsupply) * ((rsupply - 1) / (tsupply - 1))
pgg = (gsupply / tsupply) * ((gsupply - 1) / (tsupply - 1))
prg = 2 * (rsupply / tsupply) * ((gsupply) / (tsupply - 1))
If prr > 0 Then newgrid(red + 1, green) = newgrid(red + 1, green) + prr * oldgrid(red, green)
If pgg > 0 Then newgrid(red, green + 1) = newgrid(red, green + 1) + pgg * oldgrid(red, green)
If prg > 0 Then newgrid(red, green) = newgrid(red, green) + prg * oldgrid(red, green)
End If
End If
Next green
End If
Next red
For red = 0 To garm
If red <= 10 Then
For green = 0 To garm - red
If green <= 10 Then
oldgrid(red, green) = newgrid(red, green)
End If
Next
End If
Next
Next garm

For red = 0 To 10
Text1.Text = Text1.Text & mform(red, "#0") & "  "
For green = 0 To 10
Text1.Text = Text1.Text & mform(oldgrid(red, green), "0.0000000") & " "
tprob = tprob + oldgrid(red, green)
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf & tprob & crlf & crlf

tprob = 0
For n = 0 To 20
matches = n
nprob = 0
For red = 0 To 10
green = matches - red
If green >= 0 And green <= 10 Then
nprob = nprob + newgrid(red, green)
End If
Next
Text1.Text = Text1.Text & mform(n, "#0") & mform(nprob, "##0.0000000000000") & crlf
tprob = tprob + nprob
Next

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

End Sub

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

Program 2 -- rational fractions:

DefDbl A-Z
Dim crlf\$, oldgrid() As fraction, newgrid() As fraction
Private Type fraction
num As Double
den As Double
End Type
Dim mult1 As fraction, mult2 As fraction
Dim nprob As fraction, tprob As fraction, prr As fraction, pgg As fraction, prg As fraction

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

ReDim oldgrid(10, 10) As fraction
oldgrid(0, 0).num = 1
oldgrid(0, 0).den = 1
For garm = 1 To 20
ReDim newgrid(10, 10) As fraction

For red = 0 To garm - 1
If red <= 10 Then
For green = 0 To garm - 1 - red
If green <= 10 Then
tused = 2 * (garm - 1)
tsupply = 40 - tused
nonpaired = tused - 2 * red - 2 * green
rsupply = 20 - 2 * red - nonpaired / 2
gsupply = 20 - 2 * green - nonpaired / 2
If rsupply >= 0 And gsupply >= 0 Then
If tsupply <> rsupply + gsupply Then
Text1.Text = Text1.Text & "error"
Exit Sub
End If
mult1.num = rsupply: mult1.den = tsupply
mult2.num = rsupply - 1: mult2.den = tsupply - 1
prr = mult(mult1, mult2)
mult1.num = gsupply: mult1.den = tsupply
mult2.num = gsupply - 1: mult2.den = tsupply - 1
pgg = mult(mult1, mult2)
mult1.num = 2 * rsupply: mult1.den = tsupply
mult2.num = gsupply: mult2.den = tsupply - 1
prg = mult(mult1, mult2)
If prr.num > 0 Then newgrid(red + 1, green) = add(newgrid(red + 1, green), mult(prr, oldgrid(red, green)))
If pgg.num > 0 Then newgrid(red, green + 1) = add(newgrid(red, green + 1), mult(pgg, oldgrid(red, green)))
If prg.num > 0 Then newgrid(red, green) = add(newgrid(red, green), mult(prg, oldgrid(red, green)))
End If
End If
Next green
End If
Next red
For red = 0 To garm
If red <= 10 Then
For green = 0 To garm - red
If green <= 10 Then
oldgrid(red, green) = newgrid(red, green)
End If
Next
End If
Next
Next garm

For red = 0 To 10
Text1.Text = Text1.Text & mform(red, "#0") & "  "
For green = 0 To 10
If oldgrid(red, green).num = 0 Then oldgrid(red, green).den = 1
Text1.Text = Text1.Text & oldgrid(red, green).num & "/" & oldgrid(red, green).den & " "
tprob = add(tprob, oldgrid(red, green))
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf & tprob.num & "/" & tprob.den & crlf & crlf

tprob.num = 0: tprob.den = 1
For n = 0 To 20
matches = n
nprob.num = 0: nprob.den = 1
For red = 0 To 10
green = matches - red
If green >= 0 And green <= 10 Then
nprob = add(nprob, newgrid(red, green))
End If
Next
Text1.Text = Text1.Text & mform(n, "#0") & Str(nprob.num) & "/" & nprob.den & crlf
tprob = add(tprob, nprob)
Next

Text1.Text = Text1.Text & crlf & tprob.num & "/" & tprob.den & " done"

End Sub

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

Private Function add(a As fraction, b As fraction) As fraction
Dim answ As fraction
If a.num = 0 Then a.den = 1
If b.num = 0 Then b.den = 1
d = lcm(a.den, b.den)
answ.num = a.num * d / a.den + b.num * d / b.den
answ.den = d
If answ.num = 0 Then answ.den = 1
g = gcd(answ.num, answ.den)
answ.num = answ.num / g
answ.den = answ.den / g
End Function

Private Function mult(a As fraction, b As fraction) As fraction
Dim answ As fraction
answ.num = a.num * b.num
answ.den = a.den * b.den
g = gcd(answ.num, answ.den)
answ.num = answ.num / g
answ.den = answ.den / g
If answ.den < 0 Then answ.num = -answ.num: answ.den = -answ.den
mult = answ
End Function

Function gcd(a, b)
x = a: y = b
Do
q = Int(x / y)
z = x - q * y
x = y: y = z
Loop Until z = 0
gcd = x
End Function

Function lcm(a, b)
lcm = a * b / gcd(a, b)
End Function

 Posted by Charlie on 2016-06-08 13:19:16

 Search: Search body:
Forums (0)