משפט זקנדורף

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

בסיסי ספירה הם משהו שאנחנו מכירים עוד בבית הספר היסודי: אנחנו יודעים שהמספר שנכתב בתור 142 הוא המאה מאה ארבעים ושתיים, מכיוון שאנו מפרשים אותו באופן הבא: 2 כפול אחד (ספרת האחדות) ועוד 4 כפול עשר (ספרת העשרות) ועוד 1 כפול מאה (ספרת המאות) וכך אנו עושים באופן כללי לכל מספר: אנחנו מחברים את הספרות כשכל ספרה מוכפלת בחזקה כלשהי של 10 (אחד הוא \( 10^{0} \), עשר הוא \( 10^{1} \), מאה הוא \( 10^{2} \) וכן הלאה). המספר 10 כאן הוא שרירותי לגמרי; אפשר גם לעבוד עם חזקות של 2 (בסיס בינארי) או של 8 (בסיס אוקטלי) או של 16 (בסיס הקסדצימלי - כאן אנו נזקקים ל-16 ספרות שונות ולכן משתמשים באותיות גדולות מהא”ב הלטיני) וגם כל מספר אחר (נאמר 3, או 7) הוא לגיטימי. המאיה השתמשו בבסיס 20 והבבלים השתמשו בבסיס 60.

אני רוצה הפעם להשתמש בבסיס שונה לגמרי. כזה שבו המקדמים לא מוכפלים רק בחזקות של מספר אחד מסויים, אלא בסדרה “מעניינת” של מספרים. הסדרה הזו תהיה סדרת מספרי פיבונאצ'י. הצגתי אותה כבר בעבר, אבל הנה היא בקצרה שוב: נגדיר \( F_{0}=0 \) ו-\( F_{1}= \), וכעת לכל \( n>1 \) נגדיר \( F_{n}=F_{n-1}+F_{n-2} \). נקבל את הסדרה הבאה: \( 0,1,1,2,3,5,8,13,21,\dots \). שני המספרים הראשונים לא הכי רלוונטיים עבורנו (כי מ-0 אי אפשר לקבל מספרים אחרים על ידי כפל, וה-1 בתחילת הסדרה מופיע פעמיים) אז בפוסט הזה אתייחס לסדרה \( 1,2,3,5,8,13,21,\dots \).

סדרת פיבונאצ’י היא מהסדרות המפורסמות במתמטיקה, אם לא המפורסמת שבהן, ומהרבה סיבות מתמטיות אובייקטיביות. אז אם לקחת משהו “מעניין” בתור בסיס ספירה, למה לא לקחת אותם? כמובן, צריך להגביל באופן מסויים את הצורה שבה בונים מהם מספרים; בפרט, צריך להגביל את גודל המקדם שבו כופלים כל אחד מהמספרים. בבסיס עשרוני הגודל המקסימלי של מקדם הוא 9; בבסיס בינארי הוא 1. במה כדאי לבחור? ובכן, אחד מהדברים שאנו מעוניינים בהם כאשר אנו מייצגים מספרים בבסיס מסוים הוא שהייצוג יהיה יחיד. אם אותו מספר ניתן לייצוג בכמה דרכים שונות זה עשוי לגרום לבעיות בהוכחות מסויימות שמניחות במובלע יחידות של הייצוג. כעת, אם נרשה אפילו ל-2 להיות מקדם, כבר קל לראות שייצוג יחיד הולך לאיבוד בלא מעט מקרים: למשל, \( 16=2\cdot8=1\cdot3+1\cdot13 \), ולכן אם נכתוב את 16 בבסיס פיבונאצ’י נקבל את שתי דרכי הכתיבה \( 100100 \) ו-\( 20000 \) (אם לא ברור לכם למה שתי דרכי הכתיבה הללו מייצגות את 16 בבסיס פיבונאצ’י זו הזדמנות טובה לעצור לרגע ולוודא שאתם מבינים את הרעיון בבסיסי ספירה).

