משפט זקנדורף

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com