עוגה עוגה עוגה (נתהפכה כל היום עד אשר נמצא מקום)

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

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

1. אחרי כמה זמן כל הציפוי יהיה שוב למעלה כמו שהיה בהתחלה?
2. אחרי כמה זמן כל הציפוי יהיה למטה, כלומר הכל התהפך?

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

הנה איור שמתאר את המהומה הזו עבור \( \theta=\frac{\pi}{2} \) (“90 מעלות”):

בכל פעם שאני הופך פלח עוגה, אני קורא לזה “צעד”. אז אנחנו רואים שבמקרה הזה, אחרי ארבעה צעדים כל הציפוי יהיה למטה, ואחרי שמונה צעדים כל הציפוי יהיה למעלה. זו התשובה לחידה במקרה הזה. אבל המקרה הזה בבירור פשוט למדי - עבור זוויות אחרות די ברור שיהיו סיטואציות מסובכות יותר כמו זו שבה הפלח שחתכנו כרגע הוא חתיכה שכבר חתכנו בעבר , אז לכאורה כשננסה להפוך אותו הוא יתפרק לשניים והכל יימרח בכל מקום… אז בואו נניח שאנחנו יודעים להפוך פלחים-עם-חתכים בצורה מושלמת, כאילו הם הצליחו להידבק אחד לשני מחדש. עכשיו אפשר לשאול את השאלה עבור זווית קונקרטית לגמרי, למשל \( \theta=e^{-10} \) כאשר \( e=2.718\ldots \) הוא בסיס הלוגריתם הטבעי המוכר. כאן אני מודד זוויות עם רדיאנים, כלומר בכל צעד אני עובר \( \frac{\theta}{2\pi}=\frac{1}{2\pi e^{10}} \) מעגל.

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

אוקיי, כולנו חשבנו על החידה? אפשר להמשיך ולהתחיל לספיילר חופשי? יופי. ראשית - לא, אין שום משחק ניינטיז (ועכשיו קצת עצוב לי שאין), זו תמונה מג’ונרטת מן הסתם. שנית, מה שהאינטואיציה שלי הולכת אליו מייד בהקשר של החידה הזו הוא טיעון שמבוסס על אי רציונליות שבא להוכיח שהציפוי אף פעם לא יחזור כולו למעלה או יגיע כולו למטה. העניין הוא כזה - אם אני מטייל לי מסביב לעוגה בצעדים שכל אחד מהם עובר בדיוק \( \omega \)-מעגל כש-\( \omega \) הוא מספר אי רציונלי אז כשאני מסיים סיבוב סביב העוגה אני לא אחזור בדיוק למקום שממנו התחלתי. גם לא בפעם השניה. או השלישית. או כל פעם אפשרית. כי אם מתישהו חזרתי לנקודת ההתחלה, נאמר אחרי \( k \) צעדים ו-\( t \) הקפות של המעגל, אז צריך להתקיים \( k\omega=t \) כלומר \( \omega=\frac{t}{k} \) מה שמראה שהוא רציונלי. זה מה שיקרה, למשל, אם \( \theta=\frac{4\pi}{3} \), כלומר אם בכל פעם אנחנו עוברים 240 מעלות מהמעגל, שזה \( \frac{2}{3} \) ממנו: נצטרך \( k=3 \) צעדים כדי להגיע לנקודת ההתחלה בסיום הקפה מספר \( t=2 \) של המעגל.

האם במקרה שלנו \( \omega \) הוא אי רציונלי? לכאורה כן, הרי השתמשנו ב-\( e^{-10} \) המאוד לא רציונלי בהגדרה שלו. אבל \( \omega \) (החלק היחסי של המעגל שאנחנו עוברים בכל פעם) הוא \( \omega=\frac{\theta}{2\pi}=\frac{1}{2\pi e^{10}} \) ולכן מעורבת כאן השאלה האם \( \pi e^{10} \) זה גם כן מספר אי רציונלי וזו… שאלה פתוחה, ככל שידוע לי.

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

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

אם יש לנו פלח עוגה שכבר יש בו חתך, ואנחנו מרימים את כולו והופכים אותו, החתך לא יישאר במקום שבו הוא היה קודם - הוא יעבור לצד השני, כאילו הפעלנו עליו שיקוף במראה שנמצאת בדיוק באמצע הפלח. הנה הדגמה של איך זה נראה, כשהזווית שבה אנו זזים בכל פעם היא 270 מעלות:

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

עכשיו בואו נדבר פחות באוויר ונראה את המתמטיקה הקונקרטית שמעורבת, ואיך אפשר למצוא אחרי כמה זמן הכל יחזור למעלה. בואו נתחזק קבוצה \( A \) שכוללת את כל הזוויות שבהם יש חתכים בעוגה. בהתחלה הקבוצה הזו ריקה, \( A=\emptyset \). החתך הראשון קובע את נקודת הייחוס שעל פיה אנחנו מודדים את הזווית של שאר החתכים, אז אחריו \( A=\left\{ 0\right\} \). החתך הבא יהיה בזווית של \( \theta \) ביחס אליו, אז \( A=\left\{ 0,\theta\right\} \), ועכשיו אנחנו מתקדמים כל פעם ב-\( \theta \), כך שהקבוצה שלנו היא לכאורה \( A=\left\{ 0,\theta,2\theta,3\theta,\ldots\right\} \). אבל זה לא נמשך עד אינסוף ככה. מרגע שבו נשלים את הסיבוב הראשון סביב העוגה הסיפור יתחיל להסתבך, אז אנחנו צריכים להבין מתי בדיוק זה קורה.

בואו נסמן ב-\( k \) את מספר החתך הראשון שבו אנחנו אחרי סיבוב שלם סביב העוגה. כלומר, \( k\theta\ge2\pi \) אבל \( \left(k-1\right)\theta<2\pi \). יש במתמטית דרך פשוטה להגדיר את \( k \): \( k=\left\lceil \frac{2\pi}{\theta}\right\rceil \) (הסוגריים הללו מציינים ערך שלם עליון: אנחנו מעגלים למספר השלם הקרוב ביותר שגדול מ-\( \frac{2\pi}{\theta} \)). עכשיו, תהיה חשיבות גדולה לשאלה כמה החתך ה-\( k \) חורג “מעבר” לסיבוב שלם - מה ההפרש בין נקודת החיתוך הזו ונקודת הייחוס שלנו שסימנתי ב-\( 0 \). אז אני אסמן את ההפרש הזה ב-\( \delta \): \( \delta=k\theta-2\pi \). זהו, אלו כל הסימונים שנזדקק להם. כל הפתרון עכשיו יהיה במונחים של \( k,\delta \). עכשיו, המקרה שבו \( \delta=0 \) הוא פשוט מדי - כבר ראינו אותו למעלה. תוך סיבוב אחד כל העוגה הפוכה ותוך סיבוב אחד נוסף היא חוזרת לעצמה. אז נעזוב את המקרה הזה ונניח ש-\( \delta>0 \).

רגע לפני החיתוך הגורלי הזה, קבוצת החיתוכים שלנו היא

\( A=\left\{ 0,\theta,2\theta,\ldots,\left(k-1\right)\theta\right\} \)

רגע אחריו קורים שני דברים. ראשית, אני מוסיף חיתוך ב-\( \delta \) (כלומר, החיתוך הוא ב-\( \theta k \) אבל מכיוון שעברנו את קו הגבול של \( 2\pi \) אנחנו עושים את כל החשבון מודולו \( 2\pi \)). שנית, עכשיו החתך 0 “כלוא” בין החתך ב-\( \left(k-1\right)\theta \) ו-\( \delta \) ולכן כשהופכים את הפלח שבו הוא נמצא, הוא הולך להשתנות. הוא כבר לא יהיה 0. הוא יהיה… אה… אוקיי, זה חישוב מעצבן, מה? יודעים מה, בואו נשנה טיפה את דרך ההצגה של הסיפור כדי שיהיה לי קל יותר לבצע את החישוב הזה.

בואו נדמיין לרגע סיטואציה פשוטה יותר: יש לי פלח ששתי נקודות הקצה שלו הן 0 ו-\( \theta \) ובתוכו כלוא חתך אחר שנמצא ב-\( x \). לאן הוא עובר כשהופכים את הפלח? קודם המרחק שלו מהחתך 0 היה \( x \); אחרי ההיפוך, החתך 0 נמצא במקום \( \theta \); היפוך שומר על מרחקים, אז החתך הכלוא עדיין במרחק \( x \) מהחתך 0-לשעבר, כלומר הוא חייב להיות ב-\( \theta-x \) (כי \( \theta+x \) בכלל לא במסגרת הפלח הזה). זה היה חישוב פשוט! אבל לחשב לאן עובר מי שכלוא בין \( \left(k-1\right)\theta \) ו-\( \delta \) זה כאב ראש כשזוכרים שצריך לעבוד מודולו, ושכל הזמן הקואורדינטות של הפלח הנוכחי ישתנו. אז במקום זה בואו נחשוב על הסיטואציה ככה: אני תמיד חותך את החתך הנוכחי שלי ב-0; ואחרי כל חתך והיפוך פלח אני מסובב את העוגה ב-\( \theta \), בצורה כזו שמוסיפה \( \theta \) לכל זווית.

בגישה הזו, האלגוריתם שלוקח את \( A \) ומרחיב אותה על ידי הוספת החתך החדש, תוך תיקון חתכים ש”מתהפכים” עובד כך:

1. נאתחל \( A=\emptyset \)
2. נחזור שוב ושוב על הפעולה הבאה:
1. נאתחל \( A^{\prime}=\left\{ 0\right\} \) (אלו יהיו החתכים החדשים, אחרי הצעד שאנחנו עושים, ובפרט יהיה ב-\( A^{\prime} \) את החתך שעשינו ב-0)
2. לכל \( x\in A \) נעשה:
1. אם \( 0<x<\theta \) אז \( x\leftarrow\theta-x \) (כלומר, אני מציב את הערך החדש בתוך \( x \); זה ההיפוך של חתך "כלוא").
2. נוסיף את \( \left(x+\theta\right)\text{ mod }2\pi \) אל \( A^{\prime} \) (זה הסיבוב שמבצעים אחרי החיתוך וההיפוך).
3. אם \( A^{\prime}=A \), נעצור. אחרת \( A\leftarrow A^{\prime} \).

עם איזה \( A \) נסיים בסופו של דבר? מכיוון שכל הזמן אנחנו מוסיפים את 0, יהיה ב-\( A \) כל הזמן את 0, ואת כל ההזזות של \( 0 \) עד שעוברים את \( 2\pi \), כלומר \( \left\{ 0,\theta,2\theta,\ldots,\left(k-1\right)\theta\right\} \) שראינו קודם. בנוסף לכך, כשניקח את \( \left(k-1\right)\theta \) ונוסיף לו \( \theta \) נקבל \( \delta \). עכשיו, שימו לב! ה-\( \delta \) הזה כלוא בדיוק בפלח שהולכים להפוך כי \( 0<\delta<\theta \). לכן ההיפוך הולך להפוך אותו ל-\( \theta-\delta \) ומייד אחר כך הסיבוב יביא אותו אל \( 2\theta-\delta \). עכשיו הוא כבר חמק מהפלח שהופכים, ולכן לא יתהפך שוב אלא ימשיך להסתובב עוד ועוד. נקבל את \( 3\theta-\delta \) ואת \( 4\theta-\delta \) וכן הלאה וכן הלאה עד שנגיע שוב להשלמה של סיבוב, וזה יהיה ב-\( \left(k-1\right)\theta-\delta \). מייד אחר כך נגיע אל \( k\theta-\delta=2\pi \), כלומר חזרה אל 0. בינגו! איכשהו כן חזרנו אל נקודת המוצא שלנו, אפילו אם \( \theta \) הוא אי רציונלי, אחרי בדיוק שתי הקפות סביב המעגל. איך זה קרה? אז כאמור, זה לא באמת קרה כי שיניתי את נקודת המבט שלי - עכשיו אני בכל פעם מסובב את העוגה כך שהחתך שאני עושה הוא ב-0. זה אומר שאולי אני חותך כל פעם בזווית שונה, אבל בגלל האופן שבו החתכים זזים החיתוכים שלי הם רק בתוך חתכים קיימים.

אז בגישה הנוכחית שלנו לזוויות, קבוצת כל החתכים הולכת להיות

\( A=\left\{ 0,\theta,2\theta,\ldots,\left(k-1\right)\theta,\delta,2\theta-\delta,\ldots,\left(k-1\right)\theta-\delta\right\} \)

בקבוצה הזו יש בסך הכל \( 2k-1 \) חתכים, והם מגדירים \( 2k-1 \) פלחים שאפשר לכתוב במפורש:

\( \left[0,\delta\right],\left[\delta,\theta\right],\left[\theta,2\theta-\delta\right],\left[2\theta-\delta,2\theta\right],\ldots,\left[\left(k-2\right)\theta,\left(k-1\right)\theta-\delta\right],\left[\left(k-1\right)\theta-\delta,\left(k-1\right)\theta\right],\left[\left(k-1\right)\theta,0\right] \)

יש כאן שני סוגים של פלחים: כאלו שהאורך שלהם הוא \( \delta \), וכאלו שהאורך שלהם הוא \( \theta-\delta \). הפלחים מהסוג הראשון הם

\( \left[0,\delta\right],\left[\theta,2\theta-\delta\right],\left[2\theta,3\theta-\delta\right],\ldots,\left[\left(k-1\right)\theta,0\right] \)

וכאן יש \( k \) פלחים סך הכל, והפלחים מהסוג השני הם

\( \left[\delta,\theta\right],\left[2\theta-\delta,2\theta\right],\ldots,\left[\left(k-1\right)\theta-\delta,\left(k-1\right)\theta\right] \)

וכאן יש \( k-1 \) פלחים.

על מצב העוגה בכל רגע נתון אפשר לחשוב בתור סימון, לכל פלח, האם הוא הפוך באותו רגע או לא (“וקטור בינארי מאורך \( 2k-1 \)). עכשיו מגיע הפאנץ’: בכל פעם שבה אנחנו מבצעים חתך והופכים את העוגה, אנחנו הופכים פלח בגודל \( \theta \) שמורכב משני תת-פלחים, אחד מגודל \( \delta \) והשני מגודל \( \theta-\delta \). אחרי שביצענו \( k \) צעדים הפכנו את כל ה-\( \delta \)-פלחים, ואחרי שנבצע עוד \( k \) צעדים נהפוך את כולם בחזרה וכן הלאה; אבל עבור ה-\( \theta-\delta \)-פלחים, זה יקרה כל \( k-1 \) צעדים, לא כל \( k \) צעדים. כלומר, כדי שכל הפלחים בעוגה יתהפכו בחזרה, אנחנו צריכים שמספר הצעדים הכולל שלנו \( T \) יהיה כפולה זוגית גם של \( k \) וגם של \( k-1 \). כפולה, כדי שהוא יעבור על כל הפלחים מאותו סוג אותו מספר פעמים; זוגית כי אחרי שעוברים מספר זוגי של פעמים על פלח מחזירים אותו למצב המקורי שלו.

עכשיו, \( k,k-1 \) הם מספרים זרים - אין להם מחלק משותף גדול מ-1. זה אומר שהמספר הקטן ביותר שמתחלק על ידי שניהם (מה שנקרא ה-lcm שלהם) הוא המכפלה שלהם, \( k\left(k-1\right) \). המכפלה הזו היא מספר זוגי, אבל היא לא כפולה זוגית שלהם, כלומר זה לא מספר שמתקבל על ידי כך שמכפילים אותם במספר זוגי. למשל, אם \( k \) אי זוגי אז \( k\left(k-1\right) \) מתקבל מ-\( k-1 \) על ידי כפל שלו ב-\( k \) שאיננו מספר זוגי. אז אם נבצע \( k\left(k-1\right) \) צעדים, נראה שכל הפלחים בעוגה מסוג אחד הם למעלה, וכל הפלחים מהסוג השני הם למטה. הכפולה הזוגית הקטנה ביותר היא \( 2k\left(k-1\right) \).

אם נחזור למספר הקונקרטי שהתחלתי איתו, \( \theta=e^{-10} \), החישוב עכשיו הוא מאוד פשוט: מחשבים את \( k=\left\lceil \frac{2\pi}{\theta}\right\rceil \) ואז את \( 2k\left(k-1\right) \). מקבלים \( k=138397 \) ו-\( 2k\left(k-1\right)=38307182424 \). אלו לא מספרים שיש להם משמעות מעניינת, אבל אם פתרתן את החידה קודם וקיבלתן תוצאה מספרית, אפשר להשוות אותה למה שאני קיבלתי.

אוקיי, זה טיפל בשאלה מתי כל הציפוי חוזר למעלה. מה עם הגעה של כל הציפוי למטה? גם פה האינטואיציה הולמת בי - האינטואיציה הראשונית היא שזה צריך להיות בדיוק באמצע הדרך, כלומר לקחת את התוצאה שקיבלתי ולחלק ב-2. האינטואיציה הזו נכונה בדוגמא שראינו למעלה עם \( \theta=\frac{\pi}{2} \), אבל כמו שאמרתי, הדוגמא הזו הייתה פשוטה מדי; בחרתי בכוונה מקרה שבו \( \delta=0 \). כאשר \( \delta>0 \) כבר ראינו שאמצע הדרך, \( k\left(k-1\right) \), לא הולך לעבוד כי חצי מהעוגה יהיה הפוך וחצי לא. אז מה כן יעבוד? אנחנו צריכים מספר שהוא כפולה אי זוגית של \( k,\left(k-1\right) \), אבל זה פשוט בלתי אפשרי. כל כפולה של \( k,\left(k-1\right) \) תתחלק על ידי הכפולה המשותפת הקטנה ביותר \( k\left(k-1\right) \) והיא תמיד מספר זוגי; מצד שני, אחד מבין \( k,\left(k-1\right) \) הוא אי זוגי ולכן כשנכפול אותו במספר אי זוגי נקבל מספר אי זוגי. אז פשוט לא קיימת כפולה אי זוגית משותפת של \( k,\left(k-1\right) \) והציפוי אף פעם לא יהיה כולו למטה.

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