אז בואו נגביל את עצמנו רק למקדמים שהם 0 ו-1. במילים אחרות, כל מה שמותר לנו לעשות כדי לקבל מספר מסויים הוא לקחת קבוצה מסויימת של מספרי פיבונאצ’י ולחבר אותם ולקוות שנקבל את המספר שאותו אנו מקווים לקבל. אלא שעדיין אין לנו ייצוג יחיד! למעשה, אם תחשבו שניה תראו שקיימים המון מספרים שאין להם ייצוג יחיד. מי הם? מספרי פיבונאצ’י, כמובן… למשל, \( 21 \) הוא גם \( 1000000 \) וגם \( 110000 \), ותופעה דומה תהיה עבור כל מספר פיבונאצ’י אחר שגדול או שווה ל-3. אז מה עושים? מנסים למצוא עוד הגבלה. אבל איך אפשר להגביל סיטואציות שהן כל כך פשוטות כמו \( 1000000 \) ו-\( 110000 \)? ובכן, אולי… אם נאסור על שני 1 להופיע ברצף?

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

פורמלית, אני רוצה להראות שלכל מספר טבעי \( n \) קיימת ויחידה סדרה \( a_{2},a_{3},\dots,a_{k}\in\left\{ 0,1\right\} \) כך ש-\( n=\sum_{i=2}^{k}a_{i}F_{i} \) (זכרו שהשלכתי מסדרת פיבונאצ’י את שני האיברים הראשונים) ו-\( a_{i}a_{i+1}=0 \) לכל \( 2\le i<k \) (זו דרך נאה לנסח את הקריטריון של “אין שני מופעים רצופים של 1”) ו-\( a_k=1 \) (כי אחרת בוודאי שלא יהיה לנו ייצוג יחיד - אפשר להוסיף עוד ועוד אפסים לסוף הסדרה). אם כן, זה המשפט, ועצם זה שהוא נכון הוא מגניב למדי, אבל מטרת הפוסט הזה היא גם להראות לכך הוכחה כלשהי.

נתחיל עם הוכחת הקיום, כלומר שכל מספר טבעי ניתן לייצג בצורה הזו. ההוכחה תהיה, מה לעשות, באינדוקציה על המספר. עבור \( n=1,2,3 \) המשפט מובן מאליו כי שלושת אלו הם מספרי פיבונאצ’י. נניח אם כן שלכל מספר קטן מ-\( n \) אנו יודעים למצוא ייצוג זקנדורף ונמצא כזה עבור \( n \) עצמו. מה שמתבקש לעשות הוא להגיד משהו כזה: “יהא \( F_{k} \) מספר פיבונאצ’י הגדול ביותר שעודנו קטן או שווה ל-\( n \). אם \( F_{k}=n \) סיימנו; אחרת , בואו נסתכל על המספר \( t=n-F_{k} \). הוא קטן מ-\( n \) אז יש לו ייצוג זקנדורף, ופשוט נוסיף את \( F_{k} \) בסוף שלו”. זה כמובן היה מסיים את ההוכחה אלמלא החלק המעצבן הזה של לאסור על שני מספרי פיבונאצ’י רצופים בסוף הייצוג, והחלק המעצבן הזה של לאסור על מקדם גדול מ-1. הבעיה הראשונה תתרחש אם \( F_{k-1} \) מופיע בייצוג זקנדורף של \( t \), והבעיה השניה תתרחש אם \( F_{k} \) עצמו מופיע בייצוג זקנדורף של \( t \).

שתי הבעיות הללו הן לא בעיות אמיתיות כי אפשר להראות שאם משהו מהן מתרחש, אז \( F_{k} \) הוא לא באמת מספר פיבונאצ’י הגדול ביותר שעדיין קטן מ-\( n \). כדי לראות זאת, בואו נניח ש-\( F_{k-1} \) או \( F_{k} \) מופיעים בייצוג של \( t \), כלומר בכל מקרה \( t\ge F_{k-1} \). מכאן ש-\( n=t+F_{k}\ge F_{k}+F_{k-1}=F_{k+1} \), דהיינו \( n \) גדול לפחות כמו \( F_{k+1} \), מה שמסיים את העניין. זה גם מצביע לנו על האלגוריתם שבו אפשר למצוא את ייצוג זקונדורף של מספר: מתחילים ממספר פיבונאצ’י הגדול ביותר שקטן ממנו, מחסרים ואז ממשיכים ברקורסיה. למשל, כדי לייצג את 27 נחסר ממנו את 21, נקבל 6, נחסר ממנו את 5, נקבל 1 והנה קיבלנו את הייצוג \( 1001001 \) - כפי שאפשר לראות, אין שני מופעים רצופים של 1.

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

