wpt@princeton.UUCP (William Thurston) (10/17/86)
John Conway is at Princeton this year, and he has a great stock of interesting questions. Here is an unsolved problem: Imagine a universe consisting of planets arrayed at the grid points of an infinite plane. On one of the planets, an angel is sitting. Every day, the angel can fly off to another planet, but the angel's range is limited to a distance of (say) 100. Unfortunately, there is a devil in the universe. Every day, the devil can destroy a planet, anywhere in the universe. Can the angel forever avoid being trapped? Bill Thurston ...!princeton!wpt
nair@unc.UUCP (Anil Nair) (10/20/86)
Does anyone remember the article on Core Wars in one of the Computer Games column in Scientific American . That had a similar problem played on a 1-dimensional array . For practical purposes , they had a finite circular array ; but you can think of a conceptual infinite one dimensional array . The angel and devil would be two programs on the array playing a particular strategy . Drawing the analogy to this situation , you can have other strategies for the angel and the devil in this matrix . I am sorry , but I don't have an answer as to who will win even in the 1-dimensional case . If I remember right , the article had statistical info on who wins most of the time . Anil Nair - UNC
kaden@osiris.CSO.UIUC.EDU (10/20/86)
Pick square region N. Then sufficiently, 400Nd <= N/2 d <= 1/800 would work. However, d = 100 is not --> zero.
wpt@princeton.UUCP (William Thurston) (10/21/86)
Since there hasn't been much response yet to the angels and devils question
I posted a few days ago, I'll add a little more. The original question
is probably very difficult:
Imagine a universe consisting of planets arrayed at the grid points
of an infinite plane. On one of the planets, an angel is sitting.
Every day, the angel can fly off to another planet, but the angel's
range is limited to a distance of (say) 100.
Unfortunately, there is a devil in the universe. Every day, the devil
can destroy a planet, anywhere in the universe.
Can the angel forever avoid being trapped?
``Fools rush in where angels fear to tread''
There is a variation of the angel, called a fool, who, at the advice of the
hobgoblin of small minds, only travels forward through the stars:
the fool only travels in directions between north-east and north-west.
[Any resemblance to well-known people alive or dead is purely accidental.]
Find a strategy for the devil to trap the fool. Hint: for maximum jump-size
4*100*100
100, the devil needs no more than 2 rounds to trap the fool.
Bill Thurston ...!princeton!wpt
Mathematics Department
Princeton University
Princeton NJ 08544kevins@dartvax.UUCP (Kevin M. Schofield) (10/21/86)
In article <2056@princeton.UUCP> wpt@princeton.UUCP writes: >Imagine a universe consisting of planets arrayed at the grid points >of an infinite plane. On one of the planets, an angel is sitting. >Every day, the angel can fly off to another planet, but the angel's >range is limited to a distance of (say) 100. > >Unfortunately, there is a devil in the universe. Every day, the devil >can destroy a planet, anywhere in the universe. > >Can the angel forever avoid being trapped? After spending some time pondering this wonderful question, I concluded that the angel can indeed forever avoid being trapped. There are 2 ways that the angel could be trapped: 1. by walking into a "trap", i.e. a region completely enclosed except for 1 opening which the devil could remove in 1 turn. 2. by being completely enclosed by a wall on all four sides. Assuming the angel is intelligent, it will not "walk" on its own volition into a trap. Also, it is impossible for the devil to "force" the angel to move in any particular direction; thus we can forget about traps. Now still assuming the angel is intelligent, when it sees that a box is being constructed around it, it heads at full speed towards the perimiter of the box and then moves around it, it is not too difficult to prove that the angel can get to the perimiter and find an opening before the devil can complete the box. What seems like a much more interesting question is when the angel is limited to moves to adjacent grid points. I'm still working on this one, and any comments or suggestions would be appreciated... -Kevin -- ------------------------------------------------------------------------------- "There may be no heaven, but somewhere there is a San Francisco." Kevin M. Schofield '88 email: {decvax,ihnp4} !dartvax!kevins kevins@dartmouth.EDU U.S. Mail: College: H.B. 2908, Dartmouth College, Hanover, NH 03755 Real World: 1851 Vallejo Street, St.Helena, CA 94574 --------------------------------------------------------------------------------
jaw@aurora.UUCP (James A. Woods) (10/22/86)
# "Resist the devil, and he will flee" -- James 4:7
# "Philosophy will clip an angel's wings. " -- John Keats
# "The devil is an angel too." -- Miguel de Unamuno (1864-1936)
The one-dimensional case is easy; the devil picks a sufficiently large
distance from the angel at the initial point, methodically destroys
100 planets in a line, watches the angel hop wherever she pleases, repeats
the same on the other side, then entraps her with a random squeeze between
the barriers.
For the n-dimensional case, we defer to the intriguing exercise in
Berlekamp, Conway, and Guy's "Winning Ways, part 2 (Games in Particular)".
Conway, et. al., teases us with a claim by T. Koerner that the angel
can escape on the hypercube, but how this might apply to 2D is nebulous.
This kind of result has the flavor of the Poincare Conjecture, where higher
dimensional results trickle in first (Smale, n>=5, Freedman, n=4, ?, n=3).
[Mr. T -- do you believe this has been fully resolved?]
The book by Berlekamp (world's Dots-and-Boxes champ, among other things),
Conway (poser, and part solver of the computation-universality of Life),
and Guy (Alpine climbing Sprague-Grundy theorist), is highly recommended
for its refreshing style, and merits discussion in the likes of Scientific
American's Mathematical Recreations.
-- James A. Woods (ames!jaw)btb@ncoast.UUCP (Brad Banko) (10/22/86)
Of course the angel can always avoid being trapped... it is sort of like that game where you chase each other around a computer screen trying to cut each other off... (see also, Tron motorcycle races (?))... perhaps a (an) intuitive stategy would be to just continue moving away from the center of mass (nonmass) of the destroyed planets... what can a devil possibly do? As long as the angel has a range of 100 and the devil can only destroy one planet per day... Yes, it does seem to get more interesting if you change the rules... angel gets a range of R, and devil can destroy N planets per day... (less than N=8, with R=1, right?)... Ah, this side of Paradise... Brad Banko Cleveburg, Ohio -- Bradley T. Banko
td@alice.UucP (Tom Duff) (10/23/86)
>Of course the angel can always avoid being trapped... it is sort of like >that game where you chase each other around a computer screen trying to >cut each other off... (see also, Tron motorcycle races (?))... perhaps a >(an) intuitive stategy would be to just continue moving away from the center >of mass (nonmass) of the destroyed planets... what can a devil possibly do? No such simple strategy can possibly solve this problem. The devil has too much mobility. This particular strategy is easy to break: The devil can maintain a configuration that's as close as possible to symmetric about the angel's starting point. On those moves where the devil is forced to off-balance the configuration, he can force the angel following this strategy to go any direction he wants -- in particular, he can keep him running around in small circles around the origin forever. Eventually, the devil will fill in a donut too wide for the angel to jump. The angel must come up with much more subtle strategy than this to win. If you think this problem is easy enough to rattle of a solution while following up netnews without thinking about it for a week or so, you're foolishly mistaken. If JH Conway doesn't know the answer, years after publishing the question, then it is surely an extremely difficult problem.
vis@mit-trillian.MIT.EDU (Tom Courtney) (10/24/86)
In article <5283@dartvax.UUCP> kevins@dartvax.UUCP (Kevin M. Schofield) writes: > >After spending some time pondering this wonderful question, I concluded >that the angel can indeed forever avoid being trapped. There are 2 ways >that the angel could be trapped: > 1. by walking into a "trap", i.e. a region completely > enclosed except for 1 opening which the devil could remove in > 1 turn. > 2. by being completely enclosed by a wall on all four sides. Remember that it has be a thick wall, since the angel can jump over walls thinner than its range. > >Assuming the angel is intelligent, it will not "walk" on its own volition >into a trap. Also, it is impossible for the devil to "force" the angel to >move in any particular direction; thus we can forget about traps. > Not clear. Suppose the devil could almost build a wall around the angel by force, and that the angel escaped by one move. Then its subsequent moves are being forced by the devil: he can't go back the way he came. >Now still assuming the angel is intelligent, when it sees that a box is >being constructed around it, it heads at full speed towards the perimiter >of the box and then moves around it, it is not too difficult to prove >that the angel can get to the perimiter and find an opening before the >devil can complete the box. > >What seems like a much more interesting question is when the angel is >limited to moves to adjacent grid points. I'm still working on this one, >and any comments or suggestions would be appreciated... An angel with a range of one casts doubt on your escape the box assertion. Imagine the following situation: ...W... ..W.W.. .W...W. W2.A..W .W1..W. ..W.W.. ...W... A = angel; W = wall the devil would like to build; . = undestroyed planet; 1 = edge position; 2 = corner position. If the devil could blow up all the W planets, the angel would be trapped. Can this situation be achieved? Yes. First, the devil starts by detonating planets on the wall. If the angel stays, it gets trapped, so it moves to escape the prison. Suppose it moves to a section of wall remarkably devoid of detonations (remember I didn't require the devil to be clever about the first two). There are two possibilities: either the angel hits an edge or a corner. If he hits a edge (1), the devil blows up a piece of wall in front of him. If he hits a corner (2), the devil blows up the vertice. When the angel enters the wall the devil blows up the piece of wall nearest the angel not already detonated. So let the angel go for the southwest wall (they are of course, symmetrical). At worst, the situation will now look like: ...DOOOOOW ..N.AOOOW. .N...DOW.. N.....W... .N...N.... ..N.N..... ...N...... O = old prison attempt; N = new prison attempt. D = destroyed planet. Going back into the old prison attempt must be wrong, so the angel enters the new prison attempt, and this one traps him. Its hard to explain, but easy to see: 1) don't detonate the entrance to the old prison attempt until the end; 2) detonate any section of wall the angel gets to; 3) Don't detonate a vertice unless an angel gets to it; 4) when the angel is not next to a wall, detonate edge planets not next to detonated planets. I think I should probably tighten up rule 4 by having the devil blow up non-adjacent planets the angel is moving towards, but 5 minutes with a pieces of graph paper and a pebble are sufficient to get the method down perfectly. Now on to the case where the range of the angel is 2! Well, first I'm going to work out the case where the angel gets 2 1 range moves per detonation. But that will be some other night.
stirling@fortune.UUCP (Patrick Stirling) (10/25/86)
As a reminder, the problem is: Planets arranged at the grid points on an infinite plane. An angel is on a planet, and can travel up to 100 planets' distance in a day. There is a devil who can destroy one planet anywhere each day. Can the devil trap the angel? > The one-dimensional case is easy; the devil picks a sufficiently large >distance from the angel at the initial point, methodically destroys >100 planets in a line, watches the angel hop wherever she pleases, repeats >the same on the other side, then entraps her with a random squeeze between >the barriers. > -- James A. Woods (ames!jaw) Surely this wouldn't work? The angel could travel parallel to the devil's destruction line faster than the devil can destroy planets, and thus escape out of the ends of the barriers. Picture: line of destruction: ----------------> line of escape: ================> line of destruction ----------------> I think the devil can only win if the angel doesn't know where he is, and if he can destroy enough planets to trap the angel before the angel realizes the situation (e.g by destroying a circle of planets around the angel). An analogous problem would be: Two people on an infinite flat plane, one with bricks and mortar. Can the builder build a wall around the other before the other can run away? I don't think so. patrick {ihnp4, hplabs, amdcad, ucbvax!dual}!fortune!stirling
btb@ncoast.UUCP (Brad Banko) (10/26/86)
Yes, thank you for the rejoinder to my "foolish" man's solution to Professor Conway's problem... by the way, is he a Princeton man? I envy the feeling of pride that having such a man back "home" brings... ok, so the simple strategy won't work... give me a week... I'll solve it... (maybe not) Thanks for the interesting problem to ponder. Brad Banko Cleveland, Ohio ...!decvax!cwruecmp!ncoast!btb -- Bradley T. Banko
mwm@eris.BERKELEY.EDU (Mike (Don't have strength to leave) Meyer) (10/27/86)
In article <126@fortune.UUCP> stirling@fortune.UUCP (Patrick stirling) writes: >As a reminder, the problem is: >Planets arranged at the grid points on an infinite plane. An angel >is on a planet, and can travel up to 100 planets' distance in a day. >There is a devil who can destroy one planet anywhere each day. Can >the devil trap the angel? Thank you. I'd missed the original problem. But you've got an ambiguity: Can the angel teleport, or does it have to traverse the intervening planets? If the latter, define "adjacent" for planets. >> The one-dimensional case is easy; the devil picks a sufficiently large >>distance from the angel at the initial point, methodically destroys >>100 planets in a line, watches the angel hop wherever she pleases, repeats >>the same on the other side, then entraps her with a random squeeze between >>the barriers. >> -- James A. Woods (ames!jaw) > >Surely this wouldn't work? The angel could travel parallel to the devil's >destruction line faster than the devil can destroy planets, and thus >escape out of the ends of the barriers. Key words: "one-dimensional case." The devil can actually do better in this case: Destroy 100 planets in a row, centered on the angels start point. Now, destroy one hundred planets in a row between 10,000 and 10,100 planets away from the angel in the direction away from the first patch of non-planets. <mike
bmg@mck-csc.UUCP (Bernard M. Gunther) (10/29/86)
> > As a reminder, the problem is: > Planets arranged at the grid points on an infinite plane. An angel > is on a planet, and can travel up to 100 planets' distance in a day. > There is a devil who can destroy one planet anywhere each day. Can > the devil trap the angel? > I know this probably isn't a total solution to the Angel and Devil problem and I'm not being rigorous, but this is a possible way of approaching the solution... Assumption: The problem is solvable in a one dimensional case. This is effectively a case where there is only a single row of planets stretching on to infinity. ie.: <--............A..................--> In this case, is is provable that the devil can trap the angel by building a single block of 100 anywhere and then building another block of 100 at least 100*100*2 spaces away and then slowly closing in on the angel. From this follows: In the case of a space consisting of 2 rows of planets, it is also possible for the devil to trap the angel. <--- ...............A.................... ---> .................................... This is done by building a block 100 unit wide and 2 deep and then building another block (100*100*2)*2 away from the first block and then slowly closing in. For a set of arbitrary number of rows, the two stopping blocks must be located (100*100*2)*N units away from each other. Therefore: since a two dimensional field is in reality just equivalent to the case where the number of rows (N) goes to infinity, the blocks must be built an infinite distance from each other and therefore, the angel cannot be trapped. I would be very interested to hear anyone else's comments on this solution. Bernie Gunther UUCP: {ihnp4, harvard, genrad, ...}!mit-eddie!mck-csc!bmg ARPA: bmg@mit-xx
gwyn@brl-smoke.ARPA (Doug Gwyn ) (10/30/86)
In article <188@mck-csc.UUCP> bmg@mck-csc.UUCP (Bernard M. Gunther) writes: >Therefore: since a two dimensional field is in reality just equivalent to >the case where the number of rows (N) goes to infinity, the blocks must >be built an infinite distance from each other and therefore, the angel >cannot be trapped. The fallacy in this reasoning can be schematized as: Method "A" works in the 1-dimensional case. One possible way of extending method "A" to the 2-dimensional case doesn't work. Therefore no method will work for the 2-dimensional case. For the conclusion to be valid, additional lemmas would be needed: No method other than "A" works in the 1-dimensional case. The way of extending method "A" to the 2-dimensional case is essentially unique. But these points weren't demonstrated and they're not obvious. I think this is a really hard problem, and intuitive approaches aren't likely to solve it. I suggest having a local mathematician check any proposed solution before posting it, to avoid wasting people's time.
jml@cs.strath.ac.uk (Joseph McLean) (10/31/86)
The original problem gave the angel a maximum of 100 planets in one jump each angel's move being in a single direction,i.e.in a single move the angel can't zig-zag.Let's generalise to the number of planets the angel is allowed to jump in a move as n.In the one-dimensional case the devil can trap the angel for all finite n.Thus we have the two-dimensional case. Can anyone give a strategy by the devil that will work whatever the angel does,for a particular n (that might not be 100) ? Or does the value of n matter to the eventual possible success or failure of the devil ? e.g.consider n=1.Is there an easy way for the devil to trap the angel ? Cogitate and masticate. jml,the thought-provoking mathematician. (Who are I kidding?)
trost@reed.UUCP (Bill Trost) (11/01/86)
I have a problem that is somewhat similar to this problem. Imagine quantity of hunters on a "very large" section of a plane (very large => boundary cases are neglibible). Now, each hunter shoots his nearest neighbor. Question: How many hunters remain living? This question can be put into the 3-dimensional and 1-dimensional cases as well. The 1-d case is fairly easy: half the hunters will get shot by one hunter, a fourth will get shot by two, and a fourth will survive. -- .signature, aka "Reed College", aka "tektronix!reed!trost"
stuart@BMS-AT.UUCP (Stuart D. Gathman) (11/03/86)
In article <188@mck-csc.UUCP>, bmg@mck-csc.UUCP (Bernard M. Gunther) writes: > For a set of arbitrary number of rows, the two stopping blocks must be > located (100*100*2)*N units away from each other. . . . > the case where the number of rows (N) goes to infinity, the blocks must > be built an infinite distance from each other and therefore, the angel > cannot be trapped. This proves that that particular algorithm for the devil won't work in the 2 dimensional case. You haven't proved that *no* algorithm exists to trap the angel. -- Stuart D. Gathman <..!seismo!{vrdxhq|dgis}!BMS-AT!stuart>
avg@navajo.STANFORD.EDU (Allen Van Gelder) (11/03/86)
References: This problem seems to center on the issue of connectivity and separators. For the angel, any two planets within a certain distance are connected by an edge. So far, no one has clarified "distance". Three possible definitions are (1) Euclidean distance, sqrt(dx^2 + dy^2); (2) Manhattan distance, |dx| + |dy|, in which a diagonal move has length 2; (3) "max" distance, max(|dx|, |dy|), in which a diagonal move has length 1. Let's consider some small-distance cases first. Say the angel can move distance 1. In Euclidean and "max" this means only rectilinear moves. The connectivity is 4. The devil can trap the angel in about 10 moves by the well-known go tactic of playing a diagonal away. Here is an example. Let a be the angel's initial position, 1 be the devil's first move; let b be the angel's 2nd position, 2 be the devil's 2nd move; etc. . . . . . . . . . . . . 1 . . . . . . 6 . . a . . . . . . f . b . . . . . 5 e d c 2 . . . . . 4 . 3 . . . . . . . . . . . . . The rest is clear, and it is easy to try the other alternatives for the angel and see that they are fruitless. The situation is not so clear with manhattan distance; now the connectivity is 8. Going to distance 2, the connectivity jumps to 12 or 24, depending on which "distance" you use. I suspect that if you find a way to trap the angel when it can go manhattan distance 2, it will generalize to 100. Now a theorem: If the devil can always force the angel to move to a planet in 2 or more moves that she was already on or could have reached in 1 move, then the angel can be trapped. Proof: If the angel has an escaping strategy, then assume that she uses an optimal escaping strategy. Suppose the angel travels from P1 to P2 in 2 or more moves, and could have arrived there in 1 move; then the strategy is not optimal because the devil has gotten at least 1 "free" move. Similarly, if P1=P2, then the devil has gotten at least 2 free moves. Thus, if the devil can always force this to occur, then the angel has no escaping strategy. QED That isn't supposed to be rigorous; it's just supposed to convince you. This theorem at least reduces the search space; an angel strategy can be considered to fail as soon as a non-optimal move occurs; you don't have to grind it out to the bitter end. To formalize this a little more, say the angel can "see" a planet if she can move to it in one turn. Keep track of planets the angel has seen and when they were FIRST seen. At each turn the angel must move to a planet she sees but has never seen before.
jml@cs.strath.ac.uk (Joseph McLean) (11/04/86)
Re:Patrick Stirling's comments on 1-dimensional solution. Sorry,Patrick,but you have just used a 2-dim argument.The fact that you have introduced the idea of 'parallel' immediately implies 2-d's. A 1-dim system is best described by a straight line (e.g.the real line). By the way,can I clear up something ? Can the angel zig-zag in one turn, or must it travel in straight lines ? (This of course is for 2-d or greater). jml.
tan@ihlpg.UUCP (Bill Tanenbaum) (11/04/86)
< Now a theorem: < If the devil can always force the angel to move to a planet in 2 or more < moves that she was already on or could have reached in 1 move, < then the angel can be trapped. < Proof: < If the angel has an escaping strategy, then assume that she uses an < optimal escaping strategy. < Suppose the angel travels from P1 to P2 in 2 or more moves, and could < have arrived there in 1 move; then the strategy is not optimal because < the devil has gotten at least 1 "free" move. Similarly, if P1=P2, < then the devil has gotten at least 2 free moves. Thus, if the devil < can always force this to occur, then the angel has no escaping strategy. < QED < That isn't supposed to be rigorous; it's just supposed to convince you. ------ Your theorem may be correct, but your "proof" is far from convincing. ------ < This theorem at least reduces the search space; an angel strategy can be < considered to fail as soon as a non-optimal move occurs; you don't < have to grind it out to the bitter end. < To formalize this a little more, say the angel can "see" a planet if < she can move to it in one turn. Keep track of planets the angel has seen < and when they were FIRST seen. At each turn the angel must move to < a planet she sees but has never seen before. ------ Even if your theorem is correct, I do not understand how it justifies your conclusion. The theorem says that if the devil can ALWAYS force a "suboptimal" move, the angel can be trapped. You then conclude that if the devil can force a suboptimal move ONCE, the angel can be trapped. That may be true, but it certainly doesn't follow from your theorem. -- Bill Tanenbaum - AT&T Bell Labs - Naperville IL ihnp4!ihlpg!tan
aka@cbrma.UUCP (Andy Kashyap) (11/04/86)
References: >Assumption: > >The problem is solvable in a one dimensional case. This is effectively a >case where there is only a single row of planets stretching on to >infinity. ie.: > > <--............A..................--> > >In this case, is is provable that the devil can trap the angel by building >a single block of 100 anywhere and then building another block of 100 at >least 100*100*2 spaces away and then slowly closing in on the [angel. [...] >Bernie Gunther > >UUCP: {ihnp4, harvard, genrad, ...}!mit-eddie!mck-csc!bmg >ARPA: bmg@mit-xx Although the angel can travel 100 planets a day, it is not clear to me from the problem that it takes a hundred destroyed planets in a row to block the angel. I'll assume that it takes a single destroyed planet to block the angel. With that assumption, the single dimension case is too trivial. The 2D plane: Given the angel somewhere, it is clear that the devil must move far enough away from the angel to have time to build a wall (of destroyed planets) around in a circle to trap the angel before the angel can escape. Keeping the angel at the center, the number of planets on the wall grows linearly with the distance from the center and faster. That is the devil must destroy about 628(*) planets for every 100 planets he moves away from the angel. Since he can only destroy one planet a day he can never trap the angel. The devil is 1/629 times slower than he needs to be. (*) for perfectionists: the exact value is 2 * pi * r, where r=100. Other conclusions: Had the devil been able to destroy 628 planets a day, the problem would be non-deterministic. For greater 629 planets a day, he would for sure be able to trap the angel and for less than 628 planets a day, he can not. -- +---------------------------------------------------------------------------+ : What is reality anyway but a collective hunch. : Andy Kashyap : : Reality is fine in small doses ... : AT&T Bell Labs : : ... but as a life style, it's too confining. : Columbus OH : : -- The Tonight Show : ..!cbosgd!cbrma!aka: +---------------------------------------------------------------------------+
dhecker@sjuvax.UUCP (11/05/86)
In article <1056@navajo.STANFORD.EDU> avg@navajo.UUCP (Allen Van Gelder) writes: > >Now a theorem: >If the devil can always force the angel to move to a planet in 2 or more >moves that she was already on or could have reached in 1 move, >then the angel can be trapped. >Proof: >If the angel has an escaping strategy, then assume that she uses an >optimal escaping strategy. >Suppose the angel travels from P1 to P2 in 2 or more moves, and could >have arrived there in 1 move; then the strategy is not optimal because >the devil has gotten at least 1 "free" move. Similarly, if P1=P2, >then the devil has gotten at least 2 free moves. Thus, if the devil >can always force this to occur, then the angel has no escaping strategy. >QED >That isn't supposed to be rigorous; it's just supposed to convince you. I'm not convinced. Part of the angel's strategy may be to backtrack after it sees what the devil is doing. You are assuming that the angel's strategy is completely independent of what the devil does. >To formalize this a little more, say the angel can "see" a planet if >she can move to it in one turn. Keep track of planets the angel has seen >and when they were FIRST seen. At each turn the angel must move to >a planet she sees but has never seen before. This note adds a perspective to the problem I hadn't thought of before. How far can the angel see ???? I would assume, as I said above, that the angel's strategy will be dependent upon the devil's moves. But, if the angel can't see the devil's moves, this may restrict the possible strategies for the angel, since it doesn't know what the devil is going on !!! David Hecker St. Joseph's University Phila., Pa.
vnend@ukecc.UUCP (D. W. James) (11/07/86)
Distribution:net Keywords:Lets keep it simple.... Ok, lets look at the simplest case. As stated we gave the angel a movement of at most 100 per day, while only letting the devil destroy 1 planet in the same time frame. Lets 'handicap' the angel. Lets say that now he can only move 1 planet per day. If we assume that the devil and angel know nothing about each others actions (except we will let the devil know the angels starting position) then the question boils down to this: at what distance must the devil begin destroying planets so that the angel will be unable to get around the devils barrier? The formula for the number of planets that the devil must destroy to successfully trap the angel is simply the equation for the circumference of a circle. This follows from the principle that the devil wants to destroy the minimum number of planets to achieve his task ( to big an assumption? ). If this is true then we have 2piR planets to be destroyed before the angel is trapped with a finite number of planets to live on. R is dependant on the speed of the angel. Our devil need only pick an R that will enable him to complete the encirclement of the angel to win. So what is that number? It is obviously dependant on the speed of the angel. And in fact it is not definable. The poor devil must destroy 2pi times the distance the angel can travel in the same interval, and he just can't do it. Give them each total knowledge of each others actions and the answer remains the same. The devil can trap a DUMB angel (random movement or some such garbage, remember the drunkards walk?) but he can't be guarenteed of trapping the angel unless he has the ability to destroy 2pi the angels movement. -- ******************************************************************************* Later y'all, Vnend Ignorance is the Mother of Adventure. *******************************************************************************
stassen@spp2.UUCP (Chris Stassen) (11/08/86)
In article <5349@cbrma.UUCP> aka@cbrma.UUCP (Andy Kashyap) writes: >Given the angel somewhere, it is clear that the devil must move far enough >away from the angel to have time to build a wall (of destroyed planets) >around in a circle to trap the angel before the angel can escape. I don't think that the devil must complete the entire circle before the angel can reach any point on its edge. All the devil must do is be able to build the parts of the circle in the angel's path faster than the angel can change direction. For example, suppose that the angel first moves to the left. Then, the devil wouldn't have to worry about the right half of the circle just yet, as the angel isn't heading in that direction, anyway. (By the way, I don't think that you need to spend too much time considering the case of the angel reversing direction, as that's the same as giving the devil two free moves). -- Chris
desj@brahms (David desJardins) (11/09/86)
In article <742@ukecc.UUCP> vnend@ukecc.UUCP writes: >Keywords:Lets keep it simple.... > [Some ridiculous claim about destroying 2 pi R planets.] > The devil can trap a DUMB angel (random movement or some such garbage, >remember the drunkards walk?) but he can't be guarenteed of trapping the >angel unless he has the ability to destroy 2pi the angels movement. I hate to be rude, but isn't it clear to all that this is not a proof? It is not just this poster; several other people have said essentially the same thing. In sci.puzzle it might be appropriate to make random guesses about what the solution might be. It is definitely not appropriate in sci.math. I certainly don't mean to discourage all speculation -- no one expects a proof to spring forth fully formed. For example, the discussion of what happens if the angel if forced into a suboptimal move is appropriate (al- though it would be nice to have a little more rigor in the analysis). But please try to make at least some attempt to understand the mathematical subtleties of the problem before claiming to have proven a problem that has resisted the efforts of some of the world's best mathematicians. As a suggestion, consider the problem of trapping a chess king. It definitely *can* be done. If the king wins by reaching the edge of the board, then he can be prevented from doing so if he starts at the center of a board 35x35 or larger. Understand this fact (by deriving it yourself, or by reading the exposition of this and related problems in _Winning Ways_ ch. 19) before trying to solve a much harder problem. -- David desJardins
stuart@bms-at.UUCP (Stuart D. Gathman) (11/10/86)
Theorem 1:
If the devil can trap the angel when she can move up to N^2
planets per turn but cannot move through any destroyed
planets
then
the devil can trap the angel when she can move up to N planets
per turn and only the last planet in the move need be
undestroyed.
"Proof":
In the latter case, the devil can regard the universe as
consisting of N x N squares. He can completly obliterate
an N x N square in N^2 turns. During this time the angel
can move N^3 planets, or N^2 N x N squares. The angel
cannot move through an obliterated N x N square.
This resolves the question of whether the angel can 'hop' planets.
Corollary:
If the angel can move diagonally, as well as horizontally
and vertically, N squares per turn, (and can perhaps hop planets)
and
the devil has a strategy that will trap the angel when
she can move (2N)^2 square per turn, (but can't hop planets)
then
the devil can trap the angel.
"Proof":
The devil regards the angel as moving 2N planets per turn
with ability to hop. A diagonal move consists of two moves:
one horizontal and one vertical. The result follows from the
above theorem.
Now we need only worry about horizontal and vertical moves (in any
combination per turn) that cannot move through a destroyed planet.
Theorem 2: (From an assertion due to Allen van Gelder)
Any angel move that puts the angel nearer to an earlier move
than she was in her previous move will at worst allow the
devil to win. If the angel can escape, she can do so without
making any such moves.
"Proof":
Trapping the angel means that the devil has (among other things)
destroyed planets in a "shell" (of some unspecified shape)
surrounding the angel. Any backtracking by the angel simply
gives the devil more time to complete his shell.
The general character of the devil's strategy is now apparent:
Imagine a "shell" of suitable size surrounding the angel.
Proceed to destroy planets to complete this shell in a
sequence determined by the angel's subsequent moves. The
portions of the shell nearest to the angel should be
completed first.
This is in fact easily accomplished for N=1 (no diagonal moves).
(This is left as an excercize for the reader.) What we would like
to have now is a theorem showing that if the devil can trap the
angel in N moves, then he can trap the angel in N + 1 (or 2N, or
N^2, etc.) moves. (Assuming we are rooting for the devil.)
We need only deal with the "standard" game
(no diagonal moves, no planet hopping).
My suspicion is that the angel cannot be trapped when N>1. At least
I cannot come up with a general strategy. (N=1 with diagonals is like
N=4 without.) Although I can't prove this,
I think the proof would be something like this:
Conjecture 3:
If and only if the devil can partition (confine the angel
to one side of) the universe, then he can trap the angel.
The partition is an imaginary one and is enforced only
when the angel approaches.
"Proof":
The devil can trap the angel with four such partitions.
The converse is clear. If the devil cannot even partition the
universe, he cannot trap the angel.
Caveat:
What is not clear is whether the devil can adequately
"defend" more than one partition at once.
Conjecture 4:
The devil can partition the universe if and only if he can
destroy as many planets in distinct horizontal (vertical)
positions as the angel can move in one turn.
"Proof":
The devil can always secure the point of the partition nearest
the angel. Therefore, we need only consider the case where
the angel and devil are adjacent within N squares.
Since backtracking is fatal to the angel (by theorem 2),
we can assume they are moving in the same direction.
* = devil . = angel
N=1: * * the devil wins.
. . *
N=2: * * * and so on, stalemate, the angel wins ?!?! (see the
. . . caveat in proof of 3. (Other cases similar.)
N=3: * . * the angel crosses the partition.
.
and so on. (This does not exactly cover all cases. :-)
--
Stuart D. Gathman <..!seismo!{vrdxhq|dgis}!BMS-AT!stuart>berman@psuvax1.UUCP (Piotr Berman) (11/10/86)
>Ok, lets look at the simplest case. [...] the devil destroy 1 planet [per day >while] the angel can move 1 planet per day. If we assume that the devil and >angel know nothing about each others actions (except we will let the devil >know the angels starting position) then the question boils down to this: >at what distance must the devil begin destroying planets so that the angel >will be unable to get around the devils barrier? > The formula for the number of planets that the devil must destroy to >successfully trap the angel is simply the equation for the circumference of >a circle. This follows from the principle that the devil wants to destroy the >minimum number of planets to achieve his task ( to big an assumption? ). If >this is true then we have 2piR planets to be destroyed before the angel >is trapped with a finite number of planets to live on. >[However during this time angels makes 2piR moves and is outside the circle.] >Give them each total knowledge of each others actions and the answer remains >the same.... > To the contrary. First, we shall define what does it mean to 'move 1 planet per day'. Assume that the angel can move to planets in the distance 1 or sqrt(2). Select a large R. Assume the angel starts at (0,0). During first R/2 moves the devil destroys planets with coordinates of the form (R,16k) (-R,16k) (16k,R) (16k,R) where k is integer between -R/16 and R/16. Then it destroys some constant number of planets on each corner of the resulting square: *** * * * * * * * * * * * *** * * * * This is the * * rough pattern * * * * * * * * * * * * *** * * * * * * * * * * * *** Now the devil starts to watch carefully the angel. If the angel follows a diagonal toward a corner, the devil destroys more planets on both sides of the corner. If the angel is closer to one of the sides of the square than to the other sides, the devil destroys the planet which is the closest on the square perimeter to the angel, but is not destroyed yet. Draws are solved randomly. Now the angel cannot avoid the following: by the time it will approach the square perimeter, the situation will be like that: *** A Now the angel can move along the perimeter, but it will never catch up with the destruction, until it will be cornered. I am sure that this strategy is not optimal. However, I do not see any way to improve it so that twice faster angel can be trapped as well.
stassen@spp2.UUCP (Chris Stassen) (11/11/86)
Note: nothing rigorous here; just some random thoughts. Hit 'n' or 'j' now if you're only interested in proofs. Contents: 1) 2-dimensional, 1-move Angel can always be caught. 2) Looking at the "end run" concept. 3) Forcing the Angel to 'turn' 4) More than two dimensions. The Devil CAN always trap the Angel, in two dimensions, when the Angel's move is 1. Here's the strategy (condensed vertically to fit in one screen): +-----------------------------------------+ | X*....................*X | The Angel cannot get to the 'X' | * ++++++++++++++++++++ * | planets from inside the square, | .+ +. | as long as the '*' planets get | .+ A +. | destroyed first. | .+ +. | | * ++++++++++++++++++++ * | | X*....................*X | +-----------------------------------------+ The Devil simply destroys the 8 '*' planets, on a 19x19 square, with the Angel starting at the center of the square. Then, whenever the Angel reaches a planet marked '+', the Devil simply destroys the planet marked '.' right beside it. The Angel can never get out of the square. (a 19x19 square was selected so that the Angel cannot reach the '+' planets before the Devil finishes with the corners). (btw, I'll show later that it only takes one extra '*' to turn the Angel around the corner, so this could have been accomplished on a 11x11 square, only taking half of the '*' planets first). Note that this works by destroying planets so that there is no planet that the Angel can get to which permits two possible escapes from the area. Any planet ('+') that the Angel can get to has only one associated exit ('.'), which the Devil can cut off as soon as the Angel reaches the '+' planet. I've been thinking about the "end run" concept; the 1-planet-per-move Angel is the ONLY case where the Angel cannot run around a line that the Devil is building: +-----------------------------------------+ | Area that the Angel must be kept out of | |************ | | A-> | +-----------------------------------------+ The Devil can keep the Angel out of that area, because he can destroy one more planet in the line for every one planet that the Angel can move -- the Angel cannot "run around" the line if the Devil does not "want" him to. As soon as the Angel's move is bumped to 2, the Devil must destroy FOUR planets for every step that the Angel may take, and the Devil can no longer keep the Angel on one side of the line. +-----------------------------------------+ | Area that the Angel must be kept out of | The Devil must destroy the four |************++ | '+' planets to keep the Angel from |************++ | getting to the other side of the | A-> | line in two moves. +-----------------------------------------+ Back to 1-move Angels in two dimensions: If the Devil has one "spare" move (i.e. destroyed planet ahead of the line), then he can force the Angel to take a right turn. ($ = extra planet in line, 1-5 = Devil's moves, and a-e = Angel's moves). +-----------------------------------------+ | Area that the Angel must be kept out of | The Angel cannot escape to the |************123$. | '.' planet unless his move is | abcde4 | at least SQRT(2). | 5 | +-----------------------------------------+ In the above diagram, the Devil now has the Angel "walled off" on the right, and the Angel cannot "run around" the Devil's vertical line. This algorithm fails in three dimensions. The Devil can still keep the Angel on a particular side of a plane, but it requires an infinite amount of 'spare moves' ('$') for the Devil to force the Angel to turn and be contained by two intersecting planes. The issue of "being able to force the Angel to turn" is more critical to containing the Angel than the issue of keeping it on one side of a line/plane. -- Chris
chrisj@basser.oz (Christopher Jack) (11/11/86)
If the angel is allowed to move only one planet, there is a very
simple algorithm that assures that the devil will win.
Outline (to give the idea)
First destroy the planet immediately above the angel
If the angel moves down, destroy the planet immediately below the angel
else If the angel moves sideways, destroy the planet diagonally up from the angel
{if the angel moves down, destroy the planet underneath it
else if the angel moves up, destroy the planet above it
else (sideways), the next planet in the same direction}
Repeat the algorithm (approx) until angel is trapped
Basically the algorithm prevents the angel moving more than a certain
distance in any direction, and eventually traps.
I've left out a lot of fiddly bits but I think the idea is correct
chrisj@basser.OZ