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.

Peter Winkler : The Puzzle Master

Couple of years back I came to know about Peter Winkler, a mathematics professor, most likely when I came across this piece by him "Seven Puzzles You Think You Must Not Have Heard Correctly".
This contains Seven really nice puzzles with solutions most of which thought I had heard previosuly but there was one especially interesting and which turned out to be one of the toughest puzzle I have ever solved.
After that I came to know of couple of books that he has written on puzzles.
1. Mathematical Puzzles: A Connoisseur's Collection
2. Mathematical Mind-Benders

Unfortunately they are not available in indian editions, but luckily a large number of pages of the first book are on view at both amazon and books.google.com. It is certainly a treasure trove for puzzle seekers like me. It contains some of the most amazing puzzles you would have come across. He also gives a personal perspective to most puzzles, by explaining in the solutions, how he came across the puzzle. I really enjoy reading those parts too. But for the sheer quality of the puzzle this book is unbeatable and the puzzle are neatly divided into various sections like Algorithms, Geometry, Probability and so on. I would highly recommend it.

Some days back a friend pointed me to another paper by winkler, "Five algorithmic puzzles".
This as the name says contains 5 puzzles all of which have a common theme, which is that you are given a process, such as breaking a chocolate bar along a boundary iteratively, and you have to prove that the process will end in finite steps and it will end in specific configuration . To solve these you will have to find some property which either increases / decreases in the process and it has a bound beyond which it cannot go. These are again really tough puzzles and accompanied with solutions and winklers interesting notes.

Anyone interested in other recreational mathematics / puzzle writings will do good to read stuff by these people:
1. Martin Gardner (Highly Recommended): Perhaps the first person to write so extensively about puzzles and recreational mathematics. Immensely interesting and readable.
2. Raymond Smullyan: Mostly writes about Logical puzzles and interesting stuff in Mathematical Logic.
3. Ian Stewart: I dont think he is into puzzles but he writes about complex but interesting mathematical topics and makes them easy to understand and exciting. After reading his books you would want to be a mathematician!!

Again if you go to Google Books, you will find some of the works by these guys (Not Smullyan) are available for limited preview.

Two Puzzles

1. Given a sequence of r*s+1 distinct integers (r>=1, s>=1) prove that there exists either an increasing subsequence of length r+1 or a decreasing subsequence of length s+1.
Its a nice puzzle having a clean elegant solution. Though it is not really an aha! puzzle yet the solution does not involve much mathematical trickery. The way I got the solution was to first fix r at 2. So then we are looking at sequences of length 2s+1. Once you find the solution to this, it is easy to generalize it to arbitrary r. But I think this is a tough puzzle and I felt really good when I could solve it :)

2. There are 100 seats in an airplane and 100 passengers each of whom has been assigned a boarding pass which contains there seat number. They board the plane one by one. Unfortunately the first passenger has lost his boarding pass, so he sits on a random seat. Every subsequent passenger, if he finds his seat vacant takes it otherwise sits randomly on any of the empty seats. So what is the probability that the last passenger finds his seat vacant?
I had heard this puzzle couple of years back and am not sure whether I was able to solve it then. When I reread it again yesterday, I could not recall the solution but I did remember that there is a simple elegant solution to it. After some thought and much frustration I finally got the answer and felt relieved more than anything else. But the solution is nice. You can also generalize it to find probability of kth passenger finding his seat vacant.

Whats wrong with this code segment

Here is a small code segment to simulate doing something periodically (say every 5 mins) in Java. Date class here is standard java.util.Date

Date currDate = new Date(); //sets currDate to current date
Date prevDate = currDate;
int interval = 5;

while (true) {
if (currDate.getTime() >= prevDate.getTime() + interval * 60 *1000){
doSomething();
prevDate = currDate;
}
currDate.setTime(currDate.getTime() + 1*60*1000) //increment by 1 minute
}



Will this work? If not why not. Ignore if I have made any compile errors. I am looking for a logical error or more of an error from programming language point of view.

Answer: It will not work because when you do prevDate = currDate its the reference that gets copied. So essentially prevDate and currDate always point to the same Date object. So there is never any time difference between the two. The correct way to do this would be
prevDate.setTime(currDate.getTime());
or
prevDate = currDate.clone();

I have made this error so many times in past few days that I should be kicking myself in the backside. Though in my case things were not abstracted out so nicely and were part of a larger code. This whole logic was split with assignment happening somewhere else, comparison happening somewhere else etc etc. So it was not so easy to track it. In Google I had used
Joda Time which provides much nicer interface and gives an immutable class. That would have saved me from this error because you cannot modify the JodaTime object. You would always have to create a new instance to increment it. So prevDate would have pointed to the older instance and the comparison would have gone through nicely.

Nice Puzzle

There are coins of various denominations laid out in a row. Two player play a game where they take turn one by one to pick either of the two coins at the ends of the row. They play till no coin is left and the person whose coins add up to greater amount wins. Show that player who starts first has a strategy such that he cannot lose if the number of coins initially is even.

This is one of those Aha! puzzles where you just need a single insight to solve it and once you know the solution it seems completely obvious. Really nice though