הצגת המקור של הדף "חידת האסיר הבורח"

'''חידת האסיר הבורח''' היא [[חידה מתמטית]] על [[משחק]] שמתרחש בין אסיר וסוהר שרודף אחריו. נוסח החידה הוא כדלקמן: אסיר כלוא בכלא [[מעגל|מעגלי]] המוקף חומה ב[[רדיוס]] R שעליה מפטרל סוהר. [[מהירות]]ו של הסוהר גדולה פי 4 מזו של האסיר. ברגע שהאסיר מגיע לנקודה בחומה שהשומר אינו נמצא בה, הוא מטפס על החומה במהירות הבזק ונמלט. האם יוכל האסיר לברוח ואם כן כיצד?

==פתרון==
הפתרון, כלומר ה[[תכסיס (תורת המשחקים)|אסטרטגיה]] של האסיר, היא לצבור יתרון זוויתי מרבי ובמקביל להגדיל את המרחק ממרכז המעגל. המרחק המרבי r ממרכז המעגל בו עדיין ניתן לצבור יתרון זוויתי ככל הניתן הוא r = R/4, שכן יחס המהירויות הוא 4 לכן האסיר צריך לנוע במעגל ברדיוס r (כמעט r במובן הגבולי) כדי שמהירותו הזוויתית תשתווה לזה של הסוהר. האסיר ימשיך לנוע במעגל ברדיוס r עד שהוא יצבור יתרון זוויתי של π [[רדיאן|רדיאנים]] על הסוהר ולאחר מכן ינוע בקו ישר לאורך הרדיוס מרחק של 3/4R. הזמן שלוקח לאסיר לעשות זאת הוא <math>T_1 = 3/4R/V </math> לעומת הזמן שלוקח לסוהר להגיע לנקודה הנגדית לו על החומה <math>T_2  = \frac{\pi R}{4V}</math> . כיוון ש- <math>T_1</math>  קטן מ-<math>T_2</math> נובע שהאסיר יוכל להימלט. יחס המהירויות הקריטי בין הסוהר לאסיר, שמעליו האסטרטגיה הזו לא תעבוד מקיים:
<math>(R-R/K_C)/V= \frac{\pi R}{K_CV}</math> לפיכך יחס המהירויות הקריטי הוא <math>K_C = \pi + 1</math> . אף על פי כן, האסטרטגיה המביאה ליחס קריטי זה אינה פתרון אופטימלי וקיים נתיב המביא ליחס מהירויות קריטי גבוה יותר.

===נתיב המילוט האופטימלי===
[[קובץ:חידת_האסיר_הבורח.pdf|שמאל|250px|הפתרון הוא לנוע בכיוון משיק למעגל ברדיוס R/K.]]
ישנם שני סוגי יתרונות במשחק שאותם האסיר יכול לצבור על פני הסוהר: יתרון זוויתי ויתרון של ריחוק מהמרכז. שני היתרונות יכולים להיות מומרים אחד לשני, כלומר ניתן להמיר יתרון זוויתי ליתרון של ריחוק מהמרכז לפי היחס <math> \triangle r =\triangle\theta*R/k</math>. ראשית ברור שהפתרון של לצבור יתרון זוויתי מרבי באמצעות תנועה ברדיוס של כמעט R/K עד ל-180 מעלות ואז לנוע ישירות לנקודה הנגדית למיקום הסוהר אינו מיטבי; בנקודה נגדית זאת המשיק למעגל מאונך לקו שמחבר בין נקודה C באיור לנקודה זאת - משמעות הדבר היא שהאסיר יכול לנוע לנקודה סמוכה אליה כמעט מבלי לשנות את מרחק התנועה הנדרש ממנו בעוד תוספת המרחק הנדרשת מהסוהר אינסופית לעומת תוספת המרחק הנדרשת מהאסיר, כלומר יחס המהירויות הנדרש לתפיסת האסיר גדל.

הפתרון הוא, משיקולים של [[תורת המשחקים]], לנוע מנקודה C בקו ישר בכיוון מסוים, אותו אפשר להסיק מגאומטריה. בנקודה ההגעה של האסיר צריך להתקיים שהשינוי במרחק שהאסיר צריך לרוץ עקב תזוזה של נקודת ההגעה אל נקודה שנמצאת ב[[סביבה (מתמטיקה)|סביבה]] שלה, שווה לשינוי במרחק שהסוהר צריך לעבור חלקי K - תוספת זמן התנועה של הסוהר שווה לתוספת זמן התנועה של האסיר, כלומר הם מגיעים באותו זמן לנקודה המיועדת. זה שקול לכך שבנקודה זו יחס המהירויות הדרוש ללכידת האסיר מקסימלי. נסמן את הזווית CED שבאיור ב-<math>\alpha</math>. צריך להתקיים <math>|\cos\alpha| = \frac{{1}}{{K}}</math>. אם נחבר את מרכז המעגל O עם E אזי הזווית OEC שווה <math>\alpha - 90</math> (שכן משיק למעגל מאונך לרדיוס) לפיכך <math>\sin(\alpha - 90) = -sin(90 - \alpha) = -\cos\alpha = \frac{{1}}{{K}}</math>, ומ[[משפט הסינוסים]] לגבי משולש OCE נקבל <math>\frac{{R}}{{sin\angle(OCE)}} = \frac{{R/K}}{{1/K}}</math>, כלומר זווית OCE היא 90 מעלות וזה הפתרון - '''לנוע בכיוון משיק למעגל ברדיוס <math>r = \frac{{R}}{{K}} </math>'''. יחס המהירויות הקריטי <math>K_C</math> מקיים: <math>(\pi + \arccos(1/K_C))R = K_C*R\sqrt {{1 - 1/K_C^2}}</math>. פתרון [[אנליזה נומרית|נומרי]] מניב <math>K_C = 4.6033388489</math>.

==קישורים חיצוניים==
<div class="mw-content-ltr">
* [http://puzzles.nigelcoldwell.co.uk/thirteen.htm Circular Field, Hungry Dog]
* [http://datagenetics.com/blog/october12013/index.html How to escape a monster]
* [http://www.mytechinterviews.com/the-fox-and-the-duck The Fox and The Duck]
</div>
[[קטגוריה:חידות]]