A prison with an infinite number of cells

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
wraith
Posts: 103
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

A prison with an infinite number of cells

Postby wraith » Fri Jun 15, 2012 7:56 am UTC

I'm not sure if this is possible. A friend told me this problem, but I'm starting to believe he's got it wrong. Anyway.

You are the warden of a prison with an infinite number of cells. In each cell there are two prisoners with numbers #a and #b (in cell 6, the prisoners are 6a and 6b). Due to new regulations you need to redistribute the prisoners, so there will be one prisoner per cell.

You make a radio announcement to the guards (whose number is also infinite) telling them what to do.

What should the radio announcement be?

Example announcement: "Move each b-prisoner to cell n+1." - with this order, one prisoner will remain in cell 1 but there'll be two of them in the rest.

That "An" has been driving me nuts. -jr
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

User avatar
jobriath
Posts: 256
Joined: Wed Apr 04, 2007 2:11 pm UTC
Location: North of England

Re: An prison with an infinite number of cells

Postby jobriath » Fri Jun 15, 2012 8:20 am UTC

At last, one of these I can get!
Spoiler:
Hint: Put A's in even numbered cells and B's in odd-numbered cells.
Spoiler:
Rule for an A-prisoner in cell n: Put prisoner in cell 2n. Rule for a B-prisoner in cell n: Put prisoner in cell 2n-1. Assuming cells are numbered 1, 2, ..., this fills all cells; no A-prisoners share with A-prisoners; no B-prisoners with B-prisoners; and you know A's and B's can't share because they're in evens/odds.

Edit to add bonus sophomoric answer: The radio message should be boosted at intervals. Otherwise it'll never reach all the guards.

jonachin
Posts: 7
Joined: Thu Feb 02, 2012 3:01 am UTC

Re: An prison with an infinite number of cells

Postby jonachin » Sun Jun 17, 2012 5:49 am UTC

Spoiler:
assume some random cell as an origin, 0. therefore, there are cells +1, +2, +3, etc to the right of the origin. and cells -1, -2, and -3 to the left of the origin.

(can you see where I'm going with this?)

put all B prisoners in the (origin minus N)th cell and all A prisoners in the (origin plus N)th cell.

I think it's a more elegant solution to say: all B prisoners in the -nth cell, but that's semantically different than the above solution.

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: An prison with an infinite number of cells

Postby t1mm01994 » Sun Jun 17, 2012 10:47 am UTC

@Jona: Nope.
Spoiler:
From every random cell, there's only a finite number of sells on the lower end.

User avatar
SlyReaper
inflatable
Posts: 8015
Joined: Mon Dec 31, 2007 11:09 pm UTC
Location: Bristol, Old Blighty

Re: An prison with an infinite number of cells

Postby SlyReaper » Sun Jun 17, 2012 11:06 am UTC

Spoiler:
Any reason the obvious answer won't work? Move prisoner na to cell 2n, move prisoner nb to cell (2n-1)? Thus all a prisoners end up in a unique even numbered cell, all b prisoners end up in a unique odd numbered cell.
Image
What would Baron Harkonnen do?

jonachin
Posts: 7
Joined: Thu Feb 02, 2012 3:01 am UTC

Re: An prison with an infinite number of cells

Postby jonachin » Sun Jun 17, 2012 2:45 pm UTC

t1mm01994 wrote:@Jona: Nope.
Spoiler:
From every random cell, there's only a finite number of sells on the lower end.


I see your point.

I guess that
Spoiler:
I'm envisioning it as ... as a memory pointer in comp sci. $array[0] points to a bit of information (a cell) and $array[-1] also points to a bit of information (although you can't reliably insure its quality).

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: An prison with an infinite number of cells

Postby t1mm01994 » Sun Jun 17, 2012 4:04 pm UTC

@jona:
Spoiler:
There's a way to create that though, but you're going to have to think out a trick for that, first.. Which just might cause you to follow all the other solutions around here n.n

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: An prison with an infinite number of cells

Postby Gwydion » Sun Jun 17, 2012 9:05 pm UTC

jonachin wrote:
t1mm01994 wrote:@Jona: Nope.
Spoiler:
From every random cell, there's only a finite number of sells on the lower end.


I see your point.

