## Jack & The Beanstalk

Here is the **3rd logic puzzle**:

Jack has just swapped a cow for a magic seed. So he sows it and in just 1 second the seed grows into a massive beanstalk 100 meters high and makes a pause.

Throughout the next second, Jack begins to climb the beanstalk and he can only make 1 meter before the plant shakes and grows another 100 meters. It pauses again.

At this point it must be explained that the plant grows uniformly in all its length, precisely as if it was perfectly elastic and was being stretched from both ends. So, **every point of the plant grows**/stretches.

Throughout the following second, Jack climbs 1 meter and afterward the plant shakes and grows another 100 meters. It pauses. This process repeats indefinitely.

Will Jack ever reach the top of the beanstalk?

hex| PUZZLE MASTER | Profile October 7th, 2009 - 6:46 amLet’s consider steps (corresponding to time in seconds) where L is the height of the beanstalk, and H is Jack’s height:

L0 = 100

H0 = 1

Li+1 = Li + 100

Hi+1 = Li+1 / Li * Hi + 1

Note: In each step the beanstalk elongates, then Jack climbs up 1 meter

We can prove by recursion that:

Li = 100 * (i + 1)

Hi = (i + 1) * Sum(1 / j) for j = 1 to i + 1

The question then boils down to:

Is Hi >= Li for some i?

which is equivalent to:

Is Sum(1 / j) for j = 1 to i + 1 >= 100?

This is a the harmonic series (which is divergent), so essentially Jack will eventually reach the top of the beanstalk.

What we can further prove is that he will be successful at or before i = (2 ^ 198)-1 (which is essentially a time in seconds)

Al of course assuming that Jack is an immortal superhero

aaronlau| Profile October 7th, 2009 - 7:25 amYes.

Based on calculation, I seem to arrive at the 17-18 sec mark.

Rationally, i find it difficult to grasp how it can be faster than 100 seconds.

ahsergio| Profile October 7th, 2009 - 7:41 ami was unable to visualize correctly the last two puzzles, but lets see about this one.

As the whole plant stretches, the first meter that Jack climbed will become 2 meters, plus one meter that he can climb every pause. So this one meter will eventually (although it will take a long time) make Jack reach the top, i followed this chart to get to my conclusion:

plant(m) / jack(m)= proportion

100/1=100

200/3=66,666

400/7=57,142

800/15=53,333

suineg| PUZZLE MASTER | Profile October 7th, 2009 - 7:58 amI dont think so, my answer to this one is NO, because any second it passed his ascendent move represent an smaller percentage of the actual grow of the tree, lets put it in a example the first 3 secondss the man climb:

t=0 plant= 100 mts man= 0 mts

t=1 plant 100mts man= 1 mts (the plant grows again)

plant= 200mts man= 2 mts (because 2/200 is ths same as 1/100 and the man moves with the plant as it grows) now he is at 1% of the size of the plant

t=2 plant= 200 mts man= 3 mts (the plant grows again)

plant= 300 mts man= 4.5 mts (same reason as in t=1)

now the man is at 1.5% os the plant size

so this pattern continues indefinetely and the man advance a distance that represent smaller and smaller percentage oof the plant size so it will take infiniity to reach so it is impossible I guess jaja I have been wrong before.

This problem is somehow similar to a numeric calculus problem of a turtle that advance half of the distance it has left to reach the goal every second, nice problem bilbao, my guess is that you teach math in the University for sure, cool.

Sebastian Roughley| Profile October 7th, 2009 - 8:10 amI think he would. The clue is in the fact that every part of the beanstalk grows at the same time. So Jack would travel during the growth spurts, effectively negating those effects.

abcbcdcdef| Profile October 7th, 2009 - 8:15 amYes, he can!Ans can be proved mathematically.

height he reached after n secn=0 when beanst.=100) n=/=1

{([([(1x2/1)+1]x3/2)+1]x4/3)+….)x n/n-1)+1}

