A Zeno's paradox revisited?

Consider a circle with a starting circumference of C 0 = 100 C_0 = 100 units. Suppose you start on a point on that circle and proceed to walk along it until you take your first step on or past your starting position. Given the rules below:

  • each step you take is worth 1 unit;
  • for each step you take, the circumference of the circle is scaled by the formula C s = C 0 × ( s + 1 ) C_s = C_0\times (s+1) , where s s is the number of steps made (so after the first step the circumference is now 200, after the second step the circumference is 300, etc.),

which of the following gives the best (i.e. most accurate) approximation to the number of steps needed to complete the task?


Note: If you think that the task will never be completed, then answer \infty . Also, the x \left \lfloor x \right \rfloor is the usual floor function.

e 10 \left \lfloor{e^{10}}\right \rfloor e 100 \left \lfloor{e^{100}}\right \rfloor e 1000 \left \lfloor{e^{1000}}\right \rfloor e 10000 \left \lfloor{e^{10000}}\right \rfloor \infty

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Patrick Bourg
Dec 13, 2017

Relevant wiki: Harmonic Series

Let us note that, after the first step, before the circle's circumference is doubled, we have completed 1/100 of the required distance. After the radius is doubled, we note that this percentage does NOT change! Indeed, the new distance is then 200 units, but the already completed distance has been scaled accordingly as well and is of 2 units! Therefore, their ratio stays invariant! Of course, for any subsequent steps, this quantity will remain invariant. In other words, after the first step, we have completed 1/100th of the distance, irrespective of how the circle is scaled!

Now, the second step contributes to half what the first step was worth, that is: 1/200, or (1/2)/100. Again, by the argument above, this is scaling invariant. And so, after the second step, we will have completed: 1/100 + (1/2)/100 of the task.

It is now easy to see where this is going and in general, after the nth step, we will have done: 1 100 + 1 / 2 100 + 1 / 3 100 + + 1 / n 100 H n 100 \frac{1}{100} +\frac{1/2}{100} + \frac{1/3}{100} + \cdots + \frac{1/n}{100} \equiv \frac{H_n}{100} where H n H_n is the familiar harmonic series: H n = 1 n 1 k H_n = \sum_1^n \frac{1}{k}

The question is then, what is the smallest n such that H n 100 1 \frac{H_n}{100} \geq 1 or H n 100 H_n \geq 100 ?

One quick way to go about this is using the fact that H n log ( n ) H_n \approx \log(n) and therefore n e 100 n \approx e^{100} .

A more formal approach is to note the inequality : log ( n + 1 ) < H n 1 + log ( n ) \log(n+1) < H_n \leq 1+\log(n) Picking H n 100 H_n \approx 100 , we find that n ( e 99 , e 100 1 ] n \in (e^{99} , e^{100}-1] and again we see that n e 100 n \approx e^{100} is the best approximation.

The radius of the circle is 100, so its circumference is 2 π 100 = 200 π 2 \pi \cdot 100 = 200 \pi . This means the first step covers 1 200 π \frac{1}{200 \pi} of the total distance, the second step covers 1 2 200 π \frac{1}{2 \cdot 200 \pi} , and so on. Your numbers are off by a factor of 2 π 2 \pi .

Jon Haussmann - 3 years, 5 months ago

Log in to reply

Indeed! Thanks a lot of the remark. I have updated the problem accordingly.

Patrick Bourg - 3 years, 5 months ago

Log in to reply

Why change it? you defined the original circumference as 100 unite, not the radius. Ed Gray

Edwin Gray - 3 years, 5 months ago

Log in to reply

@Edwin Gray This problem was created 2 weeks ago and he originally said radius instead of circumference as the 7th word

Dylan Wedel - 3 years, 5 months ago

Log in to reply

@Dylan Wedel They should have it say the last date it was modified with a short desc of it when hovered so discussions like this don't come up.

jacki kay - 3 years, 5 months ago

It says "circle with a starting circumference of 100 units" so you are wrong in that regard.

jacki kay - 3 years, 5 months ago

Log in to reply

This problem was created 2 weeks ago and he originally said radius instead of circumference

Dylan Wedel - 3 years, 5 months ago

I strongly dissent, the probability of hit a predetermined point inside the circle is 1/ divided by infinite no matter if circle increase in size. Remenber the steps can be taking in any direction it not the case of a dotted circle.

Mara Jares - 3 years, 5 months ago

Log in to reply

I think you misunderstand the problem. You are walking in one direction along the edge of the circle, not randomly inside of it.

Alex Li - 3 years, 5 months ago

Log in to reply

