13
$\begingroup$

In the spirit of wizards and circular prisons:

You have been imprisoned by an evil wizard in a perfectly circular prison cell of unknown size. You're shackled to the wall, unable to move about the cell.

Fortunately, the wizard isn't so evil that he won't give you at least one opportunity to escape. He tells you that if you can compute the area of the prison cell exactly (that is, deterministically, and to arbitrarily high precision), he'll let you go free.

To help you accomplish this task, he's given you three flying monkey drones, Arthur, Bob, and Dale, and a set of teleportation spells you can use as often as you like:

  1. Teleport any drone to your location (you can pick which drone).
  2. Teleport yourself to Arthur or Bob's location (you can pick which drone).
  3. Teleport yourself to a random location on the prison wall. (You remain unable to move even after teleporting. Also, you never teleport to exactly the same location twice.)

Conveniently, if you pull on Arthur's tail, he will tell you exactly what the shortest angle $\theta$ between himself and Dale is, as shown below.

If you pull on Dale's tail, he will tell you exactly what the distance $d$ between himself and Arthur is, as shown below.

                               measuring distance and angle

There are three restrictions on measurement, however:

  1. You must be exactly at a drone's location to pull his tail.
  2. After you have teleported a drone to your location, you cannot pull his tail until you have teleported at least once.
  3. You cannot measure both $d$ and $\theta$ across the same pair of points (even in reverse).

All three drones start at your location on the wall, which is unknown. You may assume that you have a perfect memory, and that you can compute any mathematical function to arbitrarily high precision.

Are you able to escape? And how?


Note: Generally speaking, I'm looking for a solution that

  1. has 100.0% probability of being correct (not e.g. a probability of correctness that approaches 1 asymptotically)
  2. has finite $E\left[ n\right]$, where $n$ is the RV describing the number of steps needed to reach a solution
$\endgroup$
  • 2
    $\begingroup$ Why would one want to escape the coolness of flying monkey drone companions? $\endgroup$ – JLee Jun 13 '15 at 12:18
  • $\begingroup$ @JLee: Well... they do poop a lot. :P $\endgroup$ – COTO Jun 13 '15 at 14:54
  • $\begingroup$ A drone named "Bob" is referenced briefly in the question, but not in the diagrams nor in the instructions for tail-pulling; the drone "Dale" appears to be unable to move at all as he is not in the list of teleportation spells. I can guess that this is a typo but I don't know what the answers to those should be, or whether Dale will report distances between himself and Bob as well as himself and Arthur. $\endgroup$ – lorimer Jun 16 '15 at 16:06
  • $\begingroup$ @lorimer: "Bob" is just a marker buoy that can teleport and be teleported to. I had originally named the drones "Buoy", "Angle", and "Distance" when I worked out the problem, but changed these to "Bob", "Arthur", and "Dale", respectively. $\endgroup$ – COTO Jun 17 '15 at 3:59
1
+200
$\begingroup$
  1. Start at A
  2. Go to random B
  3. Call Arthur to B
  4. Go to Bob at A
  5. Get $\overline{AB}$
  6. Go to Arthur at B
  7. Call Bob to B
  8. Go to random C
  9. Call Arthur to C
  10. Go anywhere
  11. Go to Arthur at C
  12. Get $\angle{AC}$
  13. Go to Bob at B
  14. Call Dale to B
  15. Go anywhere
  16. Go to Bob at B
  17. Get $\overline{BC}$
  18. Go to Arthur at C
  19. Call Bob to C
  20. Go to random D
  21. Call Arthur to D
  22. Go anywhere
  23. Go to Arthur at D
  24. Get $\angle BD$
  25. If $\angle{BD}$ sucks, forget point D and goto step 20
  26. Go to Bob at C
  27. Call Dale to C
  28. Go anywhere
  29. Go to Bob at C
  30. Get $\overline{CD}$

$\overline{AC}^2=\overline{AB}^2+\overline{BC}^2\pm2\times\overline{AB}\times\overline{BC}\cos\frac{\angle{AC}}{2}$, giving two possibilities for radius $r=\frac{\overline{AC}}{2\sin\frac{\angle{AC}}{2}}$, one of which can be confirmed by solving the triangle $BCD$ in the same way.

At step 25, $\angle{BD}$ sucks with probability 0, but we can still guarantee a solution in a finite number of steps against an adversarial teleporter because only four sucky locations exist. The geometry of sucking is left as an exercise for the reader.