=(2/1×3/2×4/3x…xn/n-1) +(3/2×4/3x…xn/n-1)+…+n/n-1 +1

=n{1 +1/2 + 1/3 +1/4 +…+1/n-1} +1

The height of the beanstalk=100n

He will reach the top if

n{1+1/2+1/3+…+1/n}+1=100n

ln(n)+0.5772+1/n=ln(n)=99.4228

n=1.51×10^43s

————————————————

taking t=0 when beanstalk=0m

time taken=(1.51×10^43 )+1s; to be exact

Hopefully my calculation is right…

————————————————

Still, he would have to be alive for that long; which, in a fairy tale, is possible.

Shawn| PUZZLE GRANDMASTER | Profile October 7th, 2009 - 1:18 pmNo, for so many reasons:

The beanstalk would eventually topple under it’s own weight, although if the weight of the beanstalk causes the tip to bend downward close enough to Jack, he might be able to reach it.

The beanstalk would eventually exit the atmosphere and cease to grow.

The temperature would quickly become too cold for Jack to survive.

The atmosphere would quickly become to oxygen-poor for Jack to survive.

Jack would quickly tire and be unable to keep up his grueling pace of 1m/s vertical climb. Climb 3 feet, rest for 1 second, repeat – no thanks!

Bobo The Bear| PUZZLE MASTER | Profile October 7th, 2009 - 3:12 pmIf Jack (and the universe around him) had an infinite lifespan, infinite energy reserves, infinite patience, etc. … then yes, he would eventually reach the top.

After two seconds, Jack has climbed 1 out of 100 meters, or 1% of the way. During the next growth spurt, that percentage stays unchanged. When Jack climbs again, he gains 1 out of 200 meters, or (1/2)% of the remaining distance. The third time he climbs, he gains 1 out of 300 meters, or (1/3)% of the remaining distance, and so on.

After 4 seconds, he’s gone (1 + 1/2)% of the total distance.

After 6 seconds, he’s gone (1 + 1/2 + 1/3)%.

After 8 seconds, he’s gone (1 + 1/2 + 1/3 + 1/4)%.

After 10 seconds, he’s gone (1 + 1/2 + 1/3 + 1/4 + 1/5)%.

And so on.

Mathematically speaking, these fractions form the harmonic series, which diverges – meaning that there’s no limit to how large the sum of the fractions can be. Eventually these fractions will add up to 100% of the distance he needs to go.

But it will take quite a while. If my calculations are correct, it would take 9.565 * 10^35 years. Considering that the Big Bang model estimates the age of the universe to be 1.373 * 10^13 years, I wouldn’t wait up for him.

TonyTKL| Profile October 7th, 2009 - 6:24 pmYes, assuming he doesn’t grow old and get tired, that is. ;-) If he’s climbing 1 metre each time, there will be a certain amount of plant growing beneath him. Therefore, there will be a little less growing above him each time.

Mashplum| PUZZLE MASTER | Profile October 7th, 2009 - 8:57 pmYes. I haven’t figured out how long it will take though.

Falwan| Profile October 8th, 2009 - 4:12 amYes, Jack will reach the top after a long time.

jmart| Profile October 8th, 2009 - 7:29 pmNo, the ratio that he gains on the plant will drop too small and he’ll actually start to lose ground on the top, limit of 0 as the number of growths goes to infinity.

BillyPilgrim| Profile October 8th, 2009 - 10:42 pmNo

kasabubu| Profile October 9th, 2009 - 12:09 pmWithout doing the math, I’d say “no”, but he will come very, very close to it as the curve (if you’d pictured hes ascend in a graph of a function) will approach the curve of the beanstalk’s growth infinitely.

IrishFutbol| Profile October 9th, 2009 - 12:17 pmNo, while the ratio of amount climbed/total length will initially go up at the beginning, after a few seconds it will start to slowly decline to 1%.

