Save maximum prisoners

There are 64 prisoners who are to be executed the same day. The executioner didn't want to waste his whole day getting the electric chair set up and preferred to shoot them all. However, he thought it would be unfair to deviate from the procedure and just shoot them without giving them a second chance. So he thought of a plan.
He informed all the 64 prisoners that they would be made to stand in a line in such a way that each of the prisoners could view the heads of all the prisoners standing in front of him, and then the executioner would put one hat on each prisoner's head which would be either white or black in colour (The prisoners would not be able to see the colour of the hat on top of their own heads). Then each of the prisoners would be given a chance to shout out the colour of his own hat starting from the last prisoner (The prisoner who can see all the hats except his own). Whoever shouts out the wrong colour would be shot and the others let go.
The prisoners have quite a good unity and they want most of them to be saved. You have to help them device a strategy which if they follow would make the probability of saving all the prisoners highest!

Solutution to Random Pointer

Link to the Problem

Vandana gave a simple solution which was correct but it needed O(n) extra space and Anonymous got rid if that extra space and gave us an O(n) solution using constant space.
My solution is same as Anonymous'! Here it goes :

As Anonymous pointed out, the random pointer is a little too weak, so the idea is to use the next pointer to maintain correspondences between the old and the new (copy) list before assigning the random pointers for the new list!
Let the old list be
O1 --> O2 --> O3 --> O4 --> NULL
create new nodes and insert them in between the old nodes with old list's next pointing to the corresponding new node and the new node's next pointing to old's original next. So we get something like,
O1 --> N1 --> O2 --> N2 --> O3 --> N3 --> O4 --> N4 --> NULL
Also while creating the new nodes, copy the corresponding old node's data to the new node's data.
Now traverse through this list and assign current node's random pointer's next to the next node's random pointer.
Thus if O1->random was pointing to O3, then we get N1->random = O1->random->next = O3->next = N3;
Skip the alternate (new) nodes while doing this. When this traversal is done through the whole list, we have the new nodes having the exact structure as the old nodes. Hence, the only thing now left to be done is detaching the two lists, which can be easily done by storing old->next to a temporary pointer and then assigning old's next to old's next's next and similarly for the new nodes. Hence we get two lists
O1 --> O2 --> O3 --> O4 --> NULL and
N1 --> N2 --> N3 --> N4 --> NULL
with the random pointers also properly assigned!

Random Pointer

We've had enough of logic puzzles! Here goes a data structures problem:

You have a linked list of nodes with the following fields:

struct Node {
int data;
Node * next;
Node * random;
}

The random pointer here can point to any node in the list including itself.

Now given a pointer to such a list, your task is to create a similar copy! The structure of the links should remain the same.

To clarify, all the nodes in the list are linked through the next pointer;
Mind you, You may or may not reach all the nodes if you try to access random pointers.

Link to the Solution

Solution to Blue eyes

Link to the Problem

Manikandan's solution was almost correct and Yash correctly modified it!
Here's my solution:

In such type of problems always try decreasing the number of parameters (i.e. Use induction).

If there was only 1 blue eyed person, he would have left at the end of the first day itself as he doesn't see any other blue eyed person there (and he knows that there is at least one blue eyed person).

If there were 2 blue eyed people, then the first would see one other blue eyed person on the first day and vice versa and hence both won't leave on the first day (as they can't determine their own eye colour). However, on the second day they know that there are more than one blue eyed persons (if there was only one blue eyed person then he would have left the first day itself). And since the blue eyed persons see only one other blue eyed person, each of them themselves is the other blue eyed person creating confusion on the first day. So the two blue eyed persons know that their eye colour is blue on the second day and hence would leave at the end of that day.

Similarly, if there were 3 blue eyed people, these three blue eyed people would be confused for the first two days as they see 2 other blue eyed people not leaving the island, however on the third day they would know there is one more blue eyed person and it could be only be he himself (as they know that if there were only 2 blue eyed people, they would have left at the end of the 2nd day by above argument). So these three blue eyed people would leave at the end of the 3rd day.