I guess that
Spoiler:
I'm envisioning it as ... as a memory pointer in comp sci. $array[0] points to a bit of information (a cell) and $array[-1] also points to a bit of information (although you can't reliably insure its quality).
Regarding jona's proposed solution,
Spoiler:
I see it working one of two ways. Either a) there exist negative-numbered cells, which already contain prisoners, and you'll end up no better off. For demonstration, think about the two prisoners in cell k and the two prisoners in cell -k. Or b) there are no negative-numbered cells, and to discuss a cell (O-n) for arbitrarily large n, you'll need an origin that's infinitely far from the first cell.

Case c) in which there exist empty negative-numbered cells and two prisoners in the positive-numbered cells is a trivially solved infinite-prison scenario, which I bring up only because I've never uttered that phrase before and probably won't ever have the opportunity again.

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: An prison with an infinite number of cells

Postby lorb » Sun Jun 17, 2012 11:02 pm UTC

Spoiler:
We can do this more complicated (assuming we are allowed to have empty cells) Let p and q be any two different prime numbers. Assign prisoner a from cell n to cell p^n and prisoner b to cell q^n.
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

jonachin
Posts: 7
Joined: Thu Feb 02, 2012 3:01 am UTC

Re: An prison with an infinite number of cells

Postby jonachin » Mon Jun 18, 2012 6:10 am UTC

alright, how about something dead simple?

Spoiler:
prisoner A goes to cell 2n - 1, prisoner B to cell 2n

1 maps to 1 and 2
2 maps to 3 and 4
3 maps to 5 and 6
etc etc etc

madd0ct0r
Posts: 44
Joined: Fri Jun 15, 2012 3:13 am UTC

Re: An prison with an infinite number of cells

Postby madd0ct0r » Mon Jun 18, 2012 8:37 am UTC

do we need to work out the sequence of moving prisoners as well?

c4k3m4s73r
Posts: 2
Joined: Sat Jun 23, 2012 1:33 am UTC

Re: A prison with an infinite number of cells

Postby c4k3m4s73r » Sat Jun 23, 2012 1:45 am UTC

Im pretty sure it can't be done.
Spoiler:
If there are infinite cells but all cells already are holding two prisoners there isn't a place to move any prisoner to. It doesnt matter that the number of cells is infinite since each is already occupied by 2 inmates. the reason the solution nA->cell 2n and nB->cell 2n-1 doesnt work is because when you move prisoners from any one cell to start you end up with one prisoner in the cell you start with and 3 in the cell next door (because it is already occupied). the algorithm is breaks after one iteration. the only radio orders to give are to tell each guard to begin construction on an identical prison, hoping they don't build it complete with two prisoners per cell again or to tell them to build a wall down the center of each cell (and order your prison some new doors).

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: A prison with an infinite number of cells

Postby lorb » Mon Jun 25, 2012 8:35 am UTC

c4k3m4s73r wrote:Im pretty sure it can't be done.
Spoiler:
If there are infinite cells but all cells already are holding two prisoners there isn't a place to move any prisoner to. It doesnt matter that the number of cells is infinite since each is already occupied by 2 inmates. the reason the solution nA->cell 2n and nB->cell 2n-1 doesnt work is because when you move prisoners from any one cell to start you end up with one prisoner in the cell you start with and 3 in the cell next door (because it is already occupied). the algorithm is breaks after one iteration. the only radio orders to give are to tell each guard to begin construction on an identical prison, hoping they don't build it complete with two prisoners per cell again or to tell them to build a wall down the center of each cell (and order your prison some new doors).

I think you got something wrong:
Spoiler:
"nA->cell 2n and nB->cell 2n-1" puts the prisoner A from cell 1 into cell 2*1=2 and prisoner B from cell 1 into cell 2*1-1=1. At that point you have 1 prisoner in cell one and 3 in cell 2. But after that you put prisoner A from cell 2 into 2*2=4 and prisoner B from cell 2 into 2*2-1=3. Now you have just one prisoner in cells 1 and 2. If you continue this for infinity there will be only 1 pisoner in every cell.
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: A prison with an infinite number of cells

Postby Gwydion » Mon Jun 25, 2012 11:35 am UTC

