Let k be a positive integer. Suppose that the integers 1, 2, 3, ...3k, 3k + 1 are written down in random order.
What is the probability that at no time during this process, the sum of the integers that have been written up to that time is divisible by 3?
Source: Putnam competition
The following program counts instances directly by permuting strings of the form "1231231231", with k repetitions of "123" followed by a "1". All permutations are counted.
DefDbl A-Z
Dim crlf$
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For k = 1 To 5
s$ = ""
For i = 1 To k
s = s + "123"
Next
s = s + "1"
h$ = s
tr = 0: hit = 0
Do
tot = 0
tr = tr + 1
good = 1
For i = 1 To Len(s)
tot = tot + Val(Mid(s, i, 1))
If tot Mod 3 = 0 Then good = 0: Exit For
Next
If good Then hit = hit + 1
permute s
DoEvents
Loop Until s = h
Text1.Text = Text1.Text & k & Str(Len(s)) & Str(hit) & "/" & tr & mform(hit / tr, " 0.0000000") & crlf
Next k
Text1.Text = Text1.Text & crlf & " 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
For the first five k, given below are k, the length of the string, and the probability in fraction and decimal:
1 4 3/12 0.2500000
2 7 15/210 0.0714286
3 10 84/4200 0.0200000
4 13 495/90090 0.0054945
5 16 3003/2018016 0.0014881
|
|
Posted by Charlie
on 2016-03-17 14:39:24 |
Values for the first 5 k
