Das merkwürdige Gefängnisexperiment

Das merkwürdige Gefängnisexperiment

Veritasium hat ein Video auf YouTube veröffentlich in dem es um ein merkwürdiges Experiment geht.

100 Gefangene werden nacheinander in einen Raum geschickt. In diesem Raum befinden sich 100 Boxen mit den Zahlen eins bis 100. In jeder Kiste ist eine Zufällige Zahl von 1 bis 100 Jeder Gefangene darf 50 Kisten öffnen und wenn er seine eigene Nummer darin findet, hat er die Aufgabe bestanden und der nächste Gefangene muss vortreten. Jeder Gefangene muss den Raum genau so hinterlassen, wie er ihn vorgefunden hat und darf danach nicht mehr mit den übrigen Gefängnisinsassen kommunzieren. Wenn auch nur einer seine Zahl nicht findet, werden alle exekutiert.

Diese Rätsel müssen immer so blutrünstig sein.

Die Frage: Gibt es eine Strategie, auf die sich die Insassen einigen können, bevor der erste den Raum betritt, durch die sich ihre Chancen erhöhen?
Die vorgeschlagene Lösung: Jeder Gefangene öffnet zunächst die Kiste auf der seine eigene Nummer steht. Each prisoner opens the box with his number as the label first and then moves to the box with the number he finds inside that box.

Zum Beispiel: Gefangener nummer 10 geht in den Raum, öffnet Kiste nummer 10 und gewinnt. Wenn er nicht die 10 vorfindet, öffnet er als nächstes die Kiste, deren Nummer sich in der zuvor geöffneten Kiste befindet und so weiter.

Als mir diese Lösung präsentiert wurde, dachte ich zuerst: Das is sicher eine theoretische Lösung, die in Wirklichkeit keinen Einfluss hat. Ich habe nicht überprüft wie niedrig die Gewinnchancen sind, wenn alle Kisten zufällig geöffnet werden, ich gehe davon aus, dass (1/2)^100 stimmt oder die Zahl doch zumindest äußerst niedig sein dürfte.

Hier ist das Skript, das ausdruckt wie oft alle Gefangenen mit  der vorgeschlagenen Lösung gewinnen.

import numpy as np
import random
import time

print(100*"=")

prisoners = 100 # set number of prisoners here

def run(l):
	for i in range(prisoners):
		success = send_prisoner(l, i) # 
		if not success:
			#print("All dead, accomplished:", i)
			return False, i # i prisoners found their box before 1 failed

	return True, prisoners
	