בואו נשתמש בסימונים הבאים: נכתוב \( n=a_{1}+a_{2}+\dots+a_{k} \) ו-\( n=b_{1}+b_{2}+\dots+b_{r} \) כך שכל ה-\( a \)-ים וה-\( b \)-ים הם מספרי פיבונאצ’י ומסודרים מהקטן לגדול. מטרתנו היא להראות ש-\( r=k \) וש-\( a_{i}=b_{i} \) לכל \( 1\le i\le k \).

ראשית, אם \( a_{k}=b_{r} \) אז סיימנו, כי אפשר פשוט לחסר את המספר המשותף הגדול הזה מ-\( n \) ולהשתמש בהנחת האינדוקציה: נסתכל על המספר \( n-a_{k}=a_{1}+\dots+a_{k-1}=b_{1}+\dots+b_{r-1} \) ומהנחת האינדוקציה נקבל ש-\( k-1=r-1 \) וש-\( a_{i}=b_{i} \) לכל \( 1\le i\le k-1 \).

אחרת, אנחנו חייבים להגיע לסתירה כלשהי כדי למנוע את האפשרות ששני הייצוגים הם באמת שונים. בואו נניח ש-\( a_{k} \) הוא הגדול מבין שני המספרים \( a_{k},b_{r} \). מה שאני רוצה לטעון הוא ש-\( a_{k} \) הוא גדול כל כך עד שכל הסכום \( b_{1}+b_{2}+\dots+b_{r} \) לא מסוגל לעבור אותו! כאן אני אהיה חייב מן הסתם להשתמש בכך שבסכום הזה אין שני מספרי פיבונאצ’י סמוכים, אחרת \( b_{r-1},b_{r} \) היו יכולים להיות בדיוק שני המספרים הקודמים ל-\( a_{k} \) בסדרת פיבונאצ’י.

אם כן, הבה ואנסח במפורש את הטענה שמסיימת את ההוכחה: אם \( A \) היא קבוצה של מספרי פיבונאצ’י כך שאין בה שניים סמוכים, ו-\( F_{k} \) הוא מספר פיבונאצ’י הגדול ביותר ב-\( A \), אז \( \sum_{F_{i}\in A}F_{i}<F_{k+1} \).

את הטענה הזו נוכיח… ניחשתם, באינדוקציה. במקרה הזה, על \( k \). כרגיל, עבור \( k=2 \) (זה הבסיס כי \( F_{0},F_{1} \) לא במשחק) נקבל את התוצאה באופן טריוויאלי (כי \( A \) חייבת להיות ריקה ולכן סכום איבריה הוא 0). נניח שהטענה נכונה לכל מספר עד \( F_{k} \) ונוכיח עבורו. נתבונן בקבוצה \( A \) כלשהי של מספרי פיבונאצ’י שקטנים מ-\( F_{k} \) כך שאין שניים סמוכים, ולכן בפרט לא ייתכן ש-\( F_{k-1} \) ו-\( F_{k-2} \) נמצאים בקבוצה גם יחד. נניח ש-\( F_{k-1} \) בפנים, אז כל יתר האיברים של \( A \) הם קטנים מ-\( F_{k-2} \), ולכן על פי הנחת האינדוקציה על \( F_{k-2} \) נקבל שסכום כל יתר איברי \( A \) קטן מ-\( F_{k-2} \), ולכן סכום כל אברי \( A \) קטן מ-\( F_{k-2}+F_{k-1}=F_{k} \). אותם שיקולים מסיימים את ההוכחה גם במקרה שבו דווקא \( F_{k-2} \) בפנים.

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