**Source:**CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science

**Problem:**10% of the surface of a sphere is colored green, and the rest is colored blue. Show that no matter how the colors are arranged, it is possible to inscribe a cube in the sphere so that all of its vertices are blue.

**Hint:**Use probabilistic analysis. Consider a random cube and calculate the expected number of vertices that are blue.

(Update 23/06/10):

**Solution:**Posted by connect2ppl - Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!

Nice! Reminded me of the various problems that I solved on the 'Probabilistic Method' recently.

ReplyDeleteDidn't solve it, just wondering if 12.5% is the threshold percentage for this to happen.

ReplyDelete12.5 = 100/#vertices

@sangharsh.. Yes.. its correct..

ReplyDelete@infiniti (Nishant Totla) .. It would be good if you could share some of those problems here :)

for a random cube, expected number of blue vertices is (9/10)*8 = 7.2

ReplyDeletehow to go from here?

if probability of all vertices being blue is +ve, then it implies the existence of a cube we r looking for.

But, how to get red of dependency among the colors of vertices??

oops!!

ReplyDeleteexpectation being 7.2 itself proves the existence of cubes where all vertices are blue ( since max value of random variable is 8, 7.2 expected value is possible only bcoz of the existence of cases where its value is 8)

@Giridhar.. Thanks.. Correct solution :)

ReplyDeleteshouldn't the expected number of blue vertexes be

ReplyDelete8*[(0.9)^8] + 7*[(0.9)^7][(0.1)^1] +......+1*[(0.9)^1][(0.1)^7] rather than 8*(0.9) ?

The first one sums up to around 4.