It maybe the case but the reading says " Suppose you start on a point on that circle and proceed to walk along it until you go back to your starting position." it should say on the edge of the circle or better on the circumference and dismiss the word circle at all.

Mara Jares - 3 years, 5 months ago

Log in to reply

@Mara Jares I don't agree. A circle is a one-dimensional object only made up of its circumference (so to speak). Unlike a disk, which includes the inside. Stating that you walk on/along the circle hence leaves only one option as to what path can to be taken. I will try to be more careful with my wording next time though. Thanks for the comment.

Patrick Bourg - 3 years, 5 months ago

The question asks the number of steps to return to the starting point, i.e. hitting the exact point where the walk began. This requires H n = 100 H_n = 100 , which does not have a solution since H n H_n is always a non-integer for n > 1 n>1 . So, the correct answer should have been \infty .

Samrat Mukhopadhyay - 3 years, 5 months ago

Log in to reply

I agree! For 1 unit travelled, you create 100 additional units to travel.

That is, unless i completely missed what is meant here?

jacki kay - 3 years, 5 months ago

Log in to reply

That's not the case, but I agree, the question wasn't stated very well. When they said the circle is scaled, it's scaled about your current position. So if you were 1 unit in, and then the circle is scaled to 2(100), you are then 2 units in, and 198 units out. Notice, you're not creating 100 more units to travel for each step, that's 99. If you try more numbers, you'll see the distance necessary to travel becomes smaller and smaller (in fact, the distance is first multiplied by 2/1, then 3/2, 4/3, 5/4, etc, which converges towards 1, thus making the trip possible). Once it goes below 1, you can simply start making your way to the end without creating for steps to walk. Hopefully that makes sense.

Kevin Tong - 3 years, 5 months ago

Log in to reply

@Kevin Tong That's a good explanation

Dylan Wedel - 3 years, 5 months ago

@Kevin Tong I am not certain to agree. By definition of scaling, the distance between any two points is scaled by the appropriate factor (assuming a "homogenous" scaling, which is the case here). So you could scale about any point you want (even outside the circle). Usually, one should think of it about the center for symmetry/intuition though.

Another way I look at this (without referring to coordinates) is that a circle is a one-dimensional manifold. Up to a point on the circle, it is topologically equivalent to a line. Now, when we talk about scaling a line, it should be clear geometrically that it is like "stretching" the line. There is no "reference point" from which it is scaled.

Patrick Bourg - 3 years, 5 months ago

I found my "mistake", although I still think it is very ambiguous. I didn't think about that somehow my steps scale as well. The problem this way is HIGHLY unrealistic. Each step should be scaling only the circumference of the shape I am walking, not space behind me (formulated badly). I understand that they wanted to trick people into thinking of infinity, but that's not a very brilliant thing to do.

jacki kay - 3 years, 5 months ago

you should know,if (lim n →∞),Hn is a divergent series(p series,p=1). it means that there must be a value of n exist(the answer is that it is close to e^100) makes the value of Hn equal to 100.So you can complete this circle. Just like, lim n → ∞,Tn=1/2+1/4+1/8+.....1/(2^n).Tn equals 1. 100/100,you can also complete this circle.That's my opinion.

Cursx Tian - 3 years, 5 months ago

Log in to reply

H n H_n cannot be ever an integer for n 2 n \ge 2 . So your argument is not correct. Also, if you plot the values of H n H_n against n n it is going to be a staircase type function with lots of gaps in its values, and all the integers reside in those gaps.

Samrat Mukhopadhyay - 3 years, 5 months ago

I foolishly answered that it was not possible.. however realised later that distance covered in my first step would double too.. however my math deserted me right here !!😊

AK Shama - 3 years, 5 months ago
Kevin Tong
Jan 3, 2018

Before beginning the explanation, I want to point out that the question wasn't stated very clearly, although it can be easily understood nonetheless. Let's first consider what it means to scale the circle. In order to scale it, we must have a point to scale it about (not necessarily the center). If we were to scale it at any point other than our current position, we would end up inside of the circle since the surface would be scaled away from where we were (unless we were scaled it with). Thus, we can reasonably conclude that we are scaling the circle about our current position. Now we can begin the problem.

Let's start off observing what happens each time we take a step. After the first step before the scaling, we are 1 unit in, 99 units to go. After scaling, both our distance traveled and distance left are scaled by a factor of 2 1 \frac{2}{1} . Thus, we have 198 units left to go by that point. Since we only care about the distance left to go, we only need to pay attention to that. The main problem when solving this is the factor by which we scale the circle by each time. Since we're adding 100 units to the circumference of the circle, the factor we multiply by is C + 100 C \frac{C+100}{C} , which, as C gets larger, converges to 1. Thus, we now know the answer cannot be infinity since the factor converges.