Satya| Profile October 9th, 2009 - 12:21 pmNot Possible mathematically, Jack rate of assent is far less than the growth of bean. Even though one may think jack is in advantage with the elastic growth of beanstalk, it is a wrong perception as Jack’s elevation from ground will increase but distance from the top end of stalk will not be reduced.

I calculated to a negative result .

How ever as most pointed out practically beanstalk cease to grow and Jack will tire soon.

suineg| PUZZLE MASTER | Profile October 9th, 2009 - 4:04 pmok, now I agree with everyone that said that under the inmortal hero condition it could be possible;

because mathematically is a sum of fraction that has to equal a constant that is 100 percent

sum (1/i) from i = 1 to ? = 100 and ? is the close to the exact value of seconds it would take, close to a discrete infinity , cool man was tricky a fairy tale jajaja bilbao you are definetely a mathematician, got me but cool.

hex| PUZZLE MASTER | Profile October 10th, 2009 - 3:36 am@suineg:

The 100 comes from the following:

Li = 100 * (i + 1)

Hi = (i + 1) * Sum(1 / j) for j = 1 to i + 1

Hi >= Li

(i + 1) * Sum(1 / j) for j = 1 to i + 1 >= 100 * (i + 1)

Sum(1 / j) for j = 1 to i + 1 >= 100

More interesting physics facts:

- As the beanstalk grows, the earth rotation will slow down

- Eventually, the earth will rotate with the beanstalk

- Once the beanstalk becomes heavy enough (supposing almost infinite rigidity), it may fall through earth and emerge from the other side of the globe

The usual pat on the back :

Thanks Bilbao

Thanks RK

suineg| PUZZLE MASTER | Profile October 10th, 2009 - 7:12 pmcool Hex that is advance math for me to grasp right away jajaja, what I mean with my last comment was the ratio of percentage that represent 1 mts that the man advance in each time the plant grows; first 1% of 100,the plant grows the man climb 1 mts the plant grows again 4.5 of 300 that is 3/2%=(1+1/2)% of 300 so in my case was a much simpler sum, that is the sum of the percentage alone that always sum up to 100, this is somehow very well explained by Bobo The Bear, that sum has to add in some time 100%, the number of terms in that series is like the number of seconds the man take to reach to the top, but this problem is hard and I learn what a divergent harmonic series was that, so thanks, there were very cool explanations, congrats.

RogHyde| Profile October 11th, 2009 - 6:35 pmI don’t understand the maths but can’t see how he can possibly gain on the beanstalk:

Time Jack Tree Percentage Jack’s

Climbs Grows of Growth Total

1 sec 0m 100m 0 0

2 sec 1m 100m 50% 1 + (1m x 50%)

3 sec 1m 100m 33.3% 3.5m + (3.5m x 33.3%)

4 sec 1m 100m 25% 4.66m + (4.6m x 25%)

etc etc

Roger

bilbao| Profile October 13th, 2009 - 2:57 amAlthough it seems counterintuitive, the answer to this puzzle is YES. Jack would eventually reach the top of the beanstalk (in our fairy tale context). Most of you got it right!!!

Some really good math and non math explanations above by Hex, abcbcdcdef and Bobo The Bear.

Mashplum| PUZZLE MASTER | Profile October 13th, 2009 - 10:33 pmI wrote a computer simulation of this problem in order to arrive at the solution. It ran continuously for days without success, but I was still pretty certain that Jack could eventually get there. Thank you math people for proving it, and for proving that the human brain is still far better than a computer. Shame on me for not digging out my old Calculus book in the first place.

hex| PUZZLE MASTER | Profile October 14th, 2009 - 4:59 am@Mashplum

A quick exercise (pushing figures up a little bit):

Computer CPU speed 5 GHz quad core (ie 4 CPUs in the chip)

Assume 10 iterations per clock cycle (too exagerated considering current pipelining and execution optimizations especially that the main execution is a division)

Assume 1.51×10^43 seconds and hence iterations (according to abcbcdcdef)

Time required to compute:

