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.

The Maradona Game (a.ka. Koun Banega Maradona)

Ever since Diego Maradona hung up his magical boots, Argentina has been waiting for an heir. And because players like Maradona don't just drop off trees or grow in football field there has been no apparent heir. So if we cannot get a next Maradona we will thrust the crown over someone, that is what they decided. So every other season some promising young starlet is crowned as the "Next Maradona". Sometimes it is Maradona himself doing the declaration which lends even more credibility to such an outrageous claim. Aimar, Saviola, D Allesandro, Messi and recently Kun Aguero. The list keeps on growing. Of course what keeps this game interesting is that most player who have been so named have failed to live up to promise and fall by the wayside, though it does seem that Messi is here to stay (and while these Maradonas continue to fail, a man completely different from Maradona has made Argentine national team his own). So the hunt continues.
And now in another country, this game has caught up and become a favorite pastime. French football reached its pinnacle in the reign of Zidane The First. When it became apparent in 2006 that world cup would be the final chapter of his career, French public immediately anointed Frank Ribery as the next midfield general. Since then Ribery has evolved nicely and has really become the fulcrum of this team. But to keep the game interesting and competitive suddenly two more names have been thrust into the ring those of Karim Benzema and Samir Nasri. What advances there case is the fact that they are both of the same ethnicity as Zidane, Algerian Khabyle. And now that French national team is playing in its first major tournament without Zidane, great things are expected of these three. Maybe by the time the tournament ends one of them would have taken the lead in the race to become next Zidane. But I am sure in couple of years, fickle public having gotten bored of these names would have elevated some other youngster, because the game of course is bigger than any individual.
And what about India. When the maestro puts his bat to rest, I am sure we will not be left behind and many a new Tendulkars will be launched in passionate discussions at coffee table, barber shops, panwalas etc. Anyone betting on Rohit Sharma!!

Useful tips for booking tickets on IRCTC

I have been frustrated endlessly by the Indian Railway online ticket booking site especially at 8 o clock in the morning (not exactly the best time to waste 1 hour in front of your laptop), when I am trying to book Tatkal tickets. And given the fact the I am a very frequent traveller, this happens almost every other week. If I am lucky I end up with a confirmed ticket and a headache otherwise I only end up with a headache. But given that it is a monopoly one has to learn to live with it. These are some of the tips that I have learned the hard way over time (so called wisdom gained from experience). Ofcourse my head still hurts everytime I undergo this exercise (like today) but atleast I have now a blog post to show for all this.

1. In tatkal tickets even though the ticket is always booked from starting station of train to the ending station, there are different quotas for different source, destination pairs, which is extremely surprising. So for example today when I looked for Tatkal ticket from New Delhi to Nagpur on Gondwana express it was showing waiting. But for the same train when I looked for New Delhi to Bilaspur (which is the end station), it was showing around 86 tickets available. So I happily booked the ticket from New Delhi to Bilaspur, ofcourse after a few retries. So remember, always look for availability and book ticket from starting to ending station of train and anyways you are going to pay for the whole ticket in tatkal no matter what your source and destination are.

2. Tatkal days can be booked 5 days in advance. But a large number of times when booking a ticket from Nagpur to Delhi, exactly 5 days in advance and at sharp 8 am in the morning (which is when tatkal bookings open), I would find no availability. This puzzled me a lot and then I had one of those life changing moments, an epiphany, an aha insight. The trains didnt actually start at nagpur and in many cases the starting day would be one before the day they reached nagpur. For example Tamil Nadu express reaches Nagpur on 10th of June but it started from Chennai on 9th of June. So its tatkal booking would have opened on 4th of June (not on 5th) and would have got over that day itself. So lookout for the starting day of your train and book 5 days in advance from then. Also if I would have given my source station as Nagpur it will not have allowed me to book on 4th saying that "tatkal tickets can onlly be booked 5 days in advance". So again you would have to give source station as the starting station of train and then in boarding point you can put your actual station.

3. There is an option of "Quick Book" in the menu just below Plan Your Travel. This is something I discovered just a few days back and it is very useful. Basically here you need to know the train number that you would be traveling on and then in a single page you can fill all the details and get the booking instead of first looking at list of trains and then selecting one among them. Protocol I follow is that first at www.indianrail.gov.in I look at the availability and select a particular train I would like to travel on and then I directly go to Quick Book on irctc and fill in all the details. This really saves a lot of time, especially since indianrail.gov.in is not down that often as irctc. Also if a large number of people start using indianrail.gov.in for availability lookups than hopefully it should reduce the load on irctc and make it more responsive.

So if anyone has any other useful tips, please do share.

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.