## Posts

Showing posts from May, 2010

### Veit Elser’s Formidable 14

Source: CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science Lecture01. Course pointed to me by Aaditya Ramdas (To be CMU Grad Student & CSE-IITB Alumnus)

Problem:
Fit disks of the following diameters into a circular cavity of size 12.000:
2.150 2.250 2.308 2.348 2.586 2.684 2.684
2.964 2.986 3.194 3.320 3.414 3.670 3.736

Write a program or give a general algorithm to solve a general case.

Disclaimer: Did not spend a lot of time on the problem but I have not been able to solve it. Clearly sum of the squares of the smaller radii is less than the square of the larger radii suggesting that it might be possible to fit disks. I am not able to make any more comments!

### Another Hat Problem

Source: Very interesting puzzle from http://forums.xkcd.com/

Problem:

There are 7 people standing in a circle, and each has either a red or a blue hat. The colors of the hats are chosen uniformly at random (although the problem is much the same if they're chosen adversarially). The people can't see their own hats, but can see each others'. Everyone is given a strip of paper and a pen, and simultaneously writes "red", "blue", or "abstain". Nobody can see what the other people are writing, or convey information in any other way. They win if somebody guesses his own hat color, and nobody guesses wrong.

Find a strategy (which they agree on ahead of time) that maximizes probability of winning. Obviously, it is impossible to make a strategy that wins every time, because somebody must guess and that person has no information.

To make it easier, try it first with three people.

Disclaimer: I posted this problem (in different words) 4 months back here but…