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

Home > Probability
Matching pegs (Posted on 2016-06-08) Difficulty: 3 of 5
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.)
Solution 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

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

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