Paperback(With a New preface by the author)
-
PICK UP IN STORECheck Availability at Nearby Stores
Available within 2 business hours
Related collections and offers
Overview
Drawing on game theory, geometry, linear algebra, target-tracking algorithms, and much more, Nahin also offers an array of challenging puzzles with their historical background and broader applications. Chases and Escapes includes solutions to all problems and provides computer programs that readers can use for their own cutting-edge analysis.
Now with a gripping new preface on how the Enola Gay escaped the shock wave from the atomic bomb dropped on Hiroshima, this book will appeal to anyone interested in the mathematics that underlie pursuit and evasion.
Product Details
| ISBN-13: | 9780691155012 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 07/22/2012 |
| Series: | Princeton Puzzlers |
| Edition description: | With a New preface by the author |
| Pages: | 272 |
| Sales rank: | 447,193 |
| Product dimensions: | 5.50(w) x 8.30(h) x 0.80(d) |
About the Author
Read an Excerpt
Chases and Escapes The Mathematics of Pursuit and Evasion
By Paul J. Nahin Princeton University Press
Copyright © 2007 Princeton University Press
All right reserved.
ISBN: 978-0-691-12514-5
Introduction "Chases and escapes" are activities that might be said to define human existence, no matter where or when, ranging over the entire spectrum of violence from the romantic pursuitofa future spouse to the military pursuit of a target to be destroyed. Young children are introduced to both chases and escapes when they learn the simple rules of the game of tag: played by at least two, one player is designated as it, who then chases after all the others, who, of course, attempt to escape. When the it player manages to catch one of the evaders he or she yells "Tag! You're it!," that evader and the pursuer change roles, and the game continues until all drop from exhaustion. Parents love tag! The related game of hide-and-seek, also of this genre, is equally attractive to young children (and to their parents). And surely all readers can remember the fun of watching the old LooneyTunes Road Runner/Wile E. Coyote chase-and-escape cartoons. Hollywood's interest in chases dates, in fact, at least as far back as the 1914 serial The Perils of Pauline, with countless imaginative escapes by the heroine from her dastardly guardian's attempts to do her in.
As we grow older we leave hide-and-seek, tag, and cartoons behind, but there remains, for most people, a deep interest inpursuit-andevasion; the fascination simply becomes more sophisticated. The inherent conflict of chasing and escaping, of the battle between the hunter and the hunted, is the basis for at least half the fictional writing in the world. By their high school years, for example, most students have read the exciting Collier's Magazine story "The Most Dangerous Game" by Richard Connell. That 1924 tale of a shipwrecked man (Sangar Rainsford, a celebrated hunter) has the ironic twist of a famous hunter becoming the hunted. At first he finds what he thinks is salvation from drowning at sea as he stumbles ashore onto a nearby jungle-covered island, inhabited by one General Zaroff, who oddly finds himself regularly visited by shipwrecked sailors - probably because he has installed a false lighthouse to lure passing ships onto rocks. Rainsford soon changes his mind about salvation when he learns that the General provides his "visitors" with hunting clothes, food, and a knife, and then turns them loose back into the jungle. After a three-hour head start the General comes after them, armed only with a small caliber automatic pistol - if the General fails to make a kill within three days he promises to return his elusive prey to the mainland. As he explains to Rainsford, however, he has never failed to make the kill. The rest of the story, assigned to generations of high school English students by teachers who clearly admire Connell's tale, is of the suspenseful chase.
The printed story won a prestigious O'Henry Short Story Award, and was made into an exciting movie of the same name in 1932 (Joel McCrea played Rainsford, with his first name changed for some reason from Sangar to Bob!, and Fay Wray played a female role not in the original story; this last point is particularly interesting to note since the film was shot between takes, on the same set, of the classic film King Kong, which was released the next year in 1933 - starring, of course, Fay Wray). The Most Dangerous Game was remade at least two more times: A Game of Death (1946) and Run for the Sun (1956). There were numerous obvious derivatives of an inferior nature, as well, for example, the 1961 Bloodlust!, in which a mad scientist hunts teenagers and displays his catches in glass cases (this movie is notable for having embarrassed one of its stars, Robert Reed, even more than did his later role as Mike Brady, the perfect father on television's The Brady Bunch).
Jumping ahead a few decades, most readers of adventure fiction have enjoyed Frederick Forsyth's masterful 1971 novel The Day of the Jackal, in which a mysterious assassin-for-hire attempts to kill Charles de Gaulle, the president of France. We all know that de Gaulle was not assassinated in real life but, nonetheless, the writing of the killer's chase of his target - and of the intertwined police chase of the assassin- is so well done you think he's going to pull it off anyway. (The book was made into a successful film of the same title in 1973.) The novel was not the first of its type, being a clever reversal of roles from what I think the perfect pursuit-and-evasion fictional work- British writer Geoffrey Household's 1939 novel Rogue Male (made into the 1941 film Man Hunt). That work is a first-person, page-turning narrative of a world famous English hunter who makes the mistake of being caught sighting a high-powered telescopic rifle onto the distant figure of an unnamed European dictator. (Only a late-1930s reader as dense as a rock could have failed to recognize Hitler.) He is interrogated by his captors, that is, the Gestapo, and then escapes by a fantastic ruse back to England, where his enemies continue to pursue him ruthlessly. The book has a wonderful ending, telling the reader that matters have most definitely not ended and the chase is by no means over. This ending was literally a call-to-arms to the world of 1939 to challenge Hitlerand defeat him.
A little thought will convince you that Hollywood continues to love a good chase and (perhaps) escape - who, for example, can think of Steve McQueen's Bullitt (1968) without instantly visualizing that incredible car chase through the hilly streets of San Francisco? Other successful "chase" films include Predator (1987), The Hunt for Red October (1990), The Fugitive (1993), Alien (1979), Catch Me If You Can (2002), and the very best such film of all (in my opinion), Cornel Wilde's powerful portrayal of a naked man on the run from headhunters in his brilliant The Naked Prey (1961).
A relatively new (since the early 1980s) form of entertainment, computer videogames, has embraced the chase-and-escape concept as the basis for some of the most successful of all such games (e.g., Thief, Call of Duty, Half-Life, Max Payne, CounterStrike, Medal of Honor, and Hitman, all of which have had sequels to their original appearances). These games, called first-person shooters (so named because the screen image is the "world" as seen through the eyes of the protagonist) can be quite violent - typically, that image includes "your" hand holding a weapon for instance, a knife, gun, or club. The sales pitch for one of the Hitman games, for example, is "See the world, meet interesting people, kill them" - in Hitman you play as an assassin-for hire who is assigned targets, mostly international terrorists and crime lords, to hunt for "termination with extreme prejudice." These games can be subtle, too, however - the emphasis in the Thief games is not on killing at all(although you do carry a sword or dagger, and a bow with arrows), but rather on being able as a medieval thief to skillfully skulk about in the shadows and, if at all possible, to avoid confrontation while attempting to complete the mission goals. Whether violent or (relatively) benign, the successful first-person-shooter games are fun - many are even educational - to experience: playing as the conscript Alexei Ivanovich(a Russian sniperatthe Second World War Battle of Stalingrad) in Call of Duty can only be described as both ear-shattering and eye-opening, as well as masterfully capturing the horror of what happened there on the rooftops, in the sewers, and on the bombed-out Stalingrad streets in a way that I think equal to the best historical writing (e.g., Antony Beevor's 1998 Stalingrad, The Fateful Siege: 1942-1943).
The mathematical puzzles of chases and escapes were recognized quite early in the history of mathematics, for example, with the paradox given by the fifth-century B.C. Greek mathematician Zeno of Elea, of the race between Achilles (Homer's hero in the Iliad) and the tortoise. As Smith (1917) says about the origin of all pursuit problems, "It would be difficult to conceive of a problem that would seem more real, since we commonly overtake a friend in walking, or are in turn overtaken. It would therefore seem very certain that this problem is among the ancient ones in what was once looked upon as higher analysis. We have a striking proof that this must be the case in the famous paradox of Achilles and the Tortoise ... "(Zeno may well have been inspired to think upon the problem of linear pursuit - a chase along a straight line - by the even more ancient Aesop fable of the race between the hare and the tortoise. That tale predates Zeno by at least a century; its intent, unlike Zeno's paradox, was not mathematical at all, but rather to serve as an illustration of the moral lesson that "perseverance wins the race.") Zeno's paradox is easy to explain.
Achilles, fleet of foot, runs ten times as fast as the tortoise and so, to make their race more interesting, he gives the tortoise a ten-mile head start. Zeno's paradox is the result of a seductive argument that seems to prove that Achilles can never even catch the tortoise, much less pass him to win the race. This is a conclusion that is seen to be incorrect if one simply watches a real race! And that's the paradox, of course - where does Zeno's argument (which is pretty convincing to most young students when they first encounter it) go wrong? Zeno's argument is as follows: by the time Achilles runs through the initial ten mile head start, the tortoise will have run through one mile, and by the time Achilles runs through that one mile lead the tortoise will have run through one-tenth of a mile, and by the time Achilles runs through that one-tenth of a mile lead the tortoise will have run through one-hundreth of a mile, etc., etc., etc. This process continues through an infinity of ever decreasing leads that the tortoise has over Achilles and so, concludes Zeno, Achilles can never catch the tortoise.
The flaw in Zeno's argument escaped understanding for a very long time. Intellects as profound as those of Plato and Aristotle were befuddled by the problem, with Aristotle (in his Physics) correctly calling it a fallacy without being able to explain why. Today, twenty-five centuries later, high school students learn that the answer is that an infinity of numbers (the infinity of times it takes Achilles to run through the infinity of leads the tortoise has) does not necessarily have to add up to infinity. To see this, let v be the speed of the tortoise (and so 10v is the speed of Achilles). Thus, to run through the ten-mile head start takes Achilles a time of 10/10v. Then, to run through the now one-mile lead of the tortoise takes Achilles1/10v. To run through the now one-tenth-of-a-mile lead takes Achilles1/10/10v. To run through the now one-hundreth-of-a-mile lead takes Achilles1/100/10v. And so on. So, the total time required for Achilles to catch the tortoise is
10/10v + 1/10v + 1/10/10v + ... + 1/v (1 + 1/10 + 1/100 + 1/1000 + ...)
The expression in the parentheses is a geometric series, easily summed to 10/9, that is, the total time it takes Achilles to catch the tortoise is the finite time 10/9v, which of course we see is simply the time to run through the initial head start of ten miles at Achilles' closing speed of 10v-v =9v.
A different sort of pursuit-and-evasion problem, of great interest today among computer scientists because it requires skill in handling not a differential equation but rather what is called a data structure, also has an ancient origin: the Greek mythological story of Theseus and the Minotaur, which appears in the written word as early as in Ovid's Metamorphoses (dating from the time of Christ), although the myth itself is even more ancient, by centuries. The Minotaur, the result of an unnatural union between the wife of King Minos of Crete and a bull, was a flesh-eating monster with the head of a bull and the body of a man - but Edith Hamilton's classic book Mythology contains an illustration of the Minotaur with the head of a man and the body of a bull. This monster was kept confined by Minos to a complicated maze of connected passages called the Labyrinth, and once a year the creature was given a sacrifice offering of seven youths and seven maidens. These unfortunates were simply tossed into the Labyrinth, which was so complicated that they soon became lost and unable to find their way free. Eventually the Minotaur would come upon them in their confused wanderings and they were quickly devoured. The Minotaur's reign of terror was finally ended by Theseus, who, before entering the Labyrinth, tied one end of a ball of string to the entry. Then, after wandering through the maze until he found the Minotaur asleep - which he then killed - Theseus was able to escape by simply following the string back to the entry point. A popular undergraduate computer science programming project assignment is the writing of the code to simulate Theseus' hunt for the Minotaur through a Labyrinth of any desired structure, that is, one with arbitrarily complex connectivity.
All of the above discussion was to make the case that the subject of this book resonates with a fundamental psychological aspect of human nature. But let's now leave mere fictional games of chases and escapes, and turn our attention to the really good stuff; let's take a long look at the mathematics of pursuit-and-evasion. The intellectual demands will be significant; as Davis (1962) wrote, pursuit problems with "their curious difficulties have intrigued the fancy and strained the ingenuity of modern mathematicians." You'll agree by the time you finish, but I also think you'll see it will have been well worth the effort.
(Continues...)
Excerpted from Chases and Escapes by Paul J. Nahin
Copyright © 2007 by Princeton University Press . Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Preface to the Paperback Edition xiii
What You Need to Know to Read This Book (and How I Learned What I Needed to Know to Write It) xxvii
Introduction 1
Chapter 1. The Classic Pursuit Problem 7
- 1.1 Pierre Bouguer's Pirate Ship Analysis 7
- 1.2 A Modern Twist on Bouguer 17
- 1.3 Before Bouguer: The Tractrix 23
- 1.4 The Myth of Leonardo da Vinci 27
- 1.5 Apollonius Pursuit and Ramchundra's Intercept Problem 29
Chapter 2. Pursuit of (Mostly) Maneuvering Targets 41
- 2.1 Hathaway's Dog-and-Duck Circular Pursuit Problem 41
- 2.2 Computer Solution of Hathaway's Pursuit Problem 52
- 2.3 Velocity and Acceleration Calculations for a Moving Body 64
- 2.4 Houghton's Problem: A Circular Pursuit That Is Solvable in Closed Form 78
- 2.5 Pursuit of Invisible Targets 85
- 2.6 Proportional Navigation 93
Chapter 3. Cyclic Pursuit 106
- 3.1 A Brief History of the n-Bug Problem, and Why It Is of Practical Interest 106
- 3.2 The Symmetrical n-Bug Problem 110
- 3.3 Morley's Nonsymmetrical 3-Bug Problem 116
Chapter 4. Seven Classic Evasion Problems 128
- 4.1 The Lady-in-the-Lake Problem 128
- 4.2 Isaacs's Guarding-the-Target Problem 138
- 4.3 The Hiding Path Problem 143
- 4.4 The Hidden Object Problem: Pursuit and Evasion as a Simple Two-Person, Zero-Sum Game of
- 4.5 The Discrete Search Game for a Stationary Evader — Hunting for Hiding Submarines 168
- 4.6 A Discrete Search Game with a Mobile Evader — Isaacs's Princess-and-Monster Problem 174
- 4.7 Rado's Lion-and-Man Problem and Besicovitch's Astonishing Solution 181
Attack-and-Defend 156
Appendix A
Solution to the Challenge Problems of Section 1.1 187
Appendix B
Solutions to the Challenge Problems of Section 1.2 190
Appendix C
Solution to the Challenge Problem of Section 1.5 198
Appendix D
Solution to the Challenge Problem of Section 2.2 202
Appendix E
Solution to the Challenge Problem of Section 2.3 209
Appendix F
Solution to the Challenge Problem of Section 2.5 214
Appendix G
Solution to the Challenge Problem of Section 3.2 217
Appendix H
Solution to the Challenge Problem of Section 4.3 219
Appendix I
Solution to the Challenge Problem of Section 4.4 222
Appendix J
Solution to the Challenge Problem of Section 4.7 224
Appendix K
Guelman's Proof 229
Notes 235
Bibliography 245
Acknowledgments 249
Index 251
What People are Saying About This
This is a well-written and novel book that is comprehensively researched and enthusiastically presented. Nahin offers a very good mixture of elegant math and lively historical interludes. I wasn't aware the topic had such a rich history and wide scope.
— Desmond Higham, University of Strathclyde
Nahin provides beautiful applications of calculus, differential equations, and game theory. If you are pursuing an enjoyable collection of mathematical problems and the stories behind them, then your search ends here.
— Arthur Benjamin, Harvey Mudd College
This book is a treasure trove of puzzles and an enjoyable read. Nahin's aim is to assemble a varied collection of pursuit-and-evasion problems. Fully worked solutions, from first principles, are presented for each problem. Problems are carefully set in their historical context. I am not aware of another book that covers pursuit-and-evasion problems in anywhere near as much detail as is presented here.
— Nick Hobson, creator of the award-winning Web site "Nick's Mathematical Puzzles"
I know of no better way to grasp the basic concepts of calculus than to study pursuit-and-escape problems. Paul Nahin has made a superb survey of the vast field of such problems, from Zeno's paradox of Achilles and the tortoise through the famous four bugs that once made the cover of Scientific American. Not only does he make clear the required differential equations, but he traces each problem's colorful history. No book on the topic could be more definitive or a greater pleasure to read.
Chases and Escapes is a superb treatment of the solutions to a variety of pursuit-evasion problems, some classic and others more contemporary. The content is accessible to undergraduates in mathematics or the physical sciences, with lots of supporting detail included. The author's lively writing style makes for enjoyable reading.
— David M. Burton, University of New Hampshire
"Nahin provides beautiful applications of calculus, differential equations, and game theory. If you are pursuing an enjoyable collection of mathematical problems and the stories behind them, then your search ends here."—Arthur Benjamin, Harvey Mudd College"I know of no better way to grasp the basic concepts of calculus than to study pursuit-and-escape problems. Paul Nahin has made a superb survey of the vast field of such problems, from Zeno's paradox of Achilles and the tortoise through the famous four bugs that once made the cover of Scientific American. Not only does he make clear the required differential equations, but he traces each problem's colorful history. No book on the topic could be more definitive or a greater pleasure to read."—Martin Gardner"Chases and Escapes is a superb treatment of the solutions to a variety of pursuit-evasion problems, some classic and others more contemporary. The content is accessible to undergraduates in mathematics or the physical sciences, with lots of supporting detail included. The author's lively writing style makes for enjoyable reading."—David M. Burton, University of New Hampshire"This book is a treasure trove of puzzles and an enjoyable read. Nahin's aim is to assemble a varied collection of pursuit-and-evasion problems. Fully worked solutions, from first principles, are presented for each problem. Problems are carefully set in their historical context. I am not aware of another book that covers pursuit-and-evasion problems in anywhere near as much detail as is presented here."—Nick Hobson, creator of the award-winning Web site Nick's Mathematical Puzzles"This is a well-written and novel book that is comprehensively researched and enthusiastically presented. Nahin offers a very good mixture of elegant math and lively historical interludes. I wasn't aware the topic had such a rich history and wide scope."—Desmond Higham, University of Strathclyde