Naturally, any process for reassigning rooms of an infinite number of prisoners will be tricky and lead to some unsatisfying answers in the short run, but look at it this way:
Spoiler:
Once you move prisoners from cell 1 (call this move 0), there will be an excess of prisoners in cell 2, as lorb points out. So you move both of them to cells 3&4. Now there are 3 prisoners in each of those cells, so you move the excess prisoners from 3&4 to cells 5-8, overfilling those. Now move n creates 2^n overfilled cells, which blows up to infinity quickly.

One might think this would be unsafe, but we have plenty of guards. Proof structure: If any given guard is able to look after an infinite number of prisoners, we only need one and he/she is sufficient. This is boring, so we'll require that each guard can only manage a finite number of prisoners (m). If there is a finite number of guards (n), and since each guard can only look after a finite number of prisoners, there is a "maximum" capacity for the prison (mxn) and even before the move, there would have been an infinite number of prisoners unguarded. The only way the prison could have ever been safe is with an infinite number of guards, making moving 2^n prisoners simultaneously a huge logistical problem but certainly no challenge to our staffing.

c4k3m4s73r
Posts: 2
Joined: Sat Jun 23, 2012 1:33 am UTC

Re: A prison with an infinite number of cells

Postby c4k3m4s73r » Mon Jun 25, 2012 10:38 pm UTC

you're correct lorb. I was too hasty. something in my mental execution of the scenario made me imagine
Spoiler:
prisoners piling up but they do not
.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: A prison with an infinite number of cells

Postby HonoreDB » Fri Jun 29, 2012 12:30 pm UTC

The obvious evil expansion of this:

Version 1:
You're responsible for infinitely many prisons, Prison 1, Prison 2, etc. Each Prison K has infinitely many cells, K-1, K-2, etc. each of which has one prisoner. You receive word that all but Prison 1 are to be closed down, and everyone must be relocated to Prison 1. Each prisoner must go to a cell, and each cell must have exactly one prisoner. You're patched in to all the PA systems at once. What do you say to the guards?

Version 2:
Same as Version 1, except there are a variable (but finite) number of prisoners in each cell and you're allowed to have empty cells after the transfer.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: A prison with an infinite number of cells

Postby douglasm » Fri Jun 29, 2012 1:34 pm UTC

HonoreDB wrote:The obvious evil expansion of this:

Version 1:
You're responsible for infinitely many prisons, Prison 1, Prison 2, etc. Each Prison K has infinitely many cells, K-1, K-2, etc. each of which has one prisoner. You receive word that all but Prison 1 are to be closed down, and everyone must be relocated to Prison 1. Each prisoner must go to a cell, and each cell must have exactly one prisoner. You're patched in to all the PA systems at once. What do you say to the guards?

Spoiler:
Move each prisoner in cell N from Prison K to cell (K+N-1)*(K+N-2)/2 + N in Prison 1.

Cell 1-1 stays put.
Cell 2-1 goes to 1-2
Cell 1-2 goes to 1-3
Cell 3-1 goes to 1-4
Cell 2-2 goes to 1-5
Cell 1-3 goes to 1-6
Cell 4-1 goes to 1-7
Cell 3-2 goes to 1-8
And so on.

This is essentially equivalent to the proof that the set of rational numbers is the same size as the set of integers.


HonoreDB wrote:Version 2:
Same as Version 1, except there are a variable (but finite) number of prisoners in each cell and you're allowed to have empty cells after the transfer.

Spoiler:
I assume that prisoners are required to be 1 per cell after the move. Otherwise, the solution to version 1 works here too.

Find the highest number of prisoners in any single cell, and allocate that many cells in Prison 1 for each pre-move cell. Use the same algorithm as in version 1, just with blocks of cells instead of single cells. Then in each block split up the prisoners 1 per cell.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: A prison with an infinite number of cells

Postby HonoreDB » Sat Jun 30, 2012 2:00 am UTC

Your solution to version 2 isn't the kind I intended, since it requires coordination on the part of the guards.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: A prison with an infinite number of cells

Postby douglasm » Sat Jun 30, 2012 4:58 am UTC

Altering it to remove the requirement of knowing the highest number of prisoners per cell, then:
Spoiler:
For calculation only, consider where people would end up if no one-per-cell requirement were being added and cell groups were kept together (this is just version 1). Then treat each cell as a whole prison, with each prisoner as a separate cell, and apply the version 1 solution again.

This can even handle infinite prisoners per cell and moving them to end up with only 1 per cell.

Jeff_UK
Posts: 67
Joined: Sat Nov 03, 2007 10:38 pm UTC

