The Circular Prison

Danikov

2:47 AM

this problem is evil and I think I'm missing something in the definition that makes it remotely possible

xnor has suggested that you may pass out instructions once per day, rather than once overall (which I had assumed)

Mike Earnest

you only pass out one sheet of instructions, at the very beginning, your assumption was correct

Danikov

even then the involvement of a malicious warden makes any solution via lights highly improbable

do the prisoners keep their n-1 sheets?

I have the feeling the fact that he makes n-1 copies might be relevant

Mike Earnest

They do not keep the sheets: these disappear the first night the warden cleans the cells

the fact that there are sheets is not relevant; the warden could have shown everyone else the plan on his smartphone

Danikov

well, if we assume a cooperative strategy, in which the warden doesn't move the prisoners, e.g. you flip on the light and tell all the prisoners to flip their light the next day if their light flipped the day before...

in that case you count the days until your light flips on, that equals the number of prisoners

if there's more than 30,000 prisoners, you probably die of old age before you find out how many prisoners there were

Mike Earnest

you do have to forget about realistic concerns, such as mortatility and imperfect memory, for this problem to work

Danikov

2:57 AM

I'm guessing then you think you have a strategy that involves the single bit communication?

I still think the warden is capable of maliciously foiling any strategy

I'm a little confused by his confession for liking maths, then his resumption of his malicious ways

the only idea that I thought had any merit was something akin to radioactive dating

if you get your n prisoners to behave like radioactive particles and decay, you could somehow measure the rate of decay and extrapolate the very approximate starting mass

but it would be very fuzzy numbers, to start, and the warden could interfere with it quite easily by identifying a 'decayed' prisoner and placing them next to your cell so you never receive information

it's very difficult to have any kind of fan-out strategy as the warden can misdirect it

because you don't know the limits to n, there's a halting problem. even if the warden every day tapped out the size of n in binary to you, you wouldn't know when it had terminated

I think I have an evil solution

"What plan allows the prisoners guarantee their freedom?" < I think there's a 'to' missing in that

Mike Earnest

3:13 AM

oops, you're right. I'll fix that when I add a bunch of clarifications later. What is your evil solution?

of course, feel free to post it as an answer

Danikov

not a healthy one, but it might get a few laughs

posted

hah, I guess people don't like it

so much for lateral thinking [shrug]

Mike Earnest

Well, when you a problem has a huge detailed setup, you kind of expect the solution will require using most of the given info

Danikov

true, but a gordian knot requires a sword

Danikov

3:34 AM

for the benefit of others, how many cells can be seen from other cells?

Mike Earnest

the cells are windowless as well, I forgot to add that

the intention is that the only way of communicating is to send a single bit once a day, and the warden chooses who receives that bit

Danikov

does the warden chose before or after the bit?

I assume it's before because he places the prisoners

not that the prisoners have any defining information on what to transmit except based on their memory of flashes from previous days

Mike Earnest

before. the problem says he does the placement at midnight, while the bit sending happens at noon

Danikov

so the rooms really don't matter. same effect could be achieved with a lighting switchboard

I assume all the prisoners know when it's noon and thus whether their light did or didn't get switched

is there any consistency to the switches themselves?

I mean, because the bulb flashes, that suggests more of a button than a switch

because there's no 'on' state

and we're assuming the warden doesn't reset the switch, being malicious

Mike Earnest

think of it like this: the switches are normal light switches. If they are "on" at noon, then they give a single flash at noon. Otherwise, nothing happens

Danikov

3:41 AM

can the prisoners break the lights or do they get replaced?

Danikov

4:01 AM

so, I've thought of a really evil warden strategy

each day, the warden moves all prisoners counter clockwise, except for yourself

that means every prisoner you signal, will signal you back the next day

that leaves you personally unable to exploit the lightswitch states

so you can only go off of binary alone

you don't know the size of n, so even if you suspected a cycle, you don't know the size of the cycle, and each prisoner communicates with you 1 once per cycle, and (unknown to them) the same other prisoner n-1 times per cycle

I'm sure there's other strategies to come up with that limit the potential of even a single bit reaching the nth prisoner exponentially

the problem being, within that possibility, the warden can vary their strategy, making it utterly impossible to impose any sort of order

Danikov

