Proggies

[bplus]

100 Prisoners Problem

'  I saw this last night and just have to check out the solution in code!

' https://www.youtube.com/watch?v=iSNsgj1OCLA

' So 100 prisoners go into a room one at a time and have 50 chances to draw their number from mailbox slots
' they must return the numbers in same box they checked.

' If all the prisoners find their number they go free else they are all executed. Whew!

' But there is a strategy that if used gives them around a 31% chance of being set free!

'      A 31% Change of being set free, how can this be!?

' Here is the startegy, go into the room and pull the number from slot that matches your number.
' From that number go to the number found in the box, contimue in this manner until you find your
' number or you've drawn from 50 slots. If you hit 50 then everyone is doomed might as well start
' another run on the experiment.

' If we run this strategy 100000 times will we get around 31,000 Set Frees and 69,000 Executions?

' Let's see...

' Wow! as predicted

' Let's see...

Code: (Select All)

_Title "100 Prisoners Problem"
Randomize Timer
Dim slots(1 To 100) As Long
For i = 1 To 100
    slots(i) = i
Next
Do
    freed = 0: executions = 0
    Do
        GoSub shuffle
        For p = 1 To 100 ' prisoner number
            count = 1: test = p: madeit = -1
            While count <= 50
                If slots(test) = p Then Exit While Else test = slots(test)
                count = count + 1
                If count > 50 Then madeit = 0: Exit For
            Wend
        Next
        If madeit Then freed = freed + 1 Else executions = executions + 1
    Loop Until (freed + executions) = 100000
    Print "Freed"; freed
    Print "Exceutions"; executions
    Print
    Print "Press any for another run of 100,000... "
    Sleep
    Cls
Loop Until _KeyDown(27)
End
shuffle:
For i = 100 To 2 Step -1
    Swap slots(Int(Rnd * i) + 1), slots(i)
Next
Return


'  I saw this last night and just have to check out the solution in code!
' https://www.youtube.com/watch?v=iSNsgj1OCLA

' So 100 prisoners go into a room one at a time and have 50 chances to draw their number from mailbox slots
' they must return the numbers in same box they checked.

' If all the prisoners find their number they go free else they are all executed. Whew!

' But there is a strategy that if used gives them around a 31% chance of being set free!

'       A 31% Change of being set free, how can this be!?

' Here is the startegy, go into the room and pull the number from slot that matches your number.
' From that number go to the number found in the box, contimue in this manner until you find your
' number or you've drawn from 50 slots. If you hit 50 then everyone is doomed might as well start
' another run on the experiment.

' If we run this strategy 100000 times will we get around 31,000 Set Frees and 69,000 Executions?

' Let's see...

' Wow! as predicted