Cap problem (Revisited)

[smart_coder]

There are 100 prisioners standing in a queue. Noone can look behind or on top of their head. Means everyone is looking in one direction i.e. in front.
A prisoner can c d color of the caps of all d prisoners standing in front of him.
Now there is an executer who tells them dat he will put caps on their heads. He told dem dat dere wud be only two colors...Black or White...but didnt tell dat how many wud be black or white. Means dere can be any combination of black and white caps. He told dem he will start frm the end of the queue and ask the color of the cap that prisoner is wearing. If he answers correctly he will spare him and if he answers wrong he will kill him and den he will move forward and ask the same question to the prisoner standing in front of previous prisoner. Dis way the executer will move forward in queue and ask the question to every prisoner.
Before all this happend he told them that they can plan any strategy among demselves and try to save as many prisoner as dey can among demselves!!

[Manojks]

The prisoner who is standing at the end can save all other 99 lives by giving his life.

The answer he should say is the colour of the 99th prisoners cap...
Then the answer for 99th prisoner should be clue for 98th prisoner to find his cap...
For example: 99th prisoner is wearing Black cap(100th tells him the colour of the cap) then if 98 prisoner is wearing white cap then the answer for 99th prisoner should be "I'm not wearing White colour cap". Suppose 98th prisoner is wearing Black cap then the answer from 99th prisoner should be "I'm wearing Black cap" and so on.

If the 100th prisoner was lucky then his answer may be correct so we can 100 prisoner sometimes...

[smart_coder]

but prisoner are allowed to answer in one word!! black or white!!

[vmshenoy]

min 50 can b saved.Remaining 50 's life depends on their luck!

bye

[Manojks]

Hey if this is the case then for sure 50 can escape(if they co-ordinate) and another 50 if they are lucky then their answer may be correct... Like wat shenoy said... If any other answer then tell me...

[vmshenoy]

verify it smart coder

[smart_coder]

Correct Solution:
This is the way u can save 99 prisoners:
Prisoners agree that if the number of black hats that the back prisoner can see is even, that prisoner will say "black ". If they add up to an odd number, they will say "white". This way number 99 can look ahead and count the black hats. If they add up to an even number and number 100 said "black ", then 99 must be wearing a white hat. If they add up to an even number and number 100 said "white", signalling an odd number of black hats, number 99 must also be wearing a black hat. Number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98's head.
Sample:
100 99 98 97 96 95 94 ... Facing ->
--b--w- w--b-w- b--w-- ... -> 45 b and 48 w

this shows #100 wearing a black hat, 99 a white, 98 a white, 97 a black , 96 a white, 95 a black , 94 a white and 45 black hats - 48 whitehats on the people in front of them. 100 counts up the black hats: 47 total. So 100 says "white". The executer kills 100. 99 counts up the black hats in front: 47. 100 said white, so 100 saw an odd number. 99 sees an odd number, so 99 says "white" and lives. 98 had counted 47 black hats, and 99 didn't say "black " so thats still the total. 98 says "white". 97 counts up and finds 46 black hats. 99 and 98 didn't say "black ", so his count is missing a black hat (its on his head, he realizes). He says "black ". 96 heard the "black " and now knows that there are an even number of "black " hats in front of 95. 96 sees 46, so he knows he has a "white" hat. Etc... Even if the assassin knows the plan, she can't thwart it. Executer hears the plan, but he still has to put the hats on their heads. The plan doesn't rely on any ordering of the hats, so the worst the assassin can do is to make sure #100 gets killed and thats the worst damage he can do.

[vmshenoy]

hi smart coder

I am reducing your problem to 10 persons!(for simplicity).
( I may be wrong, or missing some point, and if it so, do tell me!)
I think you have got something wrong!

1--- B,
2---W
3---B
4---B
5---W

6---W

7---B

8---B

9.... B

10...W


Now , 10th person sees even number of blacks in front of him says "BLACK" and gets killed.

9th person counts black caps in front of him,sees its odd i.e 5 and the person behind him(10th) told black, so 9 th person realizes that he is wearing black!

So 9th person tells :black (you theory works till here)

now 8th person counts, he sees 4 black caps in front of him. Even the 9th person told black(which meant 9th person saw even number of black caps), so 8th person who also sees even number of black caps,will think that he is wearing white.He will tell white and get killed!


now 7 th person heard 8th saying white, (i.e odd blacks).Even 7th sees odd blacks he too assumes he is wearing white. He too gets killed.

I hope you are getting me!

bye

[smart_coder]

good shenoy...u raised a good point!!
i was trying for ur solution and found sumthng..wud like to share!!

10th guy wud say black and gets killed
9th guy wud say black as he can odd number of caps in front of him.
8th guy knows 9th guy's answer wud be modified answer(coz he wants to save himself)
So wt 8th guy wud think!!
Every prisoner in front of 8th guy ( including himself) wud keep a count of how many prisoner hve called black

8th will hear 2 blacks(from 10th and from 9th).He himself can c even number of black caps. So he will think that there are even black calls from behind(9th is wearing a black which means odd blacks caps are left in front of 9th prisoner) and even number of black caps in his front...so he must be wearing a black cap!!!

other prisoners will also apply the same logic!!

[vmshenoy]

hi smart

this answer seems to be more satisfying one. but i will try out various combinations.

anyway it was good puzzle.
bye

[Manojks]

Yeah good logic... If there is no restriction like the answer should be single word then my answer will be more strategic than logic...

Thanks
Manoj

[smart_coder]

plz do so...dis will help me to bring out more perfect solutions!!

[vmshenoy]

hi smart coder

To make this puzzle more realistic, i think you should accept the asnwer of Manoj(in his first post).You should remove the constraint of "one word".
Then it seems more realistic.
Your answer too, i think fits here but doesnot seems to be too realistic.Anyway this was my suggestion!answer is upto you, afterall its your puzzle!


bye

[smart_coder]

Then there cud be many solutions... like prisoners can vary the pitch of their voice while answering!!!

[vmshenoy]

iam not getting you??
Please explain what u want to say smart!

bye

[smart_coder]

like prisoners can make codes. like they can decide dat if the color of hat in front of dem i same as d color of their own cap then they wud say loudly otherwise dey wud say slowly!

[Manojks]

If u want to assume the pitch of the prisoner then all the prisoner voice amplitude and frequency should be same that wat u assumed i think... If some one got cold then everything is gone(jus joking)... Why u prefer assumption... What i told is my answer is the easiest solution... And in the question u mentioned to plan a strategy not logic..,

Thanks
Manoj

[smart_coder]

wherez d logic?? I am planning a startegy!!!
i didnt said ur strategy was wrong but it wholly depend on executer dat he will allow dem to answer in a sentence rather in a word!!