Two Partially Solved Puzzles

I read about these two puzzles in the book by Peter Winkler mentioned in a previous post around a week back. Since then I have thought about them on and off but have made only little progress. They are in the "Toughies" section of the book, and given the fact that puzzles in other sections are also quite challening, these might be quite tough. Also Winkler points that there is surprising connection between the solutions of both these.

1) It is a variation on the prisoner and hats puzzle. There are n prisoners and the jailer will put either a red or a blue hat on each prisoners head. Then they are arranged in a circle so that everyone can see everyone else's hat except his own. Now the jailer takes them one by one into a room, in arbitrary order and asks each one to guess the color of his hat. The prisoner can either pass or make a guess. If everyone passes then they are all killed, if anyone guesses incorrect then also they are all killed. So the only way for prisoners to escape is that atleast one person should guess and all those who are guessing should guess correctly. Now prisoners can agree on a strategy beforehand for guessing. What should be there strategy so as to maximise there probability of getting free. Winkle notes that with 16 prisoners, you can have a chance higher than 90% of escaping. Also note that no one can know what others have guessed and there can be no communication between the prisoners once the game starts.
My progress so far has been to show a probability of escaping equal to 75% if the number of prisoners is greater than 2. For 2 prisoners it is obvious that they cannot have a chance higher than 50%. For 3 prisoners the strategy they adopt is that if a prisoner sees both the other prisoners having the hat of same color he guesses the opposite color, otherwise he doesnt guess. This strategy will only fail when all three have the hat of same color which is 2 out of 8 possible combinations. This gives a 75% chance. Now for greater than 3 prisoners, they just select 3 prisoners. Rest will not guess at all and these 3 will play as if they were the only 3 prisoners and follow the strategy for that. This gives a chance of 75% for any number of prisoners greater than 3. This is where I have got so far.

2. A wants to send B some message. But all A can do is generate k random bits and then he is allowed to modify one bit of that sequence. He can of course chose not to modify anything. Then he sends these k bits to B. How big a message can he send to B? A and B will of course decide on a strategy beforehand. Trivially A can send a single bit message by encoding it in the first bit of the sequence. My hunch is that A can send log(k) bit long message, which means he can send a number from 1 to k. For two this is trivial to show and I have been able to show it for k=3 albeit a bit mechanically. The approach I have tried is that there are 2^k possible bit sequences of length k. Now if we can divide all these into k groups, such that no matter whatever the generated sequence is, just by modifying one bit, we can reach any of the k groups we are done. In other words, we take any k bit sequence and all the sequences at hamming distance one from it. Only 2 among these k+1 sequences will lie in the same group. For k=3, one possible division that satisfies this is
1. 000, 101, 111
2. 001, 110
3. 010, 100, 011

Unfortunately I have not been able to find any pattern in this which will help me generalise to arbitrary k.