4:38 AM

cripes, didn't realise puzzlers were such a negative bunch

Mike Earnest

5:01 AM

I understand why Wossname was frustrated, I wrote the puzzle incorrectly, then invalidated his solution when I corrected it. :/

Danikov

5:25 AM

I still think it's insoluable, so I'm expecting a very complex answer or a very clever one

and I still suspect there'll be a warden strategy that stymies it

user61230

I'm also not sure it's solvable... I'm really curious to see what the solution is. It seems like even if the mathematicians can encode information in binary, the warden can just totally scramble it before you get to read it.

user61230

Not ready to give up quite yet, though...

Danikov

there is one foolproof way for all the other inmates to transmit a message, if they all do the same lightswitching in sync

but that would mean a) coordinating themselves to do so, and b) having the right information/code to transmit

at the core of the problem is you get a series of bits from unknown sources, all indistinguishable from each other. the only action you can take is to transmit bits to unknown targets, also indistinguishable

user61230

Hmm.... randomization makes the order of light flips unreliable. That means the only information each prisoner has is the number of times they've seen a light source.

Danikov

well, not even that

because the warden can ringfence information

if you send a bit to a prisoner, he can treat that prisoner as 'tainted'

so, next cycle, he moves him upstream of you

user61230

5:38 AM

That's true, but the information will still travel given enough time

Danikov

that's just it, information doesn't travel

there's no meaning to a single bit

it's data

it becomes noise because there's no way to distinguish a bit from another bit

user61230

Hmm... is it possible to trap a bit, though? I can't design an algorithm that's guaranteed to trap information.

user61230

Let's say all the mathematicians follow the rule "If I see a light, on all successive nights I will turn a light on."

Danikov

right, so what's the end condition for you?

user61230

that would be the issue

user61230

5:40 AM

but the main thing is, you can't trap the information "I have seen a light."

user61230

so while the warden can do a lot to delay the information, I'm not sure it's possible to fence it in completely.

Danikov

yes, you're absolutely right in the sense that...

if I keep turning my light on every night

and the warden considers each prisoner 'corrupted' or 'triggered' by that light and relocates them so I can't continue to communicate with them...

eventually I should be able to send 1 bit to every prisoner

but that still tells me nothing

if I'm waiting for them to light my light, the warden merely moves the first prisoner I signal to the other side of my cell

and I falsely believe that there are 2 prisoners

the malice of the warden means that a solution has to be short-circuit proof

the question still is, what is your end condition?

either you count bits or somehow a pattern is transmitted

a pattern requires total coordination between all other prisoners else the warden can disrupt it

user61230

Hrrrm. What if you're not the one who calls out the information?

user61230

You're the only one who doesn't follow the pattern, which means the disk of prisoners becomes ordered.

Danikov

that's a possibility

user61230

5:46 AM

But by virtue of being the one who fixes the disk order, I'm not sure you can actually collect information out of it.

user61230

However, the person to your left can become the designated Information Gatherer on the first night.

user61230

"If you don't see a light on the first night, you're the one to gather information. Then, the patterns begin."

Danikov

nah, that doesn't work

because the warden has multiple options

he can either a) move the prisoner before you, so you only propagate one light to the prisoner after you

or b) move the prisoner away from you, so you and him both spawn two new prisoners

so now there's uncertainty over how many lights out there are

also, how do you count?

how do you know when nobody else has their lights on?

you have the ability to propagate, but not predictably

lets say you have the ability to force a range of values on the warden

say there's a minimum and maximum value

what's to stop the warden from forcing that outcome each time so you can't sample other values?

let's assume you come up with a sample based solution

e.g. after 10,000 bits, I can ascertain the size of n somehow

how can you uniquely encode n into a fixed sized if it is unbounded?

user61230

Hmm. There needs to be an algorithm by which certain values of $n$ are not possible.

Danikov

well you can't eliminate from the bottom because that's still unbounded

and how do you eliminate down from infinity?

user61230

5:55 AM

you'd have to count up until someone's state enters an illegal configuration

user61230

though, hm.

Danikov

I suppose we can put an upper limit, though

if they somehow know the population of the planet, n must be less

if they're sure of that figure, or you are, you can communicate it via the instructions

user61230

I'm still trying to think of a legal stopping condition

