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. infiniti6:47 PM, June 21, 2010

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

    ReplyDelete
  2. sangharsh6:51 PM, June 21, 2010

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

    12.5 = 100/#vertices

    ReplyDelete
  3. Pratik Poddar10:40 PM, June 21, 2010

    @sangharsh.. Yes.. its correct..

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

    ReplyDelete
  4. Anonymous5:04 PM, June 22, 2010

    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. Anonymous5:19 PM, June 22, 2010

    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. Pratik Poddar2:51 PM, June 23, 2010

    @Giridhar.. Thanks.. Correct solution :)

    ReplyDelete
  7. Unknown10:23 AM, September 11, 2017

    shouldn't the expected number of blue vertexes be
    8*[(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.

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more