Now let's setup an equation of what this would look like: After the first step and scaling, we have 2 1 ( 100 1 ) \frac{2}{1}(100-1) ; After the second step and scaling, we have 3 2 ( 2 1 ( 100 1 ) 1 ) \frac{3}{2}(\frac{2}{1}(100-1)-1) ; After the third step and scaling, we have 4 3 ( 3 2 ( 2 1 ( 100 1 ) 1 ) 1 ) \frac{4}{3}(\frac{3}{2}(\frac{2}{1}(100-1)-1)-1) . Notice, when we expand this, the fractions being multiplied to 100 1 = 99 100-1=99 cancel out to simply n + 1 n+1 and the 1 -1 s are multiplied by a partial sum of the harmonic series multiplied by n + 1 ) n+1) . In other words, the distance left to travel can be modeled by the formula 99 ( n + 1 ) ( n + 1 ) k = 2 n 1 k = ( n + 1 ) ( 99 k = 2 n 1 k ) 99(n+1)-(n+1)\sum_{k=2}^{n}\frac{1}{k}=(n+1)(99-\sum_{k=2}^{n}\frac{1}{k}) We want to find when this is equal to zero, thus, we can divide n + 1 n+1 on both sides, and we end up with 99 k = 2 n 1 k = 0 100 H n = 0 H n = 100 99-\sum_{k=2}^n \frac{1}{k}=0 \implies 100-H_n=0 \implies H_n=100

Now, we want to find the nth harmonic series such that it is greater than or equal to 100. To do this, notice that the harmonic series can be modeled by the function f ( x ) = 1 x f(x)=\lfloor \frac{1}{x} \rfloor . Now, notice 1 x + 1 < f ( x ) 1 x \frac{1}{x+1}<f(x)\leq \frac{1}{x} . Thus, we know that the sum of the harmonic series is between the integrals of the two other functions, namely, 1 n 1 x + 1 d x < 1 n f ( x ) d x 1 n 1 x d x ln ( n + 1 ) ln ( 2 ) < H n ln ( n ) ln ( n + 1 ) ln ( 2 ) < 100 ln ( n ) n e 100 \int_{1}^{n}\frac{1}{x+1} dx < \int_{1}^{n} f(x) dx \leq \int_{1}^{n}\frac{1}{x} dx \implies \ln(n+1)-\ln(2)<H_n\leq \ln(n) \implies \ln(n+1)-\ln(2)<100\leq \ln(n) \implies n\approx \boxed{\lfloor e^{100} \rfloor}

Can anyone explain the answer to me. If I neglect the fact thats this is a circel (which should not matter i presume) and see the problem as a 100 meter long track having a finish-flag at the end. It seems to me that every time i take a single 1-meter step someone plants the flag 100 meters farther away; adding more meters to the track than i made up for. And this happens 'every single 1-meter step i take!' The steps needed to finish a track that forever grows more than i travel could not logically converge to anything other than infinity to me. Please enlighten me !!!

V P - 3 years, 5 months ago

Log in to reply

That's because the flag isn't put 100 meters farther from you, but from your starting point, which is also being put farther from you with each step.

After your first step, you've covered 1 1 % of the track. The track then "scales up", which essentially means the road in front of you lengthens, but so does the road behind you. So for your second step you'll still be positioned at the 1 1 % mark on the track. Continuing in this fashion, your second step takes you 1 2 \frac{1}{2} % forward on the track, your third - 1 3 \frac{1}{3} % and so on. Since the harmonic series diverges, this should convince you you will indeed at some point reach the 100 100 % mark, and hence complete the race.

Ivo Zerkov - 3 years, 5 months ago

Log in to reply

Aha. That did it. I was even wondering why they didn't just write 'add' instead of that long-winded scaling formula. I thank you in slight embarrasment sir.

V P - 3 years, 5 months ago

In a very similar fashion of other solution posted, I assumed that goal was to cover a 2π path but in our mission our steps are reduced following the sequence 1/2 ; 1/3 ; 1/4 and so on. Since our initial step is 2π/100 to achieve our goal we must perform N steps so

2π/100 ( 1+1/2+ 1/3+ …. 1/N) = 2π; simplifying ( 1+1/2+ 1/3+ …. 1/N) = 100

So N will be the term of the Harmonic Series which balance the above equation. It is well known since Euler for large number the Harmonic Series can be approximated by Ln (N) plus γ the Euler Constant. Since the answer is a multiple choice the closest is indeed e^100

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...