Danikov

let's say somehow, once per some larger cycle of bits, one prisoner reaches a 'illegal' state

what do they do? stop sending bits?

how do we count how many illegal states there are?

user61230

Let's say a prisoner turns on their light every $m$th night, where $m$ is the number of nights they've seen a light.

user61230

6:03 AM

...nevermind, I'm not sure that's a helpful path.

leoll2

6:20 AM

Could anyone link the puzzle please? I can't find it

Is this? puzzling.stackexchange.com/questions/16168/…

user61230

@leoll2 Yup!

leoll2

It's amazing, it's my favourite kind of problems.

I suspect a relationship with puzzling.stackexchange.com/questions/10130/…

user61230

I'm still puzzling over it...

leoll2

6:35 AM

My mind is blowing

I don't understand the Extra question; if they make random decisions, aren't they likely to be executed?

Danikov

I'm assuming there's a strategy in which a random element is involved

not shouting out random numbers :D

Mike Earnest

@leoll2 xnor brought up this point as well in a comment

it turns out that there are algorithms which almost solve this, except they get stuck in loops

random decisions allow the prisoners to break out of these loops

leoll2

Ah I see, but still with the risk of being executed, right?

Danikov

how do you break out of a warden enforced loop?

Mike Earnest

no risk, they only use the random choices to decide on light flipping strategies, but they still only guess when they are sure they know the answer

Danikov

6:48 AM

out of curiosity, how long are the instructions for your ideal answer? a paragraph? a page?

Mike Earnest

@Danikov the one I have written up right now is two pages, but it could be written more slickly

Danikov

well, it ain't simple then

leoll2

Lateral-thinking answer: you write so many pages that the gravitational force bends the prison bars

user61230

Lateral-thinking answer: the warden is friendly and doesn't like killing people, so you can guess anything and he's not going to kill you anyway.

Danikov

yeah, there's a bit of a discontinuity there

but it's kinda moot to the problem

leoll2

6:54 AM

What if the warden's evilness is indeed in the fact that you struggle to find a solution which doesn't exist?

Mike Earnest

@leoll2 :o

user61230

If the mathematicians are perfect logicians, they'd realize it instantly and just be irritated ;)

user61230

I'm just not seeing how any state information can be reliably conveyed.

leoll2

Trivial question: can they see the number of their cell?

user61230

I don't think so; the cells are unidentifiable.

user61230

6:58 AM

However, it's possible for one person to fix themself at the zero point; it just means everybody else shuffles randomly around them.

Danikov

ah, relativity

user61230

...unless you forfeit knowledge of where the zero point is entirely after the first iteration, and let some indicator tell you when the zero point gets back to you.

Danikov

I think the circular layout is misleading

they could be in any layout and the room just randomly wired in what is eventually a cycle

not that it even matters

because the prisoners move every day too

it just means that there's always 1 in, 1 out

user61230

it does matter that the elements are in a cycle, though

Danikov

how?

user61230

7:03 AM

you're trying to count the number of elements in the cycle

user61230

since each element has one input and one output, there must be a finite number of cycles

Danikov

except for the fact that you can be moved from any room to another

user61230

right, but the rooms must be in a cycle

Danikov

but you can only shuffle bits once in a circle

then you randomise the circle

the circle is irrelevant

user61230

but if there are two cycles, you can't express the positions relative to an individual

leoll2

7:04 AM

The shape doesn't matter, as long as you keep the light wires in the correct pattern

Danikov

yeah, but it could be a square

or a block

leoll2

It's just easier to explain it with a circle

user61230

oh, yeah, the shape doesn't matter, but the number of cycles does

Danikov

the rooms have no meaningful relationship to each other

just how they're wired, in a cycle

user61230

other than that they form a connected graph :P

Danikov

7:05 AM

except that the warden can reshuffle the graph at will

user61230

er, connected isn't the right word, but you know what I mean

Danikov

unidirectional cyclical graph

user61230

yeah, that

Danikov

with no spurs

one child, one parent :D

user61230

the warden is incapable of virtually creating two or more cycles, though

user61230

7:07 AM

so the case of one cycle and $m$ cycles aren't equivalent

Danikov

the warden is capable of isolating anyone he thinks has too much information

user61230