Re: A prison with an infinite number of cells

Postby Jeff_UK » Sat Jun 30, 2012 1:38 pm UTC

Spoiler:
Get all prisoners out of their cells. Get the prisoners to go back to the first empty cell they find.
"Please only print this post if you really need to"
...hmm....I wonder how much extra energy is required to generate that request...We need a cost/benefit analysis, STAT!

Giallo
Posts: 226
Joined: Sat Jan 01, 2011 11:31 pm UTC
Location: ETH, Zürich, Switzerland
Contact:

Re: A prison with an infinite number of cells

Postby Giallo » Sat Jun 30, 2012 10:35 pm UTC

Well, that's only Hilbert's hotel with name changed...
http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

Mike Rosoft
Posts: 63
Joined: Mon Jun 15, 2009 9:56 pm UTC
Location: Prague, Czech Republic

Re: A prison with an infinite number of cells

Postby Mike Rosoft » Sun Jul 01, 2012 7:15 pm UTC

Jeff_UK wrote:
Spoiler:
Get all prisoners out of their cells. Get the prisoners to go back to the first empty cell they find.


This is begging the question, i.e. assuming that a solution exists. (Since the sets you work with are countably infinite, the solution works - but you didn't prove that it's the case.)

Mike Rosoft
Posts: 63
Joined: Mon Jun 15, 2009 9:56 pm UTC
Location: Prague, Czech Republic

Re: A prison with an infinite number of cells

Postby Mike Rosoft » Sun Jul 01, 2012 7:39 pm UTC

There's a city (with an infinite population, of course) whose inhabitants enjoy organizing themselves in clubs: every possible finite set of citizens forms a club, and no two clubs are alike. The clubs are not named; it's been decided that each club should be named after one of the citizens. (No two clubs can be named after the same person.) Can this be done?

If so, then what if the restriction that no club can have an infinite membership were lifted? If every possible set of citizens, finite or infinite, formed a club, can they be named using the same rules as above?

Hint:
Spoiler:
A citizen is not required to be a member of the club which is named after him.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: A prison with an infinite number of cells

Postby jestingrabbit » Sun Jul 01, 2012 7:47 pm UTC

Mike Rosoft wrote:
Jeff_UK wrote:
Spoiler:
Get all prisoners out of their cells. Get the prisoners to go back to the first empty cell they find.


This is begging the question, i.e. assuming that a solution exists. (Since the sets you work with are countably infinite, the solution works - but you didn't prove that it's the case.)


And in fact, you could easily run out of cells, and be left with any number (including a countable infinity) of prisoners without a cell. It could even be such that the asymptotic density of the prisoners who end up with cells was 0 before the change.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: A prison with an infinite number of cells

Postby ConMan » Sun Jul 01, 2012 11:40 pm UTC

Mike Rosoft wrote:There's a city (with an infinite population, of course) whose inhabitants enjoy organizing themselves in clubs: every possible finite set of citizens forms a club, and no two clubs are alike. The clubs are not named; it's been decided that each club should be named after one of the citizens. (No two clubs can be named after the same person.) Can this be done?

If so, then what if the restriction that no club can have an infinite membership were lifted? If every possible set of citizens, finite or infinite, formed a club, can they be named using the same rules as above?

Hint:
Spoiler:
A citizen is not required to be a member of the club which is named after him.

Yes. No.

For the first question:
Spoiler:
The first question is asking whether the set of finite subsets of the natural numbers (or a set in bijection with it) can be put into bijection with the natural numbers, and it can - you could, for example, give everyone in the city a number, then define each club by the binary number formed from the bits of whether each person is in the club, then map that back to a person (the number of each person will correspond to the binary place, so that person number 1 has the least significant bit in the numbers). So, suppose Alex was 1, Bob was 2, Carter was 3 and Dean was 4. Then the first few clubs are:
{Alex} = ...0001 = "Alex"
{Bob} = ...0010 = "Bob"
{Alex, Bob} = ...0011 = "Carter"
{Carter} = ...0100 = "Dean"
{Alex, Carter} = ...0101 = "Edward"

The rule that clubs are finite means that any club must have a member with a largest corresponding number, hence ensuring that each club can be assigned a finite number.


For the second:
Spoiler:
Rather than generate a new diagonalisation argument, let's just use the numbering system I defined in the first part, but since we could be dealing with numbers of infinite length, let's flip them around - now our clubs look like this:
{Alex} = 0.1000...
{Bob} = 0.0100...
{Alex, Bob} = 0.1100...
{Carter} = 0.0010...

Since every possible set of binary digits will be represented by a club, the set of all clubs can be put into bijection with the continuum between 0 and 1, and hence is uncountably infinite and thus not matchable with the countably infinite population.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: A prison with an infinite number of cells

Postby lorb » Sun Jul 01, 2012 11:53 pm UTC

ConMan wrote:For the first question:
Spoiler:
The first question is asking whether the set of finite subsets of the natural numbers (or a set in bijection with it) can be put into bijection with the natural numbers, and it can - you could, for example, give everyone in the city a number, then define each club by the binary number formed from the bits of whether each person is in the club, then map that back to a person (the number of each person will correspond to the binary place, so that person number 1 has the least significant bit in the numbers). So, suppose Alex was 1, Bob was 2, Carter was 3 and Dean was 4. Then the first few clubs are:
{Alex} = ...0001 = "Alex"
{Bob} = ...0010 = "Bob"
{Alex, Bob} = ...0011 = "Carter"
{Carter} = ...0100 = "Dean"
{Alex, Carter} = ...0101 = "Edward"

The rule that clubs are finite means that any club must have a member with a largest corresponding number, hence ensuring that each club can be assigned a finite number.


What if the persons can't be well-ordered?
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: A prison with an infinite number of cells

Postby jestingrabbit » Mon Jul 02, 2012 12:02 am UTC

ConMan wrote:For the second:


It seems like you're assuming that the infinitude of the citizens is countable, rather than anything more troubling. There's a way to deal with the more general setup, and you arrive at the same conclusions.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: A prison with an infinite number of cells

Postby ConMan » Mon Jul 02, 2012 12:49 am UTC

jestingrabbit wrote:
ConMan wrote:For the second:


It seems like you're assuming that the infinitude of the citizens is countable, rather than anything more troubling. There's a way to deal with the more general setup, and you arrive at the same conclusions.

I admit that while my puny monkey brain is capable of imagining countably infinitely many people, it baulks a bit at uncountably many. However, let me see how far I can get with an arbitrarily infinite set of people.
Spoiler:
The questions still boil down to "Can set X be put into bijection with the set of all its finite subsets?" and "Can set X be put into bijection with its powerset P(X)?" The second is disprovable with diagonalisation, I think ...

Let's assume that every club has a name from someone in the population. Then I will form Club Z as follows: for every person P, if they are in the club that has their name, then they're not in Club Z. If they're not in the club of their name, then they are in Club Z. Club Z is a valid club, so it must share the name of someone in the population. But whoever that is, it *can't* be their club due to the way we defined it. Thus the naming system can't work. (I can never remember how the Axiom of Choice works enough to say for sure, but I suspect I've invoked it somewhere in there.)

Ok, now to tackle the first one. We're looking for a bijection between people and clubs. Actually, this sounds even more like it's going to invoke AoC, so I might have to go away and think about it (and brush up on my Axioms at the same time).
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

Mike Rosoft
Posts: 63
Joined: Mon Jun 15, 2009 9:56 pm UTC
Location: Prague, Czech Republic

Re: A prison with an infinite number of cells

Postby Mike Rosoft » Fri Jul 06, 2012 12:48 pm UTC

Spoiler:
The conclusion that there cannot be a one-to-one correspondence between a set and its powerset (set of all subsets) does not require the axiom of choice.

As for the second problem (let C be the set of citizens):
* Obviously, there are as many one-member clubs as citizens.
* Consider the set of two-member clubs. There are at most as many two-member clubs as the elements of C x C. The set C x C has the same cardinality as C. Hence, there are as many two-member clubs as citizens.
* Since there are as many two-member clubs as citizens, the same argument can be used to prove that there are as many three-member clubs as citizens. By induction, for every natural number N, N>0, the set of N-member clubs has the same cardinality as C.
* Now we have a countably infinite number of sets, each with the same cardinality as C. Once again, the cardinality of their union is the same as C.
* There's also one empty club, but adding an element to an infinite set does not change its cardinality.

None of the steps save for the first can be proven without the axiom of choice. (This includes the last step, I believe.)


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests