שאלות ותשובות - מקבץ מס’ 4

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

1. "הוכחה שפונקציה a*b היא חד חד ערכית" - כמובן שהטענה לא נכונה אם מרשים גם ל-a וגם ל-b להיות משתנים (למשל, 24=4*6=2*12). אם "מקפיאים" אחד מהם (נניח את b), התוצאה מתקבלת באמצעות שימוש בדיסטריביוטיביות ובכך שניתן "לצמצם": \( a_1b=a_2b\Rightarrow(a_1-a_2)b=0\Rightarrow a_1-a_2=0\Rightarrow a_1=a_2 \) וזו בדיוק ההגדרה של חד חד ערכיות. כדאי לשים לב שהנחת הדיסטריביוטיביות מתקיימת כמעט בכל מקום שבו יש טעם לדבר על כפל וחיבור (זו הצורה שבה בוחרים לרוב לקשור אותן יחד) אבל לא תמיד אפשר לצמצם - בחוגים שבהם יש מחלקי אפס, למשל, לא תמיד אפשר (ובפרט, כפל אכן מפסיק להיות חד חד ערכי).
2. "מספר העלים בעץ הוא לפחות" - בעץ "כללי" יכול להיות רק עלה בודד - אם העץ הוא "שרוך". אם לכל צומת פנימי בעץ יש לפחות שני בנים, ויש בו \( n \) צמתים, אז יש בו בדיוק \( \frac{n}{2} \) (המספר מעוגל כלפי מעלה) עלים. אפשר להוכיח זאת באינדוקציה: עץ בעל צומת בודד הוא גם בעל עלה בודד (חצי מעוגל כלפי מעלה). לכל עלה שנהפוך לצומת פנימי אנחנו חייבים להוסיף לו שני בנים (עלים, עד שנוסיף גם להם בנים) ולכן קיבלנו שני עלים חדשים תמורת חיסול של עלה אחר - דהיינו, לכל שני צמתים שהוספנו לעץ, קיבלנו עלייה של 1 במספר העלים שבו. תרגיל: לנסות להכליל עבור עצים שבהם לכל צומת פנימי יש עוד יותר בנים. אגב, לאחר שכתבתי את התשובה לשאלה הזו צצה שאלה נוספת - "עץ בינארי מספר הצמתים שדרגתם 2 קטן ב-1 ממספר ה". אני משער שה"ה" הוא מספר העלים - ושוב, שגם כותב השאלה הזו מניח שלכל צומת יש או שני בנים או כלום.
3. "קשר בין כפל וחילוק במתמטיקה" - נהוג לחשוב על חילוק בתור "הפעולה ההפוכה לכפל", וניתן להציג זאת כך: החלוקה של \( c \) ב-\( b \) היא מספר כלשהו \( a \) שמקיים את התכונה לפיה אם כופלים את \( b \) ב-\( a \) מקבלים בדיוק את \( c \). באופן קצת יותר פורמלי, נהוג להגדיר לכל מספר \( a \) את המספר ההופכי לו, \( a^{-1} \) - המספר שמקיים את התכונה \( aa^{-1}=1 \). בגישה זו, חלוקה ב-\( a \) מוגדרת ככפל ב-\( a^{-1} \). זה גם מסביר מדוע לא ניתן לחלק באפס - אין לו הופכי, כי אפס כפול כל דבר הוא אפס (ובפרט, אי אפשר לקבל את 1 על ידי כפל משהו באפס).
4. "שיטות שונות בכפל רב איבר ברב איבר"  - רב איבר הוא השם העברי (ולטעמי, הנוח פחות) לפולינום. כפל שני פולינומים דורש את חישוב המקדמים של פולינום המכפלה. לכאורה, כל מקדם בפולינום המכפלה צריך להיות סכום של מכפלות של מקדמים משני הפולינומים שמוכפלים, והתוצאה תהיה סיבוכיות שהיא ריבועית בדרגת הפולינומים המוכפלים; בפועל, אפשר לשפר את הסיבוכיות הזו באמצעות שימוש (למשל; אני בטוח שיש עוד דרכים) בהתמרת פורייה המהירה. אני מקווה להרחיב על כך בעתיד.
5. "קובץ שגודלו 2k מכיל 2048 תווים" - התשובה חיובית. יחידת המידע הבסיסית ביותר במחשב היא הביט (Bit - סיבית בעברית, אך איני אוהב גם את העברות הזה). ביט מסוגל להחזיק או 0 או 1, ובאמצעות שני ערכים אלו קל לייצג כל ערך אחר שהוא בר-תרגום פשוט למספרים טבעיים. עם זאת, למעבדים לא נוח לעבוד עם סיביות בודדות ויותר קל לעבוד עם קבוצות של ביטים; מסיבות היסטוריות התגלגל שהקבוצה ה"מעניינת" הראשונה היא בגודל 8 ביטים, וקבוצה שכזו נקראת בייט (Byte, ובעברית בית). הבייט הוא יחידת המידה המקובלת לגודל של קובץ. במקרה או שלא במקרה, הטיפוס הבסיסי לתו, שנמצא ברוב שפות התכנות (Char, מלשון Character) תופס בייט בודד (דהיינו, ממש נדרש בסטנדרט של השפה שזה יהיה גודלו).באמצעות בייט אחד ניתן לייצג מספרים בטווח 0-255, כך שזה מספיק כדי לתפוס תווים מעניינים רבים (אבל לא הכל - ולכן יש שיטות קידוד, למשל Unicode, שבהם חלק מהתווים דורשים יותר מבייט אחד). כעת, מדידת גודל קבצים במחשב נעשית בצורה שעשויה קצת להטעות. מסיבות שונות ומשונות של יעילות, נוח לעבוד בעיקר עם חזקות של 2 במחשב. לכן כשמודדים גודל של קובץ, הקיצורים מתייחסים לחזקות של 2 ולא של 10. כך "k", שמייצג קילו, אין פירושו "1,000 בייט" אלא "1,024 בייט" - זוהי החזקה של 2 שהיא קרובה ביותר למספר 1,000. בדומה, גם "מגה בייט" איננו 1,000 קילובייט, אלא 1,024 קילובייט (כמה זה יוצא בבייטים?) וכן הלאה. לכן קובץ שגודלו 2k מכיל 2,048 תווים (עם זאת, כמובן שאין הכרח שתוכן הקובץ יהיה תווים - קובץ תמונה, למשל, מכיל מידע על איזה צבע צריך להופיע איפה - אבל אפשר לחשוב על המידע הזה גם בתור תווים, רק שהם לא יצטרפו לטקסט בעל משמעות באנגלית).
6. "לוח כפל חבורה מסדר 5" - ראשית, יש רק חבורה אחת כזו, כי 5 הוא מספר ראשוני: על פי משפט לגראנז', סדר של איבר בחבורה חייב לחלק את סדר החבורה; לכן הסדר של כל איבר שאיננו היחידה חייב להיות 5, כי לא קיים מספר בין 1 ו-5 שמחלק את 5. מכאן שחבורה מסדר 5 חייבת להיות ציקלית, ויש רק אחת כזו. כעת קל יחסית לתאר את לוח הכפל שלה: מסמנים כל שורה וכל עמודה בתור החזקה של אחד מהיוצרים (כלומר, בתור \( a^0, a^1, \dots, a^4 \)) ומה שיופיע בתוך התא המתאים בטבלה יהיה החזקה שמתאימה לחיבור מודולו 5 (למשל, בתא של \( a^3 \) ו-\( a^4 \) יופיע \( a^2 \)).
7. "כל מספר שהמעריך שלו הוא אפס שווה לאחד" - כלומר \( x^0=1 \) לכל \( x \). זו לא טענה שאפשר להוכיח, אלא הגדרה; אנחנו הרי מתחילים בכך שאנו מגדירים חזקות רק למעריכים שהם טבעיים שונים מאפס (\( x^1=x, x^{k+1}=x^k\cdot x \)). לכן אם מדברים על מעריכים אחרים, צריך להגדיר אותם, לרוב באמצעות מה שכבר הגדרנו, ועם נסיון לשמור על אחידות מסויימת. במקרה של מעריך אפס, אנחנו מנסים לשמור על כלל החזקות הידוע \( \frac{x^a}{x^b}=x^{a-b} \) שתקף כל עוד \( a>b \) והם טבעיים; אם הם היו שווים, אז היינו מקבלים בצורה "פורמלית" את המשוואה \( 1=\frac{x^a}{x^a}=x^{a-a}=x^0 \), כך שאנחנו נדחפים להגדרה של החזקה בתור 1. מתי בכל זאת זה לא עובד? כשמדברים על החזקה של 0, כי הרי לא ניתן לחלק באפס ולכן המוטיבציה הקודמת לא ממש תקפה. לכן לפעמים משאירים את הביטוי \( 0^0 \) בלתי מוגדר. מצד שני, לפעמים נוח להגדיר אותו פורמלית בתור \( 0^0=1 \) למרות זאת - למשל, כשרוצים לכתוב את נוסחת הבינום של ניוטון ולהרשות לאחד המחוברים להיות 0.
8. "איך לפתור את השערת גולדבך"  - למרבה הצער, כנראה שאין דרך פשוטה לעשות זאת. זה לקח חשוב באופן כללי - המתמטיקאים מתעסקים בבעיות קשות, אפילו אם הניסוח שלהן נראה קל. את רוב הבעיות בכלל לא מצליחים לפתור. יש עוד המון מה לעשות, ואין תשובות קסם. בכך, לפחות, המתמטיקה היא מדע ככל המדעים, ונבדלת מהבלי "העידן החדש".
9. "בכמה דרכים ניתן להציג את המספר 19 כסכום" - כמובן שהשאלה  לא מוגדרת היטב: סכום של מה? אם, למשל, רוצים סכום של מספרים שלמים, אז יש אינסוף דרכים להציג אותו ככזה (19 ועוד 0; 20 ועוד מינוס 1; 21 ועוד מינוס 2, וכו'). אם רוצים סכום של שני ראשוניים (למה? לא יודע) אז יש אחת: 17+2. אבל מה שעולה לי לראש כשמדברים על סכום שכזה הוא פשוט סכום של מספרים טבעיים. כך למשל 19 הוא אפשרות אחת להציג את 19 כסכום; אפשרות אחרת היא 1+18; עוד אפשרות היא 5+5+5+3, וכן הלאה. באופן כללי, בהינתן מספר טבעי, הבעיה של מציאת מספר החלוקות שלו - מספר הדרכים להציג אותו כסכום מספרים טבעיים - היא בעיה קשה בקומבינטוריקה ולא ידוע לה פתרון מוצלח, לא כל שכן נוסחה. עבור 19 יש עוד מספר קטן יחסית של חלוקות, אז אפילו בשיטה של "Brute force" אפשר לגלות את התשובה: 490.
10. "דוגמאות לדילמת האסיר" - בסרט "האביר האפל" שיצא לאחרונה יש דוגמה נאה לדילמה. לגלות עוד יהיה ספוילר, ולכן אני כותב את ההמשך בצבע לבן (כדי לראותו יש לסמן אותו עם העכבר). בסרט ישנה סיטואציה בה נוסעי שתי ספינות מגלים חומרי נפץ על ספינותיהם, וניתנים להם נפצים, אשר (כך נטען) יפעילו את חומר הנפץ בספינה השניה. מציבים בפניהם אולטימטום: אם עד כך-וכך לא תפוצצו את הספינה השניה, נפוצץ את שניכם. האיום הנוסף הזה קצת מוציא את עוקץ הדילמה (בדילמת האסיר האמיתית יש הבדל מהותי בין המקרה שבו שני האסירים שותקים ובין המקרה בו הם מדברים) אך מכיוון שאנו, כצופים, מצפים לכך שיצליחו להציל את נוסעי שתי הספינות אם הם רק יתאפקו קצת עם הנפצים, הרי שמנקודת מבטנו זוהי דילמת אסיר קלאסית.
11. "טקסטים של הצגות" - זו בדיחה דלוחה, ובכל זאת: אני ממליץ בתור התחלה על הטקסט "Linear Representations of Finite Groups" של Serre.