perplexus.info :: Probability : Matching pegs

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
     \
both
red       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

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.3458622911735
11 0/1                   0 
12 165376/765049         0.2161639319834
13 0/1                   0 
14 330752/5355343        0.0617611234238
15 0/1                   0 
16 38760/5355343         0.0072376316512
17 0/1                   0 
18 12920/48198087        0.0002680604315
19 0/1                   0 
20 323/240990435         0.0000013403022
1/1 done

Being the rational numbers, they are exact.

Program 1 -- decimal fractions

DefDbl A-Z

Dim crlf$, oldgrid(), newgrid()

Private Sub Form_Load()

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

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

Text1.Text = Text1.Text & crlf

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

Text1.Text = Text1.Text & mform(n, "#0") & mform(nprob, "##0.0000000000000") & crlf

tprob = tprob + nprob

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

Private Sub Form_Load()

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

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

Text1.Text = Text1.Text & crlf

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

Text1.Text = Text1.Text & mform(n, "#0") & Str(nprob.num) & "/" & nprob.den & crlf

tprob = add(tprob, nprob)

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

add = answ

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

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

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 (20)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info