$\endgroup$
  • $\begingroup$ You'll have to clarify how to translate the measurements into an area before I can check your solution. $\endgroup$ – COTO Jun 17 '15 at 17:14
  • $\begingroup$ Excellent! Very close to my own solution. Specifically, it relies on the somewhat obscure fact about circles: i.stack.imgur.com/15Gh0.png. Note that you should change step 29 to "go to Bob at C" since you can only teleport to Bob, even though Dale is there with him. Also, as a formality, please put in the formula for computing the possible $r$'s from $\angle{AC}$ and $\overline{AC}$, and the bounty is yours. :) $\endgroup$ – COTO Jun 18 '15 at 0:37
  • $\begingroup$ Very nice! While I had hoped there was such a convenient relationship, I was not aware of one and couldn't find it. $\endgroup$ – frodoskywalker Jun 18 '15 at 11:37
6
$\begingroup$

Remark: This is not a complete solution. See the edit below.

Yes, it is possible to escape, using the following sequence:

  1. Teleport Dale to your location
  2. Teleport to a random location
  3. Teleport Arthur to your location
  4. Teleport to a random location
  5. Telport to Arthur
  6. Pull Arthur's tail, receiving a measurement $A$.
  7. Teleport Bob to your location
  8. Teleport to a random location
  9. Teleport Arthur to your location
  10. Teleport to Bob's location
  11. Teleport to Arthur's location
  12. Pull Arthur's tail, receiving a measurement $B$
  13. Teleport to Bob's location
  14. Teleport Dale to your location
  15. Teleport to Arthur's location
  16. Teleport to Bob's location
  17. Pull Dale's tail, receiving a measurement of $d$

enter image description here

This is depicted in the image above. Your initial location is marked with $0$, the first random place you teleport to is marked with $1$, and the third random place you teleport to is marked $3$. The angle subtended by the chord of length $d$ is $2\pi-A-B$, the radius of the room is $$ \frac{d}{2\sin\left(\frac{2\pi-A-B}{2}\right)}, $$ and the area of the room is

$$\pi\left(\frac{d}{2\sin\left(\frac{2\pi-A-B}{2}\right)}\right)^2.$$

Edit: As pointed out in the comments, the situation could be different depending on the relative locations of teleportation. The picture might also look like the following: enter image description here

In this case the angle subtended by the chord of length $d$ is $B-A$, and the area of the room is

$$\pi\left(\frac{d}{2\sin\left(\frac{B-A}{2}\right)}\right)^2.$$

The difficulty is, without some knowledge of the relative positions of teleportation locations, we cannot know which formula to use.

$\endgroup$
  • $\begingroup$ Curious. Does it work if all three points lie on the same half of the circle, however? $\endgroup$ – COTO Jun 13 '15 at 11:33
  • $\begingroup$ You are not allowed to teleport to Dale's location in step 16, unless that is a typo in the question. $\endgroup$ – Trenin Jun 16 '15 at 16:16
  • $\begingroup$ @Trenin But replace "Dale" with "Bob" and the strategy still works. $\endgroup$ – Edward Jun 16 '15 at 16:41
  • $\begingroup$ @Edward Ha! Didn't notice they were in the same location! Thanks! $\endgroup$ – Trenin Jun 16 '15 at 16:41
  • $\begingroup$ @COTO It does. There's nothing in the math that relies on the triangle enclosing the circle's center. $\endgroup$ – Edward Jun 16 '15 at 16:44
5
$\begingroup$

Based on Julian's solution, I came up with the following. Mostly I just added in the repeat-as-necessary at the end to determine which calculated radius is the correct one.

  • Teleport to Random Location: Point 1.
  • Summon Dale.
  • Summon Bob.
  • Teleport to Random Location: Point 2.
  • Summon Arthur.
  • Teleport to Bob's Location (which is also Dale's location).
  • Pull Dale's tail. This gives you the distance between points 1 and 2.
  • Teleport to Arthur's location.
  • Summon Bob.
  • Teleport to Ransom Location: Point 3.
  • Summon Arthur.
  • Teleport to Bob's location.
  • Teleport to Arthur's location.
  • Pull Arthur's tail. This gives you $\angle 13$.
  • Teleport to Bob's location.
  • Summon Dale.
  • Teleport to Arthur's location.
  • Pull Arthur's tail. This gives you $\angle 23$.

As indicated in Julian's answer, there is ambiguity as to whether $$\angle 12 = 2\pi - (\angle 13 + \angle 23)$$ or $$\angle 12 = (\angle 13 - \angle 23)$$

Calculate the radius of the circle for both cases. One is correct, the other is not.

Repeat the entire process. One calculated radius from each measurement should match one from the other. That is the true radius. There is a vanishingly small chance that the incorrect radii would also match. Even if they do, repeat the whole process again.

Once you have the radius, calculating the area is straightforward.

