Fog Creek Software
Discussion Board




Earth To Moon

This Ques. was asked in microsoft interview yesterday and i was not able to answer it

U have infinite supply of paper
thickness of paper is 1mm
distance between earth and moon is 1,00,000 Km

every time we fold the paper so its thickness doubles

how many folds will be needed so that the thickness becomes >= distance between earth and moon

BondofUK
Thursday, April 15, 2004

I assume you have one very big piece of paper that you can keep on folding.

Small number example:
Thickness of paper is one unit, how many folds to get to two units?  Four units?  Eight units?

Answer: One fold to get two units.  Two folds to get four units.  Three folds to get eight units.

One can quickly deduce that if x is the desired number of units, then it takes (base two log of x) number of folds.  Or with a calculator, folds = ln(x) / ln(2), where ln() is the natural logarithm.

But what to do if you didn't bring a calculator to the interview?

JHY
Thursday, April 15, 2004

he calculated the answer for me which was about 46 but even i was not satisfied with my answer because i thought there has to be a trick in the ques. otherwise the would not ask such simple ques.

BondofUK
Thursday, April 15, 2004

Hmm,

I reckon all that would be required is to show that you got the base-2 nature of the problem, rather than to just say "46".

To do the fold, it sounds like you'd have to fold the paper in half each time.  How do you fold an infinite sheet of paper in half?

Also, I thought you could only ever fold a sheet of paper in half 7 or 8 times before it became too stiff....

Don't think you'd gain anything from saying it was impossible, however.... negative attitude!


Alan

Alan Graham
Friday, April 16, 2004

For a computer scientist the calculation ought to be easy. You correctly identified the power of 2 nature of the problem. Now it so happens that he gave you very easy numbers. There are 1000 mm in a m, and 1000 m in a km and 1,000,000  (1000 x 1000) km to the moon. So there are 10^12 paper thicknesses to the moon. As a computer professional you should know that 2^10 is as close to 1000 as makes no difference so you need to double your paper thickness 40 times.

David Clayworth
Friday, April 16, 2004

I object. The "bend" over the fold becomes so large that the paper liquefies at the center by being compressed due to its own gravitational forces. It never reaches from the earth to the moon.

Ham Fisted
Friday, April 16, 2004

I also object. I recall learning as a child that it's actually impossible to fold a piece of paper more than seven or eight times (I forget which). Hopefully this wasn't an old wives' tale I picked up during my childhood.

But other than that.. 100,000,000,000 millimeters = 100,000km. Since 2^37 = 137,438,953,472,  the answer is between 36 and 37, meaning 37 folds would get you to the moon, forgetting the problems mentioned above.

Peter Cooper
Tuesday, April 20, 2004

If you would like to find the numerical answer to the question in the first post, it may be important to notice that the distance given reads "1,00,000 km."

Notice there are two commas separating the number for ease of counting digits, but between the first comma and the second comma there are only two digits, so one might interpret the distance to be 100,000 km or 1,000,000 km.

The convention is 3 digits between commas because it makes reading big numbers in English easier, so the given distance might be a typographical error.  I think the mean distance between the earth and the moon lies somewhere bewteen 100,000 km and 1,000,000 km, so it is not clear which distance the question intended to give.

To sum up the answers given so far in no particular order:
assume d = 1,000,000 km, then it takes 40 folds
assume d = 100,000 km, then it takes 37 folds
somehow there is also 46 folds

JHY
Tuesday, April 20, 2004

I believe the "you can only fold a sheet of paper 7 or 8 times" belief is a myth.

Suppafly
Tuesday, June 22, 2004

*  Recent Topics

*  Fog Creek Home