def send_prisoner(l, prisoner):
	# let 1 prisoner search the boxes
	next_box = prisoner # start with the box with index prisoner
	for i in range(prisoners // 2): # each prisoner can check half the amount of boxes as there are prisoners
		#print("Checking", next_box, "found:", l[next_box]) #uncomment to check if they march in loops
		if l[next_box] == prisoner:
			#print("Found it, tries", i) # uncomment to see how many tries it took each prisoner
			return True
		next_box = l[next_box]
	return False

def get_boxes():
	boxes = []
	for i in range(prisoners):
		boxes.append(i)
	random.shuffle(boxes)
	return boxes

	# returns as many boxes as there are prisoners
	boxes = np.arange(prisoners) # get a list of the numbers [0 ; prisoners -1]
	np.random.shuffle(boxes) #shuffle the numbers inside the boxes
	return boxes

def main():
	successes = 0
	total_successes = 0
	start_time = time.time()
	n = 1000 # how many times the warden gets his sadism on
	for i in range(n):
		l = get_boxes()
		success, total = run(l) # run 1 experiment
		#print("Run no:", i, "successes:", total)
		total_successes += total
		if success:
			successes += 1
	
	end_time = time.time()
			
	win_ratio = successes / n
	total_completed = total_successes / (prisoners * n)
	print("Total prisoners that succeeded", total_successes, "out of: ", (prisoners * n), "=>", total_completed)
	print("Win ratio:", str(round(win_ratio * 100, 3)) + '%')
	print("Method took:", end_time - start_time) # so you can plan ahead how much time it would take to increase either n or prisoners
	
if __name__ == "__main__":
	main()

Das Skript weiter unten erzeugt automatisch Graphen, von denen 4 hier präsentiert werden.

100,000 durchläufe erzeugten folgendende Zahlen:

Gefangene: 2, Erfolgsrate 0.49721
Gefangene: 20, Erfolgsrate 0.32954
Gefangene: 50, Erfolgsrate 0.31907
Gefangene: 100, Erfolgsrate 0.31063
Gefangene: 200, Erfolgsrate 0.30901
Gefangene: 500, Erfolgsrate 0.30874
Gefangene: 1000, Erfolgsrate 0.30913

 

Wie zu erwarten reicht es nicht aus, das Experiment 100 mal zu wiederholen um statistisch relevante Aussagen treffen zu können. Das wäre ein wenig wie 6 mal zu würfeln und alle Zahlen von 1 bis 6 genau einmal zu erwarten.

1.000 Iterationen bringen uns dem tatsächlichen Ergebnis etwas näher und 100.000 Durchläufe sollten genügen, um statistisch zu belegen, dass die oben vorgeschlagene Methode die Chancen von nahe null auf über 30% erhöht. Sieh einer an.

Und da dies hier nicht BlenderDiplom wäre, wenn wir das Script, mit dem man diese Ergebnisse grafisch darstellen kann  nicht einfügen würden:

import random
import time

from bpy import data as D
from bpy import context as C
from mathutils import Vector

print(100*"=")

def run(l, prisoners):
	for i in range(prisoners):
		success = send_prisoner(l, i) # 
		if not success:
			#print("All dead, accomplished:", i)
			return False, i # i prisoners found their box before 1 failed

	return True, prisoners
	
def send_prisoner(l, prisoner):
	# let 1 prisoner search the boxes
	next_box = prisoner # start with the box with index prisoner
	length = len(l) // 2
	for i in range(length): # each prisoner can check half the amount of boxes as there are prisoners
		#print("Checking", next_box, "found:", l[next_box]) #uncomment to check if they march in loops
		if l[next_box] == prisoner: # number inside the box equals the number of the current prisoner
			#print("Found it, tries", i) # uncomment to see how many tries it took each prisoner
			return True
		next_box = l[next_box]
	return False

def get_boxes(prisoners):
	# returns as many boxes as there are prisoners
	boxes = []
	for i in range(prisoners):
		boxes.append(i)
	random.shuffle(boxes)
	return boxes

def run_experiment(prisoners, n):
	team_successes = 0 # number of times all prisoners succeded
	start_time = time.time()
	results = []
	
	for i in range(n):
		l = get_boxes(prisoners)
		success, total = run(l, prisoners) # run 1 experiment
		#print("Run no:", i, "successes:", total)
		if success:
			team_successes += 1
	
	win_ratio = team_successes / n
	return win_ratio


def plot(results, distance):
	mesh = D.meshes['Plane'] # the base mesh for the bar, add a plane and scale it in Edit Mode
	collection = D.collections['Plot']
	txt_mat = None
	bar_mat = None
	if not 'Label' in D.materials:
		txt_mat = D.materials.new('Label')
	else:
		txt_mat = D.materials['Label']

	for i, result in enumerate(results):
		prisoners = result['prisoners']
		print("Prisoners", prisoners, "Win rate", result['win_ratio'])
		label = str(prisoners)
		txt = D.curves.new(type="FONT", name = 'Label-' + label) # need to use a font curve as object data
		txt.body = label 
		txt.align_x = 'CENTER'
		txt_ob = D.objects.new('Label-' + label, txt) # curve here, text does not work directly
		txt_ob.data.materials.append(txt_mat) # so you can change the appearance of all labels at once
		
		x = i * distance # evenly space the results
		txt_ob.location = Vector((x, -1.2, 0)) #hardcoded values that fit the current setup
		txt_scale = 1.3
		txt_ob.scale = Vector((txt_scale, txt_scale, txt_scale))
		bar = D.objects.new('Bar-' + label, mesh)
		bar.scale = Vector((1, result['win_ratio'] * 20, 1))
		bar.location = Vector((x, 0, 0))
		collection.objects.link(txt_ob) # link the objects to the collection
		collection.objects.link(bar)
		
def main():
	start_time = time.time()
	results = []
	current_prisoners = [2, 20, 50, 100, 200, 500, 1000]
	n = 100 # how many times the warden gets his sadism on
	for prisoners in current_prisoners:
		win_ratio = run_experiment(prisoners, n)
		result = { # use a struct to link the current no of prisoners to their win ratio
				'prisoners' : prisoners,
				'win_ratio' : win_ratio
			}
		results.append(result)
		print(prisoners, "prisoners:", win_ratio)
	end_time = time.time()
	print("Calculations took:", end_time - start_time) # in sec so you can plan ahead how much time it would take to increase either n or prisoners
	distance = 4 # spacing between 2 bars
	plot(results, distance)

if __name__ == "__main__":
	main()