$\endgroup$
  • $\begingroup$ I'll award you the bounty in six days provided i) Julian's answer doesn't inadvertently prove correct due to Moldovan's symmetry argument, and ii) no zero-error solution is provided. Generally speaking, I'm looking for a solution whose expected number of steps is finite, and whose probability of error is exactly zero. $\endgroup$ – COTO Jun 17 '15 at 4:18
  • $\begingroup$ My only improvement of Julian's answer is the retry, so I'm fine either way. $\endgroup$ – user3294068 Jun 17 '15 at 13:43
2
$\begingroup$

This gets a bit odd, and assumes something about the rules.

My algorithm is:

  1. Identify starting point as point A
  2. Teleport at random (to point B).
  3. Summon Dale.
  4. Pull Dale's tail, revealing distance AB (call it a).
  5. Summon Arthur.
  6. Teleport at random (to point C).
  7. Summon Dale.
  8. Pull Dale's tail, revealing distance BC (call it b).
  9. Summon Arthur.
  10. Teleport back to Bob.
  11. Summon Dale.
  12. Pull Dale's tail, revealing distance CA (call it c).
  13. Calculate the diameter of the circumscribed circle (the circle that touches all three points on the triangle, which were all on the wall) according to the formula:

    diameter = 2abc / sqrt((a+b+c)(-a+b+c)(a-b+c)*(a+b-c))

  14. Multiply the diameter by Pi for the area of the circle.

  15. Escape.
  16. Profit.

The formula for the diameter is explained in great detail at https://en.wikipedia.org/wiki/Circumscribed_circle

$\endgroup$
  • $\begingroup$ Unfortunately you can't pull Dale's tail in steps 4,8,12 because you haven't teleported since summoning him. I was thinking along these lines and hit the same snag. $\endgroup$ – frodoskywalker Jun 17 '15 at 15:00
  • $\begingroup$ The trivial solution to this would be to teleport to Bob and then back to Dale and pull his tail. That satisfies the letter of the law, not sure about the spirit of it. COTO? $\endgroup$ – Carmi Jun 17 '15 at 16:04
  • $\begingroup$ That satisfies the spirit of the law, but not the letter. You can't teleport to Dale. $\endgroup$ – frodoskywalker Jun 17 '15 at 17:00
  • $\begingroup$ @Carmi: You can teleport from X to Y back to X again to satisfy the tail pulling rule at X, but as frodo points out, you can't teleport to Dale. $\endgroup$ – COTO Jun 17 '15 at 17:17
0
$\begingroup$

My answer assumes a few things about the situation that I must put forth:

  1. Although I may not move throughout the prison I am able to move my arms as I can pull the tails of the drones but have no "pull" spell.
  2. The drones are flying and therefore their mass does not matter when moving them.
  3. The drones fly low enough for me to grab them, as I can pull their tails.
  4. The drones will accept actions I take upon them as they allow me to pull their tails.

With these assumptions this is my answer:

  1. push Arthur as far from me as possible in what appears to be the direction of the far side of the wall.
  2. Teleport to Arthur.
  3. Repeat steps 1 and 2 until we reach a wall.
  4. Use two pieces of clothing torn from my garments pulled taught to make a line that is perpendicular to the line connecting two points on the circumference (one piece is on two points, the other placed perpendicular to it)
  5. Push Arthur out to tip of perpendicular piece of clothing
  6. Teleport to Auther and pull his tail
  7. If result is not 180 degrees move clothing and Arthur untill answer is 180 degrees. Teleporting to Arther each time to pull.
  8. Push Arther along perpendicular cloth until he is against the wall.
  9. Teleport to Bob
  10. As bob and Dale are in the same place pull Dale's tail
  11. I now have the diameter of the circle and can calculate the area as A = (d/2)*pi^2
$\endgroup$
-2
$\begingroup$
ok, let try this for minimal Blinkage:
Blink to somewhere random
summon dale
summon bob
Blink to art
YANK! (i can has angle now)
Blink to bob (quik cause arts gonna bite i'm sure)
YANK! (i can has a chord now, B#!)
Blink away from dale (again avoiding the aforementioned consequence)
now i can do my math,
you can calculate the radius as you now has an isosceles triangle
call the center of the room c
angle AcD and dist AD are known
angles cDA and cAD are equal to (180-AcD)/2
call midpoint AD as m
again use symmetry to get angles Dcm and Adm as 90-AcD
i can has a right triangle and all the angles is now knowed
Ac = Am/sin(Acm)
and the area is (Ac)^2
lemme go!
if i was a masochist i could do it with one less blink
but then maybe i wouldn't wanna leave...
$\endgroup$
  • $\begingroup$ sry, broke rule 3 cause i didn't read rulez... $\endgroup$ – BurgercheeseCanHasI Jun 10 '16 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.