Cube in a sphere

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!

Comments

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

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

    12.5 = 100/#vertices

    ReplyDelete
  3. @sangharsh.. Yes.. its correct..

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

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

    how 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??

    ReplyDelete
  5. oops!!

    expectation 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)

    ReplyDelete
  6. @Giridhar.. Thanks.. Correct solution :)

    ReplyDelete

Post a Comment