Caught In A Circle
You are trapped in the center of a flat circular area of radius 1000 by an evil maniacal tyrant. You have to walk out by taking steps of size 1. However, for each step, you can only choose the direction to walk in, and the tyrant will dictate if you move in the positive or negative direction.
What is the minimum number of steps you need to take to guarantee that you can reach the circumference ?
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.
2 solutions
Great! The basic idea is that you want to increase your distance from the center of the circle. This approach can be described as "Pick the vector such that the minimum distance that that you move from the center, is maximized". Phrased like this, it becomes the obvious choice of what to do.
We then have to fill in the details and do the calculations, to see how things turn out.
Log in to reply
"Pick the vector such that the minimum distance that you move from the center, is maximized" is the whole crux of the solution. Very concisely put.
Based on what I understand from the question, if i try to move right 1 step, the evil man could make me walk 1 step left instead. So, he could just make me stay in a circle of radius 1 from the center. So, he would not be able to get out. Or did I not understand the question?
Log in to reply
If you just think about the first two steps, it should be clear how movement outside r=1 is possible. Step 1: move left or right 1 unit (equivalent). Step 2: move up or down 1 unit (also equivalent). After the second step, you're at r=sqrt(2).
I do't understand this statement " regardless of what the evil maniacal-but-powerless-to-sway-your-progress tyrant says ". He is basically controlling the no. of steps to reach the circumference . The exact answer of the problem depends on that evil guy.
Log in to reply
No, as long as you always choose a direction that's perpendicular to the radius, regardless of which way the tyrant wants you to take, "positive or negative", your advancement towards the circumference is exactly the same either way. I'll post a graphic shortly to illustrate.
Edit: See my graphic and explanation added to my original answer.
Good one! This was my approach too.
This doesn't prove that 1 0 6 steps is necessary, only that it's possible.
Log in to reply
Calvin did put in the word "guarantee", which is asking for the maximum that could be required.
Log in to reply
Yes, assuming you use the best strategy. You proved that this strategy will reach the circumference in 1 0 6 steps. You haven't proven that there is no strategy that can reach the circumference in less steps.
Log in to reply
@Ivan Koswara – Now I'm in the funny position of having to prove that Calvin's argument about the minimum possible advance being maximized is a proof! But, okay, I'll see if I can offer something more rigorous, before you beat me to it.
Log in to reply
@Michael Mendrin – There is a very simple way to make this argument rigorous. As I stated, "Pick the vector such that the minimum distance that that you move from the center, is maximized". Now, the main issue is that we have to justify why the greedy algorithms works, as opposed to started out with a sub-optimal solution. IE Why locally optimizing leads to a globally optimal result.
This is almost obvious. As we realized, the important detail of our current position is simply the "distance from the center". Consider the following
-
At step n , if we are distance r n from the center, then the maximum of the minimum of where we are for step n + 1 will be r n + 1 = r n 2 + 1 .
-
At step n if we are distance r n ≤ n from the center, then the maximum of the minimum of where we are for step n + 1 will be r n + 1 ≤ n + 1 .
Hence, this establishes that r n ≤ n , and so we will need at least 1 0 0 0 2 steps.
Log in to reply
@Calvin Lin – Your point 1 is not so trivial to prove (even if it's still pretty easy), hence why I said this solution is not complete yet.
Log in to reply
@Ivan Koswara – Yes, I agree that the Michael current solution is incomplete. From his previous comment, I was under the impression that he had difficulty filling in the gap. That's why I replied with "There is a very simple way to make this argument rigorous", with the subtext from your comment of "You haven't proven that there is no strategy that can reach the circumference in less steps."
Log in to reply
@Calvin Lin – there is no way to reach the center from the circumference, right?
Log in to reply
@Mehdi K. – Right, because any direction you choose at the beginning, Mr Evil can always force you away further away from it.
@Calvin Lin – Let's not forget that this being a multiple choice question, after having proven that 1 0 6 would work, the only alternative less than this is 1 0 3 , which means from the center is a path straight out to the circumference. Mr Evil can easily up the number from this, and so the "solution" offered is sufficient to prove that choice 1 0 6 is the correct one.
Log in to reply
@Michael Mendrin – Let's not succumb to "this being a multiple choice question". Thanks!
It is possible that for every 4 steps, I can (or he can force) come to center of circle. From center if I give direction Step1-horizontal either left or right, let's assume right Step 2 -vertical either down or up, let's assume up Step 3 - horizontal, now left Step 4 - vertical, now down
Log in to reply
There are infinitely many directions in which you can move not just four.
Log in to reply
Yes what I am saying that process may be repeated for every 4 steps like what I mentioned, for simplicity I used horizontal and vertical directions. By that for 4 or 8 or 12 or so many ... I will be at same point i.e center of circle, there is no point of escape.
"regardless of what the evil maniacal-but-powerless-to-sway-your-progress tyrant says." (+1)
Perfect solution Sir!! Simpler than I thought It would be, and a great question too!!
Minimum number of steps is r 2 = 1 0 6
Can you explain in detail?
Log in to reply
Yes sir, I will provide more explanation later, is that ok?
Log in to reply
Sure, look forward to reading it.
Log in to reply
@Calvin Lin – I hope it is correct, the surface area of a dome is half of that of the sphere which is equal to 2 π r 2 . The tyrant is going in circles. We know that one circle is 2 π , so the steps needed to get to the perimeter of the dome is 2 π 2 π r 2 = r 2 .
Log in to reply
@Hana Wehbi – Nope, nothing to do with the dome. Let me remove that from the question completely.
Log in to reply
@Calvin Lin – Ok, i will keep squeezing my brain. Don't worry, i will come up with the right solution but right now, i am a bit tired. I wrote my problems for the writing party under the community page. Nice problem too.
@Calvin Lin – I like the new problem, but if anybody read my solution is going to say " what is she talking about?" By taking the dome out.
@Hana Wehbi – I meant the minimum number of steps, i am solving from my ipad, it is hard to edit :(
Relevant wiki: Circles Problem Solving - Basic
In worst case scenario, you start at the center. After your first step, you always choose the direction that is perpendicular to the line from where you are to the center. Hence, you will inexorably move towards the circumference with each step, regardless of what the evil maniacal-but-powerless-to-sway-your-progress tyrant says. Your distance from the center after n steps is n , so the answer is 1 0 6 . Stack a bunch of right triangles together to see how this works out, of successive hypotenuses of 2 , 3 , 4 , . . . etc.
If you are at distance n from the center, and you move a distance of 1 perpendicularly either to the right or left, then, using Pythagorean's Theorem, your new distance is n + 1 .
Note that, for example, once you have reached point C , regardless of what the tyrant says, you'll end up either at D or D ′