but he's not capable of isolating the information that person has

Danikov

because the prisoners can only propagate information at 1 bit per day

user61230

that's the important part

user61230

if the warden were able to make multiple cycles, he'd be able to prevent a subset of people from seeing information

user61230

7:08 AM

but he can't do that; no matter what the warden does, any information someone has will eventually escape

Danikov

but the information is 1 bit!

it's not informative

leoll2

Also, if they get the information at noon, how can they "answer" if everything resets at midnight (before the next noon)?

Danikov

I don't think their memories reset

user61230

I'll grant that, but the information can't be restricted - in other words, even if it doesn't make sense to anyone else, it must eventually escape confinement

Danikov

the endgame for the problem is one of two possibilies, regarding the warden

either he can't act, or his actions are ineffective

as long as he actions that give multiple results, he can foul your ability to compensate for him

leoll2

7:10 AM

I think this could be a great problem for IMO (international math olympiad)

Danikov

let's say, my first move, I send a bit to prisoner a, knowing that my instructions will cause him to send a bit to prisoner a+1 next time around

if we suppose my intent is that the bit eventually reaches everyone and there's a single bit that tours, and I count the days...

the warden moves that prisoner to the cell before mine

on day 2 I get a bit, and go 'there's 2 prisoners', except the warden has tricked me

let's assume the opposite. I'm going to try to maximise sending bits until all the lights are on

the warden can adjust how many lights toggle per cycle by moving prisoners to either light the light of prisoners who are already lighting their lights

user61230

Ahh, I see what you're saying. There must be multiple final configurations which encode the same information, and the warden has to be trapped into picking one of those equivalent final configurations.

Danikov

or move them to fresh prisoners

user61230

...that means there have to be $n!$ final configurations

Danikov

so, while there is the possibility to affect every prisoner within a timeframe, that timeframe is somewhere between log n and n days

and the amount of information in that single propagation alone is 1 bit

at no point have we begun to count anything

and at no point do I, as the instigator of that signal, can be sure that it is fully propagated

user61230

7:14 AM

if it minimally takes $\log n$ days to convey one bit, then a lower bound on the number of days is $(\log n)^2$ to solve the puzzle

Danikov

I don't know n

the first move of the warden could be to move the first prisoner I signalled before me, so I'll get a bit forever more

user61230

Ah, there's one more piece of information we're forgetting.

user61230

The prisoners know what the night number is.

Danikov

how?

user61230

They know how many bits they've received.

Danikov

7:17 AM

ah, damn, I think I solved it

user61230

Hmm?

leoll2

Can't wait to see

Danikov

oh, it's very vague in my head, but I'm certtain it'll result in a solution

the numbers get a bit massive

let's say day 1 is time 1

and day 2 and 3 are time 2

day 4, 5, 6 are time 3

pascal numbers, basically

that lets you communicate multiple bits to communicate a number forward

leoll2

triangular numbers, you mean?

Danikov

yeah

ah, it doesn't work

because of the warden scrambling

day 2 I could have prisoner a in front of me

day 3, prisoner z

so I can't even communicate a coherent sequence of bits

user61230

7:21 AM

mm, you totally can

Danikov

I can either send 1 bit to everyone

user61230

each prisoner broadcasts their number using the pascal triangle

user61230

when you receive a number equal to your own, that's the number of people

Danikov

you're assuming they're numbered

user61230

okay, each prisoner follows a rule: if they haven't seen a light before, and receive the number $m$, they broadcast $m+1$.

Danikov

7:23 AM

and you still don't get a coherent set of bits

but they can't broadcast the number

user61230

they can using the pascal triangle

Danikov

warden can just shuffle them around so the information is scatered

no, it doesn't work because the warden is malicious

they can still only send 1 bit per day

then the warden shuffles

user61230

but that bit tells them whether this night corresponds to a number on the tree

user61230

in other words, in one night a mathematician can send any complete number; they just have to wait until the right night to do it

user61230

the warden can't trap or destroy that information because it's all sent in one night

Danikov

7:24 AM

right, but it means a number can only ever be sent once

user61230

not necessarily

Danikov

how big is the loop?

user61230

divide up the tree so that on the $q$th iteration, you can broadcast $2^q$ numbers

user61230

