Skip to content

26 prisoners and a light bulb logic problem in python

by mat on November 14th, 2010

I was sent a interesting logic problem by samsamsam which is as follows (or very similar):

Q: How can the prisoners tell, with certainty, that all 26 of them have visited the central living room with the light bulb.

Riddle:
26 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There’s a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 26 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven’t been to the living room), all 26 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Solution

I won’t explain the solution in words as that might ruin it if you were planning on figuring it out, instead I have posted some python code that calculates the probability of number of days it will take.

# -*- coding: utf-8 -*-
from random import randint

bin=[]
binstep=50

# Loop 
for i in xrange(0,50000):

	nopris=26
	light=0
	count=0
	days=0

	# Create a set of prisoners with value 0 or 1
	# for having visited the room when light is off
	p=[]
	for i in range(0,nopris):
		p.append(0)

	# Until all prisoners have switched light on and have
	# been counted
	while count<nopris-1:
		x=randint(0,nopris-1)
		# First person to be picked is the counter
		if days==0:
			counter=x
			p[x]=1
		# Counter adds one if light is on and resets it
		elif x==counter and light==1:
			light=0
			count+=1
		# If light is off and prisoner hasn't turned light 
		# on before he does so
		elif p[x]==0 and light==0:
			p[x]=1
			light=1
		else:
			pass
		days+=1
		

	# Expand our bin if it isn't big enough
	while days>len(bin)*binstep:
		bin.append(0)
	bin[days/binstep]+=1	
	

# Just chucking data into a histogram type layout
# to speed up processing afterwards (I'm crap at
# openoffice stuff)
for i in range(0,len(bin)):
	print i*binstep+binstep/2,",",bin[i]

For 50k iterations I got the following output:

$ python prisoners.py
25 , 0
75 , 0
125 , 0
175 , 0
225 , 0
275 , 0
325 , 2
375 , 31
425 , 162
475 , 636
525 , 1659
575 , 3492
625 , 5448
675 , 7134
725 , 7755
775 , 7103
825 , 5758
875 , 4341
925 , 2884
975 , 1701
1025 , 909
1075 , 511
1125 , 255
1175 , 124
1225 , 63
1275 , 25
1325 , 4
1375 , 2
1425 , 1

Which shown as a histogram looks like:

Histogram for the 26 prisoners problem (50k iterations)

Histogram for the 26 prisoners problem (50k iterations)

Let me know how you’d improve this method or any other cool logic problems I can have a go at :)

10 Comments
  1. superMeat permalink

    incredible

  2. mmc permalink

    The problem is not clear: how many prisoners are there? 26 or 100? And when they visit the room, is it important whether the light is on or off? You should really adjust your problem description.

  3. @mmc Sorry, c&p error, I have updated it now. There should be consistently 26 prisoners. As to the importance of the light, it is paramount to the problem as this is the only method of communicating (if you can call it that, maybe call it binary communication) that the prisoners have.

  4. Fun! I solved it a totally different way, I’d code it up, but I’m a bit tired .. Instead (since you asked) I’ll pose the question a different way:

    “Q: How can a given prisoner tell, with certainty, that all 26 of them have visited the central living room with the light bulb.

    … However, if it is indeed true, all prisoners are set free, but only after all the prisoners have indicated this. …”

    -Phil

  5. Matt D permalink

    Nice solution, but I think it would go faster if each prisoner was counting, rather than just the first.

  6. @Matt D, But if each prisoner was counting how would they know what number to start on? plus no way of knowing if they count the light on twice for the same person unless they turn off the light which will ruin everyone else’s counting.

  7. Matt D permalink

    @mat: you’re right. I still suspect there’s a way of doing it without a master counter, but I can’t prove it.

  8. anon permalink

    It needs to be clarified that the prisoners are allowed to agree on the protocol, and that one of them is the counter.

  9. WuForumite permalink

    @mat and MattD: you could have, for example, five counters who each count up to five (including themselves). One of them counts up to six to account for the spare prisoner. They do this counting for an agreed number of days. After that, one of them counts the counters, up to five. If any of the first-stage counters don’t fill their quota, they don’t signal in the second phase. If the second phase finishes without all counters having been counted, they repeat the first and second stages indefinitely (with shorter durations than the original phases) until everybody is counted.

    Not that this phased method only works if it is known that the warden picks one prisoner per fixed interval. If he picks them at arbitrary intervals, as in some versions of this puzzle, the prisoners can’t keep track of the number of visits.

    There are various other tweaks you can make to improve this method, and you can try using different numbers of counters, different numbers of phases, etc. Put two phases with [square root of number of prisoners] counters in the first phase is probably close to optimal.

    Much more discussion of this puzzle at William Wu’s Berkeley site.

  10. @WuForumite Interesting, seems complicated but I guess these prisoners don’t have much else to contemplate. It also depends on if they get to communicate before they start, because they would not be able to agree on the number of days without doing so. Just assuming they are quite logical (and share the same logic) they could chose the simpler solution that I posted.

    I may try and model to see what the optimum number of counters/period would be. Thanks for the tip.

Leave a Reply

Note: I am currently writing my thesis so probably wont have time to reply to your comment
Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS