איך תופסים אריה במדבר?

לפני מספר ימים ראיתי סרט (לא אפרט איזה, כדי לא לקלקל יותר מדי) שבו מוחבאת פצצה במקום מסויים בעיר, ומטמיני הפצצה, בתור קינטור, הציבו מצלמה שמשדרת את תמונת הפצצה באופן רציף. אחד מהרעיונות של הגיבורים למציאת הפצצה הוא ניתוק החשמל לאיזורים בעיר ובדיקה בכל פעם האם המצלמה הוחשכה. זה רעיון מצויין (בהנחה שניתוק החשמל לא ימריץ את כוחות השחור לפוצץ את הפצצה או משהו), אך בסרט לא יוצא ממנו כלום - גם כששעת האפס מתקרבת, רק חלק זעום מהעיר נסרק באמצעות ניתוקי חשמל. האם היה אפשר לעשות את זה טוב יותר?

איני יודע מה יענה האדם ברחוב על השאלה הזו, אבל אם השאלה תופנה לאנשים שלמדו מעט מתמטיקה או מדעי המחשב, קרוב לודאי שתיזרק לחלל האוויר התשובה “אריה במדבר”. ואכן, זו בדיוק השיטה שהייתה מובילה למציאת הפצצה תוך דקות ספורות.

השם המוזר הזה מגיע מבדיחה מתמטית ישנה - איך תופסים אריה במדבר? ראשית, בונים גדר סביב המדבר. שנית, בונים גדר שעוברת באמצע המדבר. כעת האריה נמצא באחד משני חצאי המדבר. בונים גדר שחוצה גם את חצי המדבר הזה לשניים, ומקבלים שני “רבעי מדבר”, שהאריה נמצא באחד מהם. ממשיכים שוב ושוב בתהליך בניית הגדר עד שבסופו של דבר האריה נמצא בתוך כלוב זעיר של מטר על מטר על מטר (מסוג הדברים שרואים יותר מדי בגני החיות). מי שרוצה לשחק במשחק הזה בעצמו, יכול; בגרסה קצת יותר מתוחכמת הוא נקרא “סוגר שטחים” (ובאנגלית השם ה”גנרי” הוא Qix, או Xonix - יש המוני משחקים כאלו).

מה משעשע בבדיחה הגרועה הזו? העובדה שהיא מתארת בצורה די מדוייקת שיטת עבודה מתמטית. אנסה לתאר שניים מהשימושים הנפוצים שלה - חיפוש בינארי, ומשפט בולצאנו-ויירשטראס.

חיפוש בינארי מוסבר בדרך כלל באמצעות ספר טלפונים. נניח שיש לכם ספר טלפונים - איך אתם מחפשים בו שם, נניח “הפלשתי גוליית”? (השמועה אומרת שפעם היה כזה בספר הטלפונים) ובכן, קרוב לודאי שאתם קודם כל הולכים לתחילת האות ה’ - זהו שימוש באינדקס, שהוא נושא לדיון בפני עצמו, אבל בואו נניח שספר הטלפונים גרוע ואין בו סמנים לתחילת האותיות. אז מה עושים?

מה שאני הייתי עושה הוא לפתוח את ספר הטלפונים בערך באמצע, ולראות איזה שם אני רואה. נניח שהשם היה “נביא, יחזקאל”. מה עכשיו? מן הסתם, גוליית נמצא בחצי הראשון של ספר הטלפונים, וכל מה שבא אחרי יחזקאל לא רלוונטי. אם כן, אפתח באמצע החצי הראשון, ואראה את השם “דלפון, עני”. אז גוליית נמצא אחרי השם הזה, אבל לפני יחזקאל - זהו “הרבע השני” של ספר הטלפונים. אם כך, אפתח גם אותו באמצע, וכן הלאה וכן הלאה, עד שיימצא גוליית או שאגלה שני שמות רצופים, שגוליית גדול מהראשון, אך קטן מהשני (למשל, “הפלשתי בני”, ומייד אחריו “הפלשתי דוד”) ואז אדע שאין גוליית.

במציאות זה לא בדיוק עובד ככה. אם אני מחפש את הפלשתי גוליית, כנראה שלא אפתח את ספר הטלפונים בדיוק באמצע אלא בשליש הראשון או משהו דומה. מה שחשוב כאן הוא הרעיון הכללי - בכל חיפוש שאני עושה, אני מחלק את האיזור שעוד נותר לחפש בו לשני חלקים שהם “בערך מאותו גודל” (ה”בערך” הזה הוא לב העניין כאן), ואז בעזרת קריאת שם בודד מספר הטלפונים, אני פוסל לחלוטין את אחד משני החלקים הללו, ולכן נשאר לחפש את השם בחלק השני. אם פתחתי את הספר בדיוק באמצע, הרי שעל כל שם שאני קורא, צמצמתי בחצי את כמות השמות שעוד נותרה לי לעבור עליהם. כדי להבהיר עד כמה הצמצום הזה משמעותי, אני הולך להכניס לתמונה משוואות וסימונים מתמטיים מרושעים.

