A subtle puzzle... - Tilted Forum Project Discussion Community

KnifeMissile · 03-19-2004, 05:55 PM

You're a kid and you've been sent to math camp as punishment from your parents for getting poor grades.

Now, this camp is trying to foster problem solving skills so, to motivate you, they give you this problem to solve.

You're in a meeting with 9 other kids and a card that's white on one side and black on the other. You're told that, during your stay at camp, you'll be playing a game. Every day, one of you will be picked at random to come back to this room where you can flip the card over, if you want to. You will also be given a chance to declare that everyone has visited this room during the game, at least, once. If you are correct, you can all go home immediately! If you guess incorrectly, your parents will send you back to camp for another 12 years! So, you definitely don't want to guess wrong...

So, how will you kids plan your strategy? Remember, you will be picked at random, so some kids may visit the room several times before another's first visit. You're all staying at different camp grounds so, after this meeting, the only communication between you kids will be the flipping (or non-flipping) of this card...

rsl12 · 03-20-2004, 03:51 AM

I assume you can't choose to put the card on different spots on the table or write anything on it or chip it or rotate it...

this is an interesting problem too. This is the best solution I could think of so far:

Before anyone starts, the card shows black. It's decided that, for the first 9 days, the only person who wil flip the card to white will be the first person to go to the room twice. If no-one goes to the room twice in 9 days, then the 9th person, seeing the card is black, can immediately declare that it's everyone's been in the room. Otherwise, after 9 days, the 9 people can be divided into 4 groups: the ones that, the first time they came into the room, saw that the card was black; those that saw it was white the first time they came in; the person who flipped the card from black to white, and those who never got to the room in the 1st 9 days. The person who flipped the card will be the one who collects information from the others. When he flips the card on Day X (i'll assume it's a boys camp), he knows that at least X-1 people (the people who saw black, including himself) will have entered the room by day 9. The people who saw black have nothing else to do--they've already been counted by the information gatherer. The other people (those who saw white or didn't enter the room at all) need to be counted now. Starting with the person who enters on Day 9, here's the procedure:

If those who haven't been counted see that the card is white, they flip it to black. Once they flip it one time, any subsequent time they enter the room they do nothing, no matter what they see.

Those who have been counted never do anything.

The information gatherer flips the card to white whenever he sees that it is black.

The information gatherer will count the number of times he sees the card is black after day 9. If he sees the card is black 9-(x-1) days, then he knows that everyone has been in the room!

But this is potentially a LONG procedure--if camp is only 3 months, I think you'd be lucky if you cut your time in camp by half. I will try to think of a better solution.

mulletJeb · 03-21-2004, 05:47 PM

can you trust the other kids to cooperate?

mulletJeb · 03-21-2004, 05:48 PM

::edit:: nm.

ChickenNinja · 03-21-2004, 09:08 PM

See what you do, is you give every kid in the room the first day a black eye on their left eye, then the next day you give every kid in the room a black eye on their right eye. Then the next day you mark everybody on the nose, maybe with the card, since that's how you're supposed to communicate. Continue this, marking everyone in the room in one way every day, on any day where everyone in the room has the same mark somewhere, you win!

So it's violent. :P

kutulu · 03-22-2004, 09:02 AM

You're supposed to communicate with the kids via the card. I see no reason why you can't use the placement of the card as a means of communication. If so, just pick 4 spots in the room to put the card in. Everyone flips the card one time.
If the card is white first, the first visitor flips it to black. The next unique visitor makes it white again and moves it to the second position. When somone sees the card on the black side in the 4th position, he knows that everyone has been there.

If you can't use the placement of the card, I'd go with rsl12's info gatherer approach.

KnifeMissile · 03-22-2004, 12:36 PM

I think rsl12 is the only person who understands the question.

No, you may not move the card as a form of communication. The idea is that there is only one bit of information that can be transfered at a time. You can assume the camp counsellors (or whatever they're called) will always centre the card on the table after you've flipped it (for neatness)...

ChickenNinja, perhaps it's pointless to say this but your scheme is both violent and useless. You still can't solve the problem using your "solution" but, at least, you'll have a bunch of kids with black eyes, if that's your cup of tea...

Quote:

Originally posted by rsl12
When he flips the card on Day X (i'll assume it's a boys camp), he knows that at least X-1 people (the people who saw black, including himself) will have entered the room by day 9. The people who saw black have nothing else to do--they've already been counted by the information gatherer. The other people (those who saw white or didn't enter the room at all) need to be counted now. Starting with the person who enters on Day 9, here's the procedure:

...

The information gatherer will count the number of times he sees the card is black after day 9. If he sees the card is black 9-(x-1) days, then he knows that everyone has been in the room!

I don't understand the significance of day 9 (not to mention that there are ten kids, but that's arbitrary and unimportant). Suppose the the first kid to see the room twice is on the third day. I'm confused about how to proceed using your algorithm.

Other than that, it sounds like you understand the problem and, in fact, are on your way to one of the more efficient methods of doing so. There are two others, more effecient, but neither are terribly obvious...

rsl12 · 03-22-2004, 01:08 PM

whoops, read the problem wrong. change all references from day 9 to day 10.

The idea of the 1st part of my algorithm is to take advantage of the fact that you know that only one person will see the card on each day. If the a kid comes back on the 3rd day, you don't get much benefit from the plan. Then that kid knows that can really only count on 2 kids (him and another) and has to go through the 2nd part of the algorithm for 8 other kids. BUT if a kid doesn't get repeated until day 5 or so, then he's already got 4 kids counted (including himself) and needs to go through the 2nd part for 6 of the kids.

To clarify with an example: Let's call them kids 1-10.

1st day. Kid 1 (black)
D2: K2 (black)
D3: K3 (black)
D4: K2 (white, knows that 3 kids, including himself, have entered)
D5: K4 (white)
D6: K1 (white)
D7: K5 (white)
D8: K5 (white)
D9: K2 (white)
D10: K4 (black, so that next time K2 enters, he knows that at least 4 kids have entered. It was necessary to establish a day when you switch to the 2nd algorithm, because if you start immediately after Day 4, the card gets flipped to black on Day 5 by K4, and on Day 6, K1 might think he's the 1st person to enter twice and is therefore the information gatherer.)
From here on out, you continue with the 2nd part of the algorithm. You could solve the problem with JUST the 2nd part of the algorithm, but, on average, you get a more efficient answer by adding the 1st part. Still trying to think of other solutions.

EDIT: also, like I said, the 1st part of the algorithm takes advantage of the fact that you know only 1 kid is entering per day, so you can count kids entering by counting the days. If the time interval between which kids are entering is unknown, then that 1st part of the algorithm is useless. ALSO: it might be more efficient, on average, to use a cutoff day other than Day 10. Using Day 10 as the cutoff allows the possibility of getting out of camp as early as Day 10, but if you use something like Day 5 or Day 6 it might be more efficient on average, even though you would never get out after 10 days. When using Day 5 as the cutoff, then if the kid entering on Day 5 sees that the card is black, he flips it to white even if it's his first time entering and becomes the information gatherer (and knows that 5 kids have entered the room as of Day 5 if it's his 1st time, or that 4 kids have entered if it's his 2nd time).

2nd EDIT: I guess this also assumes that all the kids know that the 1st day that a kid will enter the room is June 1st, or something like that, so that they can count days.

rsl12 · 03-24-2004, 04:26 AM

knifemissile, i give up! what are the other solutions?

Yakk · 03-24-2004, 08:22 AM

{deleted by me}

shakran · 03-24-2004, 12:37 PM

hmmm. This sounds like the old barmoeter question:
http://wearcam.org/barometer.html

Namely, there are better ways to solve it than the way that the jerks who made the problem want you to. Were I in that camp, I'd just ask each kid if he'd been in the room. The threat of 12 years of math camp would keep them honest. Once all of them said yes, I'd declare and we'd go home.

kutulu · 03-24-2004, 01:16 PM

In my first day of Process Design class my professor had that question. He had about two pages of answers for it. One of my favorites was to drop it off the side of the building and measure the time that it took to reach the ground.

Kadath · 03-24-2004, 02:06 PM

Quote:

Originally posted by shakran
hmmm. This sounds like the old barmoeter question:
http://wearcam.org/barometer.html

Namely, there are better ways to solve it than the way that the jerks who made the problem want you to. Were I in that camp, I'd just ask each kid if he'd been in the room. The threat of 12 years of math camp would keep them honest. Once all of them said yes, I'd declare and we'd go home.

Quote:

You're all staying at different camp grounds so, after this meeting, the only communication between you kids will be the flipping (or non-flipping) of this card...

Shpoop · 03-24-2004, 04:45 PM

well ive heard a riddle like this before, but for some reason i cant remember the answer, so i made up a new one... would this work? they start all 9 black up... the person who sees all black is told to flip them all over, the person who sees all white is told to flip 8 over, the person who sees 8 black is told to flip 7 over...etc... by following that logic, the person who sees 3 white (i think) would know that he is teh final person

SirGoreaxe · 03-24-2004, 05:46 PM

One person would be the information gatherer just like RSl12 said, when some one goes into the room if it is there first time or they haven't fliped the card up yet and the card is black then they flip the card to white, else they leave it alone, then the information gatherer when he goes in if he sees white then he turns it over to black and it goes on when the information gatherer counts 9 whites then everyone has been in there.

I know that would take forever but it is simple and no one would be able to get confused to wether or not they should flip the card or not.

rsl12 · 03-25-2004, 11:28 AM

shakran, the sentiment of coming up with creative solutions is wonderful. if you can think of one for this problem, i'd love to hear it.

Ryan · 03-25-2004, 11:51 AM

You rip the card into pieces, on your first visit to the room you take a riped piece. Once all of the ripped pieces of card are gone you can assume everyone has been in the room

losthellhound · 03-25-2004, 04:45 PM

I understand the question, but I cant solve it past a certain point. Im going to give it to my best Math student at UofWaterloo tonight at WIlliams and let him "at it"

losthellhound · 03-25-2004, 07:17 PM

Alright here is a solution.. Rock solid, but it will take awhile...

First, assign every kid a number and make sure they know thier number.. between 1 and 10.

- child1 is assigned to any day ending in 1. (Includes 1, 11, 21, 31 ...)
- subsequently all other children are assigned the days ending in thier number child2 gets 2, 12, 22 etc etc
- card starts black
- If child1 comes in on any day ending in 1, he flips the card from black to white
- If child2 comes in on his assigned day and sees the card white, he knows that child1 has been in the room the day before
- If any child enters the room on a day that they are not assigned to, and the card is white, they flip the card to black or leave it black
- Any child except for child1 who enters the room on thier assigned day and sees the card black, they leave it black
- Until such time as they come in and see the card is white on thier assigned day, from that point on they leave the card white, or flip it white on any assigned day after that...

- so... for example (days are arbitrary)

day 31 - child1 comes in and flips it white
32 - child2 comes in sees that it is white, now knows that child1 has been in the room and from then on will ensure they leave the card white or flips the card white on any day that ends in 2
..
..
..
as an example:
day 72 - child2, knowing for the last few months that child1 has visited the room, leaves the card white, or flips it white
day 73 - child3 sees the card white and knows from now on that both child1 and child2 have been in the room and from that point on leaves the card white or flips the card white on any of his assigned days.. Before this point, child3, not having proof of child 2 and 1, would have been leaving the card black or flipping to black..

so.. fast forward to day 2000 child10 enters the room. (he's pissed, his parents have abandoned him to the evil dictators of the math camp) sees the card white.. he knows that child9 was in the day before, and has proof that all other children have visited the room.. He then shoves the card down the counsellors throat and sues his parents..

BUT.. he gets to go home..

How's that Knifemissile?

KnifeMissile · 03-25-2004, 10:59 PM

Yeah, that was my first solution. When I mentioned this to a colleague of mine, they suggested an optimisation where you flip the card white, not only on your day but, on the days of the kids you already know have gone through. This will propogate the information faster...

For all of you who are looking for a more in-depth treatise of this problem, check out this PDF file of a problem with a hundred prisoners...

EDIT: Damnit, I forgot to double-check my link. It's been corrected now...

dimbulb · 03-26-2004, 08:19 AM

Corrected link
http://www.ocf.berkeley.edu/~wwu/pap...sLightBulb.pdf

rsl12 · 03-26-2004, 10:26 AM

btw knifemissile--my exact solution is in that document...Section 2.2. I knew there had to be a way to get everybody to be a counter, but couldn't figure it out. Thanks for the very interesting puzzel...

Yakk · 03-26-2004, 11:16 AM

The best part about the puzzle is the first reaction, which is "no way you can do that! You have 1 bit." =)

Fun variants: (at least one isn't possible)
The prisoners are in solitary, and have no clocks. They don't know what day it is when they are brought to the room.

Every prisoner is given a number. Someone has to report the sum of all the numbers (or, roughly equivilently, list all of the numbers, if you can bound each.)

Every prisoner has to say "I know everyone has been in the room" before anyone is let free.

Every prisoner has to say "I know everyone has been in the room" before everyone is let free, but once you say it, you are moved to another cell block.

All prisoners have to say "I know everyone has been in the room" at once.

The warden listens in. Based off your algorithm, he can change which prisoner goes in when. However, every prisoner will visit an infinite number of times in an infinite period of time.

losthellhound · 03-26-2004, 02:06 PM

Quote:

The warden listens in. Based off your algorithm, he can change which prisoner goes in when. However, every prisoner will visit an infinite number of times in an infinite period of time.

My solution works for this

rsl12 · 03-26-2004, 07:10 PM

losthellhound: not really, if he systematically sends people in this order:

1, 3, 2, 4, 5, 6, 7, 8...99, 100, 1, 3, 2, 4, 5, etc, etc, you will never get out.

on the other hand, MY solution ought to work.

shakran · 03-26-2004, 08:28 PM

Quote:

Originally posted by rsl12
shakran, the sentiment of coming up with creative solutions is wonderful. if you can think of one for this problem, i'd love to hear it.

d'oh. I should really learn to read one of these days

03-19-2004, 05:55 PM	#1 (permalink)
KnifeMissile Location: Waterloo, Ontario	A subtle puzzle... You're a kid and you've been sent to math camp as punishment from your parents for getting poor grades. Now, this camp is trying to foster problem solving skills so, to motivate you, they give you this problem to solve. You're in a meeting with 9 other kids and a card that's white on one side and black on the other. You're told that, during your stay at camp, you'll be playing a game. Every day, one of you will be picked at random to come back to this room where you can flip the card over, if you want to. You will also be given a chance to declare that everyone has visited this room during the game, at least, once. If you are correct, you can all go home immediately! If you guess incorrectly, your parents will send you back to camp for another 12 years! So, you definitely don't want to guess wrong... So, how will you kids plan your strategy? Remember, you will be picked at random, so some kids may visit the room several times before another's first visit. You're all staying at different camp grounds so, after this meeting, the only communication between you kids will be the flipping (or non-flipping) of this card...

03-20-2004, 03:51 AM	#2 (permalink)
rsl12 On the lam Location: northern va	I assume you can't choose to put the card on different spots on the table or write anything on it or chip it or rotate it... this is an interesting problem too. This is the best solution I could think of so far: Before anyone starts, the card shows black. It's decided that, for the first 9 days, the only person who wil flip the card to white will be the first person to go to the room twice. If no-one goes to the room twice in 9 days, then the 9th person, seeing the card is black, can immediately declare that it's everyone's been in the room. Otherwise, after 9 days, the 9 people can be divided into 4 groups: the ones that, the first time they came into the room, saw that the card was black; those that saw it was white the first time they came in; the person who flipped the card from black to white, and those who never got to the room in the 1st 9 days. The person who flipped the card will be the one who collects information from the others. When he flips the card on Day X (i'll assume it's a boys camp), he knows that at least X-1 people (the people who saw black, including himself) will have entered the room by day 9. The people who saw black have nothing else to do--they've already been counted by the information gatherer. The other people (those who saw white or didn't enter the room at all) need to be counted now. Starting with the person who enters on Day 9, here's the procedure: If those who haven't been counted see that the card is white, they flip it to black. Once they flip it one time, any subsequent time they enter the room they do nothing, no matter what they see. Those who have been counted never do anything. The information gatherer flips the card to white whenever he sees that it is black. The information gatherer will count the number of times he sees the card is black after day 9. If he sees the card is black 9-(x-1) days, then he knows that everyone has been in the room! But this is potentially a LONG procedure--if camp is only 3 months, I think you'd be lucky if you cut your time in camp by half. I will try to think of a better solution. __________________ oh baby oh baby, i like gravy. Last edited by rsl12; 03-20-2004 at 03:56 AM..

03-21-2004, 09:08 PM	#5 (permalink)
ChickenNinja Crazy	See what you do, is you give every kid in the room the first day a black eye on their left eye, then the next day you give every kid in the room a black eye on their right eye. Then the next day you mark everybody on the nose, maybe with the card, since that's how you're supposed to communicate. Continue this, marking everyone in the room in one way every day, on any day where everyone in the room has the same mark somewhere, you win! So it's violent. :P __________________ Someday someone may kill you with your own gun, but they should have to beat you to death with it because it is empty.

03-22-2004, 01:08 PM	#8 (permalink)
rsl12 On the lam Location: northern va	whoops, read the problem wrong. change all references from day 9 to day 10. The idea of the 1st part of my algorithm is to take advantage of the fact that you know that only one person will see the card on each day. If the a kid comes back on the 3rd day, you don't get much benefit from the plan. Then that kid knows that can really only count on 2 kids (him and another) and has to go through the 2nd part of the algorithm for 8 other kids. BUT if a kid doesn't get repeated until day 5 or so, then he's already got 4 kids counted (including himself) and needs to go through the 2nd part for 6 of the kids. To clarify with an example: Let's call them kids 1-10. 1st day. Kid 1 (black) D2: K2 (black) D3: K3 (black) D4: K2 (white, knows that 3 kids, including himself, have entered) D5: K4 (white) D6: K1 (white) D7: K5 (white) D8: K5 (white) D9: K2 (white) D10: K4 (black, so that next time K2 enters, he knows that at least 4 kids have entered. It was necessary to establish a day when you switch to the 2nd algorithm, because if you start immediately after Day 4, the card gets flipped to black on Day 5 by K4, and on Day 6, K1 might think he's the 1st person to enter twice and is therefore the information gatherer.) From here on out, you continue with the 2nd part of the algorithm. You could solve the problem with JUST the 2nd part of the algorithm, but, on average, you get a more efficient answer by adding the 1st part. Still trying to think of other solutions. EDIT: also, like I said, the 1st part of the algorithm takes advantage of the fact that you know only 1 kid is entering per day, so you can count kids entering by counting the days. If the time interval between which kids are entering is unknown, then that 1st part of the algorithm is useless. ALSO: it might be more efficient, on average, to use a cutoff day other than Day 10. Using Day 10 as the cutoff allows the possibility of getting out of camp as early as Day 10, but if you use something like Day 5 or Day 6 it might be more efficient on average, even though you would never get out after 10 days. When using Day 5 as the cutoff, then if the kid entering on Day 5 sees that the card is black, he flips it to white even if it's his first time entering and becomes the information gatherer (and knows that 5 kids have entered the room as of Day 5 if it's his 1st time, or that 4 kids have entered if it's his 2nd time). 2nd EDIT: I guess this also assumes that all the kids know that the 1st day that a kid will enter the room is June 1st, or something like that, so that they can count days. __________________ oh baby oh baby, i like gravy. Last edited by rsl12; 03-22-2004 at 01:22 PM..

03-24-2004, 04:26 AM	#9 (permalink)
rsl12 On the lam Location: northern va	knifemissile, i give up! what are the other solutions? __________________ oh baby oh baby, i like gravy.

03-21-2004, 05:47 PM	#3 (permalink)
mulletJeb Insane	can you trust the other kids to cooperate?

03-21-2004, 05:48 PM	#4 (permalink)
mulletJeb Insane	::edit:: nm.

03-22-2004, 09:02 AM	#6 (permalink)
kutulu Junkie	You're supposed to communicate with the kids via the card. I see no reason why you can't use the placement of the card as a means of communication. If so, just pick 4 spots in the room to put the card in. Everyone flips the card one time. If the card is white first, the first visitor flips it to black. The next unique visitor makes it white again and moves it to the second position. When somone sees the card on the black side in the 4th position, he knows that everyone has been there. If you can't use the placement of the card, I'd go with rsl12's info gatherer approach.

03-24-2004, 08:22 AM	#10 (permalink)
Yakk Wehret Den Anfängen! Location: Ontario, Canada	{deleted by me} __________________ Last edited by JHVH : 10-29-4004 BC at 09:00 PM. Reason: Time for a rest. Last edited by Yakk; 03-24-2004 at 08:28 AM..

03-24-2004, 12:37 PM	#11 (permalink)
shakran Tone.	hmmm. This sounds like the old barmoeter question: http://wearcam.org/barometer.html Namely, there are better ways to solve it than the way that the jerks who made the problem want you to. Were I in that camp, I'd just ask each kid if he'd been in the room. The threat of 12 years of math camp would keep them honest. Once all of them said yes, I'd declare and we'd go home.

03-24-2004, 01:16 PM	#12 (permalink)
kutulu Junkie	In my first day of Process Design class my professor had that question. He had about two pages of answers for it. One of my favorites was to drop it off the side of the building and measure the time that it took to reach the ground.

03-24-2004, 04:45 PM	#14 (permalink)
Shpoop Curious Location: NJ (but just for college)	well ive heard a riddle like this before, but for some reason i cant remember the answer, so i made up a new one... would this work? they start all 9 black up... the person who sees all black is told to flip them all over, the person who sees all white is told to flip 8 over, the person who sees 8 black is told to flip 7 over...etc... by following that logic, the person who sees 3 white (i think) would know that he is teh final person

03-24-2004, 05:46 PM	#15 (permalink)
SirGoreaxe Tilted Location: Bremerton, WA	One person would be the information gatherer just like RSl12 said, when some one goes into the room if it is there first time or they haven't fliped the card up yet and the card is black then they flip the card to white, else they leave it alone, then the information gatherer when he goes in if he sees white then he turns it over to black and it goes on when the information gatherer counts 9 whites then everyone has been in there. I know that would take forever but it is simple and no one would be able to get confused to wether or not they should flip the card or not. __________________ (;þ "You can't change what has happened, but you can make the best of it, and make better decisions from the past." (Unless there is a quick edit button.) Last edited by SirGoreaxe; 03-24-2004 at 05:49 PM..

03-25-2004, 11:28 AM	#16 (permalink)
rsl12 On the lam Location: northern va	shakran, the sentiment of coming up with creative solutions is wonderful. if you can think of one for this problem, i'd love to hear it. __________________ oh baby oh baby, i like gravy.

03-25-2004, 11:51 AM	#17 (permalink)
Ryan Crazy	You rip the card into pieces, on your first visit to the room you take a riped piece. Once all of the ripped pieces of card are gone you can assume everyone has been in the room

03-26-2004, 08:19 AM	#21 (permalink)
dimbulb Riiiiight........	Corrected link http://www.ocf.berkeley.edu/~wwu/pap...sLightBulb.pdf

03-25-2004, 04:45 PM	#18 (permalink)
losthellhound Thats MR. Muffin Face now Location: Everywhere work sends me	I understand the question, but I cant solve it past a certain point. Im going to give it to my best Math student at UofWaterloo tonight at WIlliams and let him "at it" __________________ "Life is possible only with illusions. And so, the question for the science of mental health must become an absolutely new and revolutionary one, yet one that reflects the essence of the human condition: On what level of illusion does one live?" -- Ernest Becker, The Denial of Death

03-25-2004, 07:17 PM	#19 (permalink)
losthellhound Thats MR. Muffin Face now Location: Everywhere work sends me	Alright here is a solution.. Rock solid, but it will take awhile... First, assign every kid a number and make sure they know thier number.. between 1 and 10. - child1 is assigned to any day ending in 1. (Includes 1, 11, 21, 31 ...) - subsequently all other children are assigned the days ending in thier number child2 gets 2, 12, 22 etc etc - card starts black - If child1 comes in on any day ending in 1, he flips the card from black to white - If child2 comes in on his assigned day and sees the card white, he knows that child1 has been in the room the day before - If any child enters the room on a day that they are not assigned to, and the card is white, they flip the card to black or leave it black - Any child except for child1 who enters the room on thier assigned day and sees the card black, they leave it black - Until such time as they come in and see the card is white on thier assigned day, from that point on they leave the card white, or flip it white on any assigned day after that... - so... for example (days are arbitrary) day 31 - child1 comes in and flips it white 32 - child2 comes in sees that it is white, now knows that child1 has been in the room and from then on will ensure they leave the card white or flips the card white on any day that ends in 2 .. .. .. as an example: day 72 - child2, knowing for the last few months that child1 has visited the room, leaves the card white, or flips it white day 73 - child3 sees the card white and knows from now on that both child1 and child2 have been in the room and from that point on leaves the card white or flips the card white on any of his assigned days.. Before this point, child3, not having proof of child 2 and 1, would have been leaving the card black or flipping to black.. so.. fast forward to day 2000 child10 enters the room. (he's pissed, his parents have abandoned him to the evil dictators of the math camp) sees the card white.. he knows that child9 was in the day before, and has proof that all other children have visited the room.. He then shoves the card down the counsellors throat and sues his parents.. BUT.. he gets to go home.. How's that Knifemissile? __________________ "Life is possible only with illusions. And so, the question for the science of mental health must become an absolutely new and revolutionary one, yet one that reflects the essence of the human condition: On what level of illusion does one live?" -- Ernest Becker, The Denial of Death

03-25-2004, 10:59 PM	#20 (permalink)
KnifeMissile Location: Waterloo, Ontario	Yeah, that was my first solution. When I mentioned this to a colleague of mine, they suggested an optimisation where you flip the card white, not only on your day but, on the days of the kids you already know have gone through. This will propogate the information faster... For all of you who are looking for a more in-depth treatise of this problem, check out this PDF file of a problem with a hundred prisoners... EDIT: Damnit, I forgot to double-check my link. It's been corrected now... Last edited by KnifeMissile; 03-26-2004 at 10:50 AM..

03-26-2004, 10:26 AM	#22 (permalink)
rsl12 On the lam Location: northern va	btw knifemissile--my exact solution is in that document...Section 2.2. I knew there had to be a way to get everybody to be a counter, but couldn't figure it out. Thanks for the very interesting puzzel... __________________ oh baby oh baby, i like gravy.

03-26-2004, 11:16 AM	#23 (permalink)
Yakk Wehret Den Anfängen! Location: Ontario, Canada	The best part about the puzzle is the first reaction, which is "no way you can do that! You have 1 bit." =) Fun variants: (at least one isn't possible) The prisoners are in solitary, and have no clocks. They don't know what day it is when they are brought to the room. Every prisoner is given a number. Someone has to report the sum of all the numbers (or, roughly equivilently, list all of the numbers, if you can bound each.) Every prisoner has to say "I know everyone has been in the room" before anyone is let free. Every prisoner has to say "I know everyone has been in the room" before everyone is let free, but once you say it, you are moved to another cell block. All prisoners have to say "I know everyone has been in the room" at once. The warden listens in. Based off your algorithm, he can change which prisoner goes in when. However, every prisoner will visit an infinite number of times in an infinite period of time. __________________ Last edited by JHVH : 10-29-4004 BC at 09:00 PM. Reason: Time for a rest.

03-26-2004, 07:10 PM	#25 (permalink)
rsl12 On the lam Location: northern va	losthellhound: not really, if he systematically sends people in this order: 1, 3, 2, 4, 5, 6, 7, 8...99, 100, 1, 3, 2, 4, 5, etc, etc, you will never get out. on the other hand, MY solution ought to work. __________________ oh baby oh baby, i like gravy.