By similar argument we can prove that if there are N blue eyed people, they would be confused till N-1 days but on the Nth day they would all come to know that their eye colour is blue! And hence all the N blue eyed people leave at the end of the Nth day.

Hence in this case all the 100 Blue eyed people leave on the 100th day and no one else leaves!

Blue Eyes

Two hundred and one perfect logicians with assorted eye colours are stuck in a deserted island. Of these, 100 have blue eyes, 100 have brown eyes and one has green eyes which however they don't know. These people can see everyone else (and hence know their eye colours) but they don't know their own eye colour (they don't even know the all colours present there)! Also, they cannot communicate with each other by any means. Every midnight a ship comes to the island and takes away only those people who know their own eye colour for sure at that point of time. The Guru (who happens to have green eyes) is allowed to speak one sentence to the islanders (at noon) after which no one speaks (communicates) and he says, "I see blue eyes!"
Now the question is: Who all leave the island and at what time?

Link to the Solution

Solution to The emperor's party

Link to the Problem

Nice try by Mythalez, Vivek and Ankit! I had never thought of such a solution!
Here goes my Solution:
2^11 = 2048 which is greater than 2009. Hence, all numbers from 1 to 2009 can be represented
using 11 bits! Now represent each bottle number in 11 bit binary format and list them row wise. Each row now has a 11 bit number representing a bottle number. Let each column be a single bit. So, each column would contain either a 0 or a 1 corresponding to each bottle(row). Keep one slave per column and make the slave drink from all the bottles which have a 1 in that column! Hence, you get the poisoned bottle using the combination of slaves who die (write 1's for the slaves who die and 0's for the slaves who don't and the binary number hence formed gives the bottle number corresponding to the poisoned bottle).
e.g.
Let's say the third bottle was poisoned.

1   2   3   4   5   6   7   8   9   10   11     - Slave numbers

0   0   0   0   0   0   0   0   0    0    1     - 1st bottle
0   0   0   0   0   0   0   0   0    1    0     - 2nd bottle
0   0   0   0   0   0   0   0   0    1    1     - 3rd bottle
0   0   0   0   0   0   0   0   1    0    0     - 4th bottle
.
.
.
.

Now the slaves from 1 to 9 wont die and 10th and 11th slave would die after 10 to 15 hrs. From this we can decode the bottle number by writing nine 0s followed by two 1s i.e. 00000000011 which is 3. Hence, we conclude that the third bottle is poisoned!

Here time of death was included just to introduce some confusion while solving the problem. However, if Vivek's time window concept is used (which seems reasonable) we can achieve this using ceil(11/3) slaves i.e. 4 slaves!!!!

The emperor's party

You are an emperor of a huge kingdom and are conducting a party tomorrow in which you have invited very important guests. You had ordered for 2009 bottles of expensive wine for the celebration. However, you come to know that the wine in one of these bottles has been poisoned (but you don't know which one) and that this poison exhibits no symptoms until death. Also, death occurs within ten to fifteen hours after consuming even the minutest amount of this poison. Since the guests are very important you cannot risk serving them poisoned wine. You have slaves at your disposal who could be made to drink the wine in order to detect the poisoned bottle. Since you don't want to disturb the other important tasks the slaves are carrying out, you want to do this with the least number of slaves possible. How would you go about doing this so that you could have a smooth celebration tomorrow and what is the minimum number of slaves you would have to use?

Link to the Solution

Solution to The prisoners of the Zhou Dynasty

Link to the Problem

Manikandan's solution to this problem was absolutely correct!

My solution:
Since there are 5 cards and only 4 suits there has to be at least 2 cards of the same suit! So one of those cards can be kept as the 5th card and one card can be sent first to denote the suit of the 5th card to the second prisoner. Knowing the suit brings down the number of possibilities of the 5th card from 52 to 12 (as one card of that suit has already been sent). An absolute ordering can be established between the other three cards breaking ties by giving different weightage to different suits. So there are three cards, low, mid and high with which we can make 6 combinations. So the prisoners could decide to denote numbers from 1 to 6 by the different orders in which these cards are sent (low mid high as 1, low high mid as 2 etc.). Now there are 12 possibilities for the 5th card but only 6 numbers can be encoded using the 3 cards. So we need some other information. The beauty is you can send any of the 2 cards of the same suit and any of these two cards can be kept as the card to be guessed. So choose the first card such that the difference between the fifth and the first card is less than or equal to 6 (on a circular scale). After sending the first card, the difference between the first and the fifth card can be sent using the other three cards. For example if u have 3 and Jack of the same suit, send Jack first and then 3 so that the difference is 5.
Hence, send the first card to denote the suit and the other 3 cards in the order encoding the difference between the fifth and the first card!

The prisoners of the Zhou Dynasty

Two prisoners were sentenced to death by King Xuan of Zhou and were kept in two different inaccessible cells. They were to be put to the gallows the day after. However, King Xuan wanted to give them a last chance. Since he was very fond of riddles, he came up with one for the prisoners which if they solved, they would be set free. The prisoners were told that they would be put into a single cell for a day when they can discuss their strategy, after which they would again be sent back to their respective cells. One of the prisoners would then be given 5 playing cards out of the pack of 52 cards. He can send four of these five cards to the other prisoner through the jailor one by one after which the second prisoner has to guess the one card (number and suit) which is left with the first prisoner. If he guesses right, both the prisoners would be set free but if not they would be hanged the same day.
What strategy could they possibly come up with which could save them?

Link to the Solution

Solution to the pistol duel

Link to the Problem

Since you as a cyborg are intelligent, assuming the other two cyborgs also to be equally intelligent, Sujit gave the right solution! Here goes my solution assuming the same!

Lets analyze the scenario when both you and the 50% accuracy cyborg miss:
The 100% accuracy cyborg gets the chance now and he surely hits. So he would want the cyborg who would have a lower accuracy of hitting to get the next chance so that he has a higher probability of surviving and hence he would choose to kill the 50% accuracy cyborg.
The 50% accuracy cyborg knows this and hence would never want the 100% accuracy cyborg to get a chance. So in his turn he would want to kill the 100% accuracy cyborg and hence would aim at him.
Now consider your first turn. If you choose to aim at the 50% accuracy cyborg and if you hit then the 100% accuracy cyborg would aim at you and you are sure to be dead and if you miss, the 50% accuracy cyborg would get the next turn and he would aim at the 100% accuracy cyborg for reasons mentioned above. On the other hand if you aim at the 100% accuracy cyborg and if you hit, then the 50% accuracy cyborg would aim at you but this time you have 50% chance of survival. However, if you miss, the 50% accuracy cyborg would again aim at the 100% accuracy cyborg(same as above). Therefore, you have more chances of survival if you aim at the 100% accuracy cyborg than if you aim at the 50% one.
Hence, you aim at the cyborg with 100% accuracy!

The pistol duel

You are a cyborg in a pistol duel with two other cyborgs. You have been programmed to fire pistols with an accuracy of 33%. The other two cyborgs shoot with accuracies of 100% and 50% respectively.
The rules of the duel are one shot per-cyborg per-round. The shooting order is from worst shooter to best shooter. Thus, you go first, the 50% guy goes second, and the 100% guy goes third; repeat. If a cyborg dies, we just skip his or her turn. Which cyborg should you shoot at in round one to maximize your chances of survival over time?

Link to the Solution

Solution to Getting all possible denominations

Link to the Problem

Consider the bags as switches, switching the first bag on indicates that u give away the first bag full of coins. This can be represented as a 10 bit long binary number with which you can represent 0 to 1023 numbers. But here you have only 1000 coins. With 9 bits you can represent numbers from 0 to 511. Put 2^0 = 1 coin into the first bag, 2^1 = 2 coins into the second bag, 2^2 = 4 coins into the third bag, ... so on till you put 2^8 = 256 coins into the 9th bag. With this arrangement you can give away all denominations till (2^10-1) = 511. And you have 489 coins left. Put all of that into the 10th bag and now to represent any number from 512 to 1000 (lets say N) just give away the bag with 489 coins and the combination of bags which equate to (N-489) which will always be less than or equal to 511 (since N <= 1000) and is hence achievable using the combination of other 9 bags!
Hence, the number of coins that you put into the bags are 2^0, 2^1, 2^2, .... , 2^8, 489.

Getting all possible denominations

Divide 1000 one rupee coins into 10 bags such that you are able to arrive at any denomination less than or equal to Rs.1000 with some combination of these bags.

(If you had put 600 one rupee coins in one bag and 400 one rupee coins in another bag, you can arrive at Rs.400, Rs.600 and Rs.1000 using these two bags. You have to divide the coins into ten such bags so that u can arrive at each and every denomination <= Rs.1000 using the bags)

Link to the Solution

Solution to the five greedy pirates

Link to the Problem

The idea is to reduce the number of participants (greedy pirates) and see what happens in that case and start reasoning based on that. One more thing to note here is that a pirate would accept a proposal only if he knows that in case he would not accept the proposal, he would get less of the treasure. Let's say we identify the pirates by the number of years of experience they have.
Now consider the case when pirates 5, 4 and 3 killed and only 2 and 1are left. Now 2 has to get a vote from 1 to stay alive. However, 2 can never give 1 more number of coins that what he would get by killing 2 and hence 2 can never satisfy 1. Therefore, 2 would never want to be left alone with 1 and 3 being intelligent knows that!
Now consider the case when pirates 5 and 4 are killed and only 3, 2 and 1 are left. 3 has to get one more vote from either 2 or 1 to stay alive. And 3 knows that 2 never wants to stay alone with 1 and hence would always vote for 3. So 3 being so lucky could keep all the 1000 gold coins and give nothing to 2 and 1 and still stay alive. So 2 and 1 would not want 3 to be a proposer of the split even if they get one gold coin each and 4 being intelligent knows that!
Now consider the case when only the pirate 5 is killed and 4, 3, 2 and 1 are left. 4 has to get 2 more votes to get a majority which it can get from 1 and 2 by giving them 1 gold coin each and keeping the rest 998 with himself and giving 3 nothing. So 3 would not want 4 to propose even if he gets 1 gold coin for himself, and 1 and 2 would not want 4 to propose if they get more than 1 gold coin which 5 being intelligent knows!
Now consider the real problem wherein 5 has to propose so that he gets the maximum and doesn't get killed. He needs 2 more votes minimum inorder to stay alive. He could get one vote from 3 by giving him one gold coin. And for one more vote he could give either 1 or 2 two gold coins as discussed above! So he keeps 997 gold coins for himself, gives 1 gold coin to 3 and give 2 gold coins to either 1 or 2!

Hence the proposal is :
5 - 997 gold coins
4 - 0 gold coins
3 - 1 gold coin
2 - 0 gold coins or 2 gold coins
1 - 2 gold coins or 0 gold coins

The five greedy pirates!

There are 5 pirates, all of them being equally greedy. They have varied number of years of experience. Say for convenience sake 5, 4, 3, 2 and 1. They find a booty of 1000 gold coins which they want to split amongst themselves. Everyone being greedy, wants the most for themselves. So they device a scheme!
They agree that each one would propose a split starting with the most senior person to the least senior person. If there is no majority, the guy who proposed will be killed and then the next guy gets the chance. So it'll be 5 first then 4 etc. How does the guy with 5 years experience propose to split the coins so that he gets the max and does not get killed?

Link to the Solution