1.51×10^43 iterations / (10 iterations per clock cycle) / (5e9 clock cycle per second) / (4 cores per PC)

= 7.55 x 10^31 seconds

~= 2.4 x 10^24 years

Life is plain too short

cocoawatwat| Profile October 16th, 2009 - 2:11 pmWell really i would say yes or no, i mean what would jack really expect to be at the top? In the story there is a giant that wanted to get him. If i were jack i wouldn’t keep climbing. He was poor too so he should work or something instead of climb an endless bean stalk. Also he could just try to chop it down.

Mashplum| PUZZLE MASTER | Profile October 16th, 2009 - 2:52 pmThanks hex. Here is the program:

10 let n=1

20 let j=0

30 let b=100*n

40 if j>=b then goto 80

50 let n=n+1

60 let j=(j+1)*n/(n-1)

70 goto 30

80 print n”, “b”, “int(j)

90 end

Do you think after 2 septillion years I would have at least got the right answer with this?

Mashplum| PUZZLE MASTER | Profile October 16th, 2009 - 2:53 pmOf course I would have to multiply n by 2 to get the answer in seconds.

hex| PUZZLE MASTER | Profile October 16th, 2009 - 5:21 pmin Basic? Multiply my time estimate by about 100-1000 depending on whether it is interpreted or compiled (i guess interpreted).

Why do you have to multiply by 2?

Anyway, a faster and cleaner implementation would be:

10 s=0

20 i=0

30 i=i+1

40 s=s+1/i

50 if s<100 then goto 30

60 print i-1;”,”;s

70 end

Mashplum| PUZZLE MASTER | Profile October 17th, 2009 - 9:31 amIt is in Basic because I learned to program in 1988 (after which my forward-looking high school cancelled all its programming classes.)

I have to multiply by 2 since each loop takes 2 seconds (1 for the beanstalk to grow and 1 for Jack to climb). The same would be true for your program.

hex| PUZZLE MASTER | Profile October 17th, 2009 - 5:16 pmBasic was such a popular language then. I guess it is still widely used (VB.NET)

Each second Jack climbs up 1 m, and the beanstalk stretches instantaneously. So no doubling needed here.

Puzzler| Profile March 25th, 2010 - 7:51 pmHe would never reach the top because when the tree expanded, he would be ripped in half , or he would fall.

james turner| Profile May 30th, 2010 - 2:17 pmAll,

Though this is an old problem, it is of interest that one can generate a simple differential equation for the solution. This process is as follows:

Let:

b denotes bean height

j denotes height Jack has climbed

vb denote bean rate of growth

vj denote Jack climb rate

dj height Jack climbs in each unit of time

d denotes time increment

Model:

j(t+d) = j(t)*b(t+d)/b(t) + dj

b(t+d) = b(t) + vb*d (growth rate for beanstalk)

=> j(t+d) – j(t) = j(t)*vb*d/b(t) + vj*d

Divide by d:

j(t+d) – j(t) = j(t)*vb/b(t) + vj

————

d

Old Friend the derivative of j(t):

djdt = j(t)*vb/(b0+vb*t) + vj

Solve differential equation for j(t):

j(t) = (b0+vb*t)*log(b0+vb*t)*vj/vb + C)

Initial condition: @t=1, j(1)=1, b0=100, vj=1, vb = 100

C = -(2*log(200)-1)/200

Set b(t) = j(t) to find time Jack reaches the top:

b0+vb*t = j(t) = ( b0+vb*t)*log(b0+vb*t)*vj/vb + C)

Solving for T yields,

t = ( exp( (vb/vj)*(1-c) ) – b0 )/vb

Plugging in Numbers:

t = 2*exp(199/2) – 1 = 3.2608509268211d43 Indeed a big number!!!

ladybug48363| Profile September 17th, 2010 - 4:17 pmDoes the beanstalk stretch thinner as it grows?

soumen023| Profile April 24th, 2013 - 2:21 am50 seconds he will take