on the $2^q+1$th iteration, the entire counting process starts over

Danikov

so 1, 1, 2, 1, 2, 3, 1, 2, 3, 4

user61230

7:25 AM

everyone jettisons their status; there weren't enough bits to count everyone

user61230

so they try again with one more factor of two

Danikov

or binary, probalby more efficient

user61230

more like [1], [1, 2], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7, 8]...

Danikov

eh, whatever cycle is necessary

problem is, who are you sending that number to

and what are they doing with it?

let me put it this way, you must always act on your input

otherwise the warden can use you as a dead-end

user61230

You send it to the next person, after either keeping it the same, or, if this is the first time you've seen a number, one higher

Danikov

7:28 AM

doesn't accomodate for bifurcation

user61230

?

Danikov

let's say I give prisoner a '1', he keeps transmitting '1' to any number of prisoners. they'll ALL transmit 2

user61230

hmm

Danikov

the warden could grow that until half n are saying half n

log n, even

or cultivate it so only one is saying half n

or anything inbetween

user61230

if you receive a number equal to your own, add 1.

user61230

7:31 AM

ah, crap, that's the stop condition

Danikov

yeah, you can get deadends

you should get to a point where they all converge on the same number, which is n or some factor of it

maybe n^2

user61230

hmm, we're trying to make it so that each person adds to the total once and only once

user61230

and that someone always knows the total

Danikov

well, when you get two people who know a number, that means two additions

so when they (finally) collide, a subtraction is needed

here's the fundamental problem, though

when you recieve number n, how can you be sure that's the size of the population? how do you verify?

user61230

oh, I got it

Danikov

7:34 AM

you could always have a 'token' bit

user61230

totally got it

Danikov

but the warden can force that to loop between you and another prisoner

user61230

Person at the top holds the highest number $m$

user61230

If they broadcast to a person who hasn't seen a number, the steps continue

user61230

But there are a known number of people who have already seen a number: $m-1$

user61230

7:36 AM

so the $m-1$th person, on the $m$th night, starts broadcasting $m$

Danikov

so how do you detect when m = n?

user61230

when $m^2$ nights pass, the current number must be the answer

Danikov

incorrect

let's suppose I think m is the answer and I send it out for verficiation

what stops the warden, knowing m is... 100m^2 bigger, faking the result of m?

user61230

not sure I understand

Danikov

he can grab a desired value of m propagating deep in the ring and then feed it to you to give the illusion

user61230

7:39 AM

no value is higher than $m$ until $m$ is broadcast to someone who hasn't added one to the number yet

Danikov

what I'm saying is there's always an n^2 bigger than m^2

so you can only ever say with confidence that n is at least m

the m that you test with forms a lower bound

user61230

hmm

Danikov

there is a bound at which, yes, the warden is forced to feed you m

when m is close to n

user61230

I see what you're saying

Danikov

but when is very distant, he can give that illusion

user61230

7:42 AM

damn, this puzzle is fun

Danikov

so, yeah

it seems the warden strategy to beat is him trying to give you the illusion you have found m prematurely

given an unbounded n that may be massively larger than candidate m

so, to turn things on their heads...

not only must we find a way to count to n

we must find a way to signal unambiguously that we're not done counting to n until we are

user61230

wait, if everyone broadcasts the highest number that they heard, shouldn't it be possible to determine based on the number of nights exactly how many people broadcast it?

user61230

it's not possible to broadcast $m$ before the $m$th night without multiple people broadcasting the same number

Danikov

it's not possible to broadcast more than m unless you feed one into another...

but then the question is, do they start broadcasting that new number?

what stops the warden taking two prisoners and feeding them back and forth into each other to grow repeatedly?

and how do we signal that all prisoners are exhausted

no, it's impossible

it's impossible to disprove that there are unvisited prisoners

prove^

either or

it's like the set of all sets, problem

any set of inputs/results we can see are potentially the result of a superset of which we are a subset of

gonna have a shower/shower thinking :D

user61230

grah, this puzzle

user61230

7:54 AM

@Mike Do you enjoy my struggle?

user61230

room topic changed to The Circular Prison: For discussing the Circular prison problem (puzzling.stackexchange.com/q/16168), including clarifications, possible strategies, etc. (no tags)

Transcript for