ובכן, נניח שבספר הטלפונים יש \( N \) שמות. אני רוצה לבדוק אם שם ספציפי אחד נמצא שם. מה הדרך לעשות זאת? הדרך הכי נאיבית היא לקרוא את כל השמות, ולבדוק האם השם שאני מחפש מופיע ביניהם. הדרך הזו תכריח אותי לקרוא \( N \) שמות - וזה הרבה. למרבה המזל, ספר טלפונים הוא לא סתם מקבץ אקראי של שמות, אלא יש לשמות שבו תכונה חשובה ביותר - הם ממויינים. מישהו כבר טרח ועמל כדי שהשמות שבספר יהיו מסודרים “מהקטן אל הגדול”. הטרחה והעמל הללו הם לא טריוויאליים, ובהחלט יש מקום לפוסט נפרד עליהם. השאלה שלי כרגע היא איך אני מנצל את המיון הזה - וזה בדיוק מה ששיטת החיפוש שהצעתי לעיל עושה. החשיבות של המיון היא בכך שאחרי שחציתי את ספר הטלפונים לשני חצאים, די לי להסתכל על השם שבאמצע כדי לדעת בודאות איפה השם שאני מחפש לא יכול להימצא, ולכן איזה חלק מהספר אפשר “לזרוק”.

אם כן: אחרי קריאת אפס שמות, יש לי \( N \) שמות לחפש בהם. אחרי קריאת שם אחד, יש לי \( \frac{N}{2} \) שמות לחפש בהם. אחרי קריאת שני שמות, יש לי \( \frac{N}{4} \); אחרי קריאת שלושה שמות, \( \frac{N}{8} \); ובאופן כללי, אחרי קריאת \( k \) שמות יש לי \( \frac{N}{2^{k}} \) שמות לחפש ביניהם. השאלה היא - מתי יישאר לי לכל היותר שם אחד? או בניסוח אחר, מתי \( \frac{N}{2^{k}}\le1 \)? ובניסוח אחר, מתי \( N\le2^{k} \)? וכאן נכנס לתמונה המושג המתמטי של לוגריתם. תזכורת: \( x=\log_{a}b \) (“לוגריתם של \( b \) על בסיס \( a \)) פירושו שמתקיים \( a^{x}=b \), כלומר הלוגריתם של \( b \) על בסיס \( a \) הוא בדיוק המספר שבחזקתו יש להעלות את הבסיס כדי לקבל את \( b \). במדעי המחשב לוגריתם על בסיס 2 הוא נפוץ מאוד, כך שיש לו סימן מקוצר: \( \log_{2}x=\lg x \). מההגדרה שנתתי אפשר לראות ש-\( \lg2^{k}=k \) (למה?) ולכן התשובה לשאלה “מתי \( N\le2^{k} \)” היא כמו התשובה לשאלה “מתי \( \lg N\le k \)?” (שימו לב שאני מניח שהפעלת לוגריתם על שני האגפים משאירה את אי השוויון בעינו ולא הופכת כיוון או משהו דומה - לא אכנס לסיבה כרגע, אבל נסו לחשוב אם אתם מבינים מהי).

אם כן, המסקנה היא שכדי למצוא שם בספר טלפונים עם \( N \) שמות, אני צריך לבדוק רק \( \lg N \) מהשמות. זה מספר הרבה, הרבה יותר קטן מאשר \( N \). כדי לקבל מושג עד כמה, אציין ש-\( \lg1,000\approx10 \) (כלומר, הוא בערך 10; למעשה, הוא יותר בכיוון ה-9.965 משהו משהו משהו), וש-\( \lg1,000,000\approx20 \) וש-\( \lg1,000,000,000\approx30 \) - הבנתם את הרעיון. המסקנה היא שגם בספר טלפונים שמכיל את שמות כל בני האדם שחיו אי פעם, לא תצטרכו לקרוא יותר מאשר, נניח, 50 שמות כדי למצוא את גוליית - וגם בספר שמכיל את כל שמות כל האורגניזמים שאי פעם התקיימו (אני מהמר על כך שהמספר הזה אינו גדול יותר מ-\( 10^{30} \), למרות שאולי זה שקר גס) לא תצטרכו לבדוק יותר מ-100 שמות.

כעת נחזור לעניין הפצצה. נניח שיש לנו \( N \) מקומות אפשריים שבהם הפצצה יכולה להיות מוחבאת. אפשר לעבור ולנתק אותם אחד אחד ולראות מה קורה. אפשרות אחרת - לנתק חצי מהם בבת אחת, ולראות מה קורה. אם המצלמה הוחשכה, פסלנו חצי מהמקומות - כל אלו שלא הוחשכו; ואם היא לא הוחשכה, פסלנו חצי מהמקומות - כל אלו שכן הוחשכו. בקיצור, גם כאן יידרשו לנו רק \( \log N \) בדיקות - הרבה יותר אפקטיבי מלהחשיך כל מקום לחוד (כמובן שייתכן שאחרי שנחשיך את המצלמה ונחזיר את החשמל, המצלמה לא תשוב לפעול - ואז נרגיש די מטומטמים).

שימו לב להבדל שבין דוגמת הפצצה ודוגמת ספר הטלפונים - בדוגמת הפצצה שום דבר לא ממויין בשום צורה, ואנחנו לא בודקים אף מקום בצורה ישירה. מה אם כן הרעיון הבסיסי המשותף לשני המקרים? שבשניהם אנחנו מבצעים חלוקה לשניים, ואז מקבלים אינדיקציה כלשהי באיזה משני החלקים מה שאנחנו מחפשים נמצא. במקרה של ספר הטלפונים, האינדיקציה נובעת מהפעולה של “קרא שם מהספר, השווה את השם שאתה מחפש לשם הזה” ומכך שהספר ממויין; במקרה של הפצצה, האינדיקציה נובעת מהמצלמה שמכוונת על הפצצה. זהו, אם כן, הרעיון הבסיסי שעומד מאחורי חיפוש בינארי; רעיון מופשט שתקף גם עבור ספרי טלפונים וגם עבור פצצות. ההפשטה הזו היא לב לבה של המתמטיקה.

השימוש השני שאני רוצה לדבר עליו, משפט בולצאנו-ויירשטראס, דורש מעט יותר ידע במתמטיקה, ולכן אנסה להציג גרסה שלו שאיננה הכללית ביותר, אך היא דורשת מעט מאוד מושגים קודמים ולא מאבדת את הרעיון הכללי. נניח, אם כן, שאנו מתבוננים בקטע \( \left[0,1\right] \) שעל הישר הממשי, ויש לנו קבוצה \( A \) שמכילה אינסוף נקודות מתוך הקטע הזה. הטענה של בולצאנו-ויירשטראס היא שקיימת ל-\( A \) נקודת הצטברות בתוך הקטע. “נקודת הצטברות” היא נקודה \( x \), כך שבכל סביבה שלה, קטנה ככל שתהיה (אבל עם גודל שאינו אפס) יש נקודה מ-\( A \). במילים אחרות - לכל \( \varepsilon>0 \) קיימת נקודה \( a\in A \) שמרחקה מ-\( x \) הוא לכל היותר\( \varepsilon \): \( \left|x-a\right|\le\varepsilon \). המשפט הזה חשוב מאוד כאשר עוסקים בחשבון אינפיניטסימלי; לא אסביר כעת בפירוט מדוע (למתקדמים, רמז: כדי להראות שכל סדרת קושי של מספרים ממשיים מתכנסת, משתמשים בבולצאנו-ויירשטראס, או במשפט שקול לו).

הרעיון הוא זה: נחלק את הקטע \( \left[0,1\right] \) לשני חצאים: \( \left[0,\frac{1}{2}\right] \) ו-\( \left[\frac{1}{2},1\right] \). מכיוון ש-\( A \) היא קבוצה אינסופית, באחד משני החצאים הללו יש מספר אינסופי של נקודות מ-\( A \) (כי אם היה בשניהם מספר סופי, כך גם באיחוד שלהם, שהוא הקטע \( \left[0,1\right] \) כולו). נבחר אחד משני החצאים הללו שבו יש מספר אינסופי של נקודות, וגם אותו נחתוך לשניים - ושוב, נקבל שני קטעים שבאחד מהם מספר אינסופי של נקודות, נבחר אותו ונמשיך הלאה, וכו’ וכו’ וכו’, עד אינסוף.

התוצאה? סדרה של קטעים, שהאורך שלהם הולך וקטן עד אינסוף, וכל אחד מהם מכיל אינסוף נקודות מ-\( A \). תוך התבססות על תכונות המספרים הממשיים אפשר להראות שיש נקודה שמשותפת לכל סדרת הקטעים האינסופית הזו - זו תהיה הנקודה \( x \) שלנו. כעת, כדי להראות שלכל \( \varepsilon \) קיימת \( a\in A \) שקרובה מספיק ל-\( x \) פשוט מסתכלים על קטע מסדרת הקטעים שבנינו, שאורכו הכולל קטן מ-\( \varepsilon \); הוא מכיל אינסוף נקודות מ-\( A \), ולכן בוודאי שהוא מכיל נקודה אחת \( a \) כנדרש.

ההבדל בין ההוכחה הזו לבין החיפוש הבינארי שהצגתי קודם הוא בכך שפה ה”אינדיקציה” היא מעט שונה. אני לא מחפש נקודה מסויימת באחד משני הקטעים, אלא מתעניין בכך שיהיו בקטע שאני בוחר אינסוף נקודות מ-\( A \), מה שמבטיח שלמרות שסדרת הקטעים שאני בונה היא אינסופית, אף פעם לא “ייגמרו” הנקודות של \( A \) שנמצאות בתוכם. כמובן, ייתכן שבשני הקטעים יהיו אינסוף נקודות, ואז אבחר אחד מהם באופן שרירותי.

אם כן, בפעם הבאה שבה תצטרכו ללכוד אריה במדבר, או בספר טלפונים, או לאתר פצצה, אני מקווה שתדעו כיצד לעשות זאת ביעילות. האם תוכלו לתת עוד דוגמאות למקומות שבהם שיטה זו שימושית?