נטגר גליון 9

---

דבר העורך

רון אהרוני

קוראים יקרים.

מי שקורא את "נטגר" חזקה עליו שהוא אוהב מתמטיקה. אבל האם הוא יודע מה זו מתמטיקה?

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

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

 גם כתבנו הוותיק גדי אלכסנדרוביץ' תרם לנו משהו מן הבלוג שלו, "לא מדויק". וגם הוא נדרש לשאלה "מה זו מתמטיקה": מה הופך בעיה כה פשוטה כמו "איך לשלם סכום של $latex 31 $ שקלים עם מספר קטן ככל האפשר של מטבעות" לבעיה עם עומק מתמטי?

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

קריאה מהנה, העורך

---

בעיית המטבעות

גדי אלכסנדרוביץ

המאמר הבא פורסם בבלוג המתמטי "לא מדויק" ומפורסם פה פעם נוספת באדיבות גדי אלכסנדרוביץ'.

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

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

נתחיל מדוגמאות קונקרטיות. בישראל כיום יש לנו מטבעות עבור 10 אגורות, 50 אגורות, 1 שקל, 2 שקלים, 5 שקלים, 10 שקלים, 20 שקלים, 50 שקלים, 100 שקלים ו-200 שקלים. המילה "מטבעות" קצת מטעה, כמובן, כי 20,50,100,200 הם סכומים שבאים בשטרות, לא במטבעות; אבל אני משתמש במילה "מטבעות" כדי לתאר כל סוג של כסף מזומן. כמו כן, אין לי כוח לאגורות אז בואו נשכח מקיומן ונדבר רק על סכומים שהם מספר שלם של שקלים. עכשיו, איך אפשר לייצג 12 ש"ח? הנה כמה דרכים: אפשר להשתמש ב-12 מטבעות של 1 ש"ח; אפשר להשתמש ב-6 מטבעות של 2 ש"ח; אפשר להשתמש ב-5 מטבעות של 2 ש"ח ובשני מטבעות של 1 ש"ח; אפשר להשתמש במטבע אחד של 10 ש"ח ומטבע אחד של 2 ש"ח, ועוד ועוד. אנחנו רואים שגם עבור סכום כסף קטן יחסית יש לו המון ייצוגים שונים. השאלה היא – מה הייצוג האופטימלי?

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

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

חשבתם? קרוב לודאי שהחלוקה שחשבתם עליה היא 20 ועוד 10 ועוד 1. זו חלוקה מאוד טבעית, שנובעת משיטת חלוקה שאוהבים לקרוא לה "חמדנית". בשיטה החמדנית, בכל רגע נתון בוחרים בדבר "הכי טוב" שנראה שאפשר לעשות כרגע. ספציפית אצלנו זה אומר שאנחנו בוחרים את המטבע בעל הערך הגבוה ביותר שעדיין לא עובר את הסכום שאנחנו רוצים לייצג כרגע, ואז מנסים לייצג את מה שנשאר. במקרה של 31 התחלנו מ-20 כי המטבע הבא (50) כבר גדול מדי. נותר לנו לייצג את 11, ולכן המטבע הבא היה 10, וזה שאחריו היה 1. בדומה, עבור 76 נקבל בשיטה החמדנית את 50 ואז 20 ואז 5 ואז 1.

האם החלוקות החמדניות הללו אופטימליות? התשובה היא חיובית, וזאת בשל תכונה נחמדה שיש למערכת המטבעות בישראל – החלוקה החמדנית היא תמיד אופטימלית במערכת הזו. זה מעלה מייד שאלה אחרת – האם קיימת מערכת מטבעות שבה החלוקה החמדנית היא לא תמיד אופטימלית?

למרבה המזל, בבריטניה הייתה נהוגה בעבר שיטת מטבעות הזויה לחלוטין, שבה התכונה הנחמדה הזו לא התקיימה. במערכת המטבעות הזו ערכי המטבעות היו 1,3,6,12,24,30,60,240 (יחידת המטבע הבסיסית היא פני). מה האלגוריתם החמדני יתן עבור 48 במערכת המטבעות הזו? קל לראות שאת החלוקה 30+12+6, שכוללת 3 מטבעות. לעומת זאת, החלוקה 24+24 כוללת רק 2 מטבעות ולכן עדיפה. מסקנה: קיימות מערכות של מטבעות שבהן החלוקה החמדנית אינה אופטימלית.

מכאן נובעות שתי שאלות הכרעה אלגוריתמיות:

1. נתונה מערכת מטבעות ונתון סכום כלשהו. האם החלוקה החמדנית של הסכום הזה במערכת המטבעות הנתונה היא אופטימלית?
2. נתונה מערכת מטבעות. האם החלוקה החמדנית במערכת המטבעות הנתונה תמיד נותנת את החלוקה האופטימלית?

הבעיה הראשונה נראית קלה יותר מן השניה – בראשונה אנחנו רק צריכים לבדוק סכום אחד, בעוד שבשאלה השניה אנחנו צריכים איכשהו לומר משהו על כל הסכומים האפשריים. לכן הטוויסט הבא כל כך נחמד: הבעיה הראשונה היא קשה אלגוריתמית, במובן מאוד קונקרטי שניתן להוכיח; ואילו הבעיה השניה היא משמעותית יותר קלה אלגוריתמית. פורמלית, למי שמכיר, הבעיה הראשונה היא NP-שלמה בעוד שהבעיה השניה היא ב-P.

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

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

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

בואו נעבור לניסוחים פורמליים. את מערכת המטבעות נסמן באות $latex C$. מערכת כזו מאופיינת על ידי סדרה של מספרים טבעיים – ערכי המטבעות האפשריים. נסדר אותם מהגדול לקטן, כלומר $latex C=\left(c_{1},c_{2},\dots,c_{n}\right)$ כאשר $latex c_{1}>c_{2}>\dots>c_{n}$. כמו כן נניח ש-$latex c_{n}=1$, כי אחרת מערכת המטבעות שלנו לא שלמה ולא יכולה לייצג חלק מהסכומים (לפחות את 1). אז למשל, במערכת הישראלית יש לנו $latex C=\left(200,100,50,20,10,5,2,1\right)$ (ו-$latex n=8$). למי שלא מכיר – סדרה כזו של איברים נקראת לעתים קרובות וקטור והאיברים האינדיבידואלים בוקטור מכונים כניסות.

עכשיו, ייצוג של סכום כלשהו במערכת $latex C$ הוא בעצם סדרה של $latex n$ מספרים טבעיים, שאומרים "כמה מכל סוג מטבע אנחנו לוקחים". כך למשל $latex V=\left(0,0,1,0,1,0,1,0\right)$ הוא ייצוג של 50+10+2, כלומר של 62. עכשיו נכניס לתמונה הוקוס-פוקוס של סימון מתמטי סטנדרטי: אם $latex \left(a_{1},\dots,a_{n}\right)$ ו-$latex \left(b_{1},\dots,b_{n}\right)$ הם שני וקטורים, אז המכפלה הסקלרית שלהם מתקבלת מכפל של איברים באותו מקום בשני הוקטורים וחיבור של כולם. נכון שבכלל לא הבנתם מה אמרתי כרגע? זה כי ניסוחים טקסטואליים הם מסורבלים ונוסחאות קלות יותר להבנה:

$latex \left(a_{1},\dots,a_{n}\right)\cdot\left(b_{1},\dots,b_{n}\right)=\sum_{i=1}^{n}a_{i}b_{i}=a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n}b_{n}$

סימן ה-$latex \sum$ הוא סימון מקוצר לסכימה שמקובל במתמטיקה; עבור מי שלא מכיר אותו כתבתי את הסכום יותר במפורש מימינו.

כעת, חמושים בסימן המכפלה הסקלרית, קל לנו להמשיך: אם $latex C$ היא מערכת המטבעות שלנו ו-$latex V$ הוא וקטור של טבעיים, אז המספר ש-$latex V$ מייצג במערכת $latex C$ הוא פשוט $latex C\cdot V$. כמו כן, אם נסתכל על $latex V\cdot\left(1,1,\dots,1\right)$ נקבל את מספר המטבעות שבהן $latex V$ משתמש (זה בעצם סכום כל הכניסות של $latex V$). נשתמש בסימון המקוצר $latex \left|V\right|=V\cdot\left(1,1,\dots,1\right)$ ונאמר ש-$latex \left|V\right|$ הוא המשקל של $latex V$.

כעת אנחנו רוצים לתאר את הוקטור שהוא הייצוג הטוב ביותר של מספר $latex x$ כלשהו במערכת המטבעות $latex C$. ברור שזה צריך להיות וקטור $latex V$ שמקיים $latex C\cdot V=x$, אבל אי אפשר סתם לומר "בואו ניקח מבין כל ה-$latex V$ האפשריים את זה בעל המשקל המינימלי", כי אולי יש כמה וקטורים שונים בעלי משקל מינימלי שכזה. למשל, במערכת המוזרה של הבריטים אפשר לייצג את 36 בתור 30+6 או בתור 24+12 – שני ייצוגים מגודל 2, ואין ייצוג מגודל 1 כי אין מטבע של 36. אז צריך לבחור בצורה כלשהי מי מבין שני הייצוגים הללו הוא "טוב יותר", והבחירה שלנו היא להעיף כמה שיותר מטבעות גדולים. כמקודם, גם כאן הפורמליזם יאפשר לי להסביר את הכוונה שלי יותר טוב מאשר מילים.

למי שמכיר, מה שאנחנו עושים הוא קובעים סדר לקסיקוגרפי על הוקטורים $latex V$ האפשריים באופן הטבעי. למי שלא מכיר, הנה מה שזה אומר. ראשית, בואו ניזכר איך מילים מסודרות במילון (בהנחה שמישהו עדיין זוכר איך מילים מסודרות במילון…): ראשית כל מופיעות כל המילים שמתחילות באות א', אחריהן אלו שמתחילות באות ב' וכדומה. כלומר, משווים מילים על פי האות הראשונה שלהן. אם היא שונה, אז באה קודם מי שהאות הראשונה שלה באה קודם. ומה עם מילים שבהן האות הראשונה שווה? עוברים לאות השניה, וכדומה.

ניקח את אותו רעיון עבור וקטורים. נסמן $latex U<V$ אם קיים $latex 1\le i\le n$ כך ש-$latex u_{j}=v_{j}$ לכל $latex j<i$ וכמו כן $latex u_{i}<v_{i}$. למשל, $latex \left(1,100,500\right)<\left(2,0,3\right)$. כעת אפשר לומר על וקטור כלשהו $latex V$ שהוא מקסימלי בקבוצת וקטורים אם לכל וקטור $latex U$ שונה ממנו בקבוצה מתקיים $latex U<V$.

עכשיו אפשר לומר בדיוק מה אנחנו רוצים: בהינתן מערכת מטבעות $latex C$ וערך $latex x$ כלשהו, אני מסמן ב-$latex M\left(x\right)$ ($latex M$ מלשון Minimal) וקטור $latex V$ שנבחר כך: ראשית אני מסתכל על כל הוקטורים $latex U$ המקיימים $latex C\cdot U=x$. שנית, מביניהם אני מסתכל על כל אלו שעבורם $latex \left|U\right|$ הוא מינימלי; ולבסוף, מבין מי שנשארו אני לוקח את זה שהוא מקסימלי בסדר הלקסיקוגרפי להיות ה-$latex V$ שלי. אפשר לכתוב את זה פורמלית באופן הבא:

$latex V=\max\left(\arg\min_{\left|U\right|}\left\{ U\ |\ C\cdot U=x\right\} \right)$.

הכתיב הפורמלי כאן הוא לטעמי מסובך מדי ואין ממש הכרח להשתמש בו – ברור מה אני רוצה גם מהניסוח המילולי. עם זאת, יש כאן מוקש נפוץ למדי במתמטיקה שצריך להיזהר איתו. אני מגדיר כאן אובייקט כלשהו, אבל בכלל לא מובטח לי שהוא קיים. הסכנה במקרה הספציפי שלנו היא שאף אחד לא מבטיח לי אוטומטית שקבוצת "כל הוקטורים $latex U$ המקיימים $latex C\cdot U=x$" אינה ריקה. במקרה שלנו, מכיוון שאמרנו שהמטבע 1 תמיד יהיה במערכת המטבעות שלנו, תמיד יש וקטור כזה – $latex U=\left(0,0,\dots,0,x\right)$, ולכן ההגדרה שלי טובה (שימו לב שהוקטור הזה הוא הקטן ביותר בסדר הלקסיקוגרפי, וש-$latex \left|U\right|$ יהיה הגדול ביותר מבין כל המשקלים של וקטורים שמייצגים את $latex w$).

אם כן, $latex M\left(x\right)$ הוא הייצוג האופטימלי של $latex x$. עדיין נותר להגדיר את הייצוג החמדני, אבל זה קל – אנחנו פשוט מוותרים על דרישת המינימום של המשקל. דהיינו, אגדיר $latex G\left(x\right)=\max\left\{ U\ |\ C\cdot U=x\right\} $ (כאן $latex G$ הוא מלשון Greedy – חמדני). למה האיבר המקסימלי לקסיקוגרפית מבין אלו שמייצגים את $latex x$ מתאים לייצוג החמדני? כי מה זה אומר, שהוא ראשון לקסיקוגרפית? ראשית, שהכניסה הראשונה (שמייצגת את המטבע הכי גדול) היא הכי גדולה שרק אפשר כך שעדיין נייצג את $latex x$; ואחר כך הכניסה השניה היא הגדולה ביותר שרק אפשר, בהינתן הערך של הכניסה הראשונה, וכן הלאה. זה זמן טוב לעצור ולוודא שאתם מבינים אותי (ואת כל הסימונים שהיו עד כה). אם איבדתם אותי, נסו לקרוא שוב, או לנסות ולהמציא את ההגדרות מחדש בעצמכם; אין טעם להמשיך לקרוא בלי להרגיש בנוח עם מה שהלך עד כה.

כעת אפשר לנסח מתמטית את מה שאנחנו רוצים. נאמר שמערכת המטבעות $latex C$ היא קנונית אם $latex M\left(x\right)=G\left(x\right)$ לכל $latex x$ טבעי. שתי הבעיות שלנו, אם כן, הן הבעיות הבאות:

1. בהינתן $latex C,x$, האם $latex M_{C}\left(x\right)=G_{C}\left(x\right)$?
2. בהינתן $latex C$, האם $latex M_{C}\left(x\right)=G_{C}\left(x\right)$ לכל $latex x$?

הוספתי את $latex C$ ל-$latex M,G$ למטה כדי לציין שהפונקציות הללו תלויות במערכת המטבעות $latex C$ שלנו. בדרך כלל זה מובן מאליו ולכן אני לא טורח לכתוב את זה במפורש, אבל בניסוח הפורמלי של הבעיות שאנחנו רוצים לפתור זה נראה לי מתאים.

עכשיו בואו נעבור לפתרון הבעיה שאנחנו יודעים לפתור – בעיה 2. הרעיון הוא שבהינתן מערכת המטבעות $latex C$, אם היא לא קנונית אז יש דוגמאות נגדיות לקנוניות שלה – כל מני $latex x$-ים שמקיימים $latex M\left(x\right)\ne G\left(x\right)$. מביניהם, נסמן ב-$latex w$ את הדוגמה הנגדית הקטנה ביותר. הפתרון שלנו יתבסס על כך ש-$latex w$ יכול להיות רק אחד מבין לכל היותר מספר לא גדול של ערכים שונים שאפשר לחשב מתוך $latex C$ – מספר שלא אתן במדויק אבל הוא לא גדול מ-$latex n^{2}$ (כאשר $latex n$, כזכור, הוא מספר המטבעות ב-$latex C$ – ה"אורך" של הוקטור $latex C$). יותר מכך – עבור כל ה-$latex w$-ים הפוטנציאליים הללו, אנחנו יודעים בדיוק מהו $latex ,M\left(w\right)$ ולכן כל מה שנותר לנו לעשות הוא לחשב עבורם את $latex G\left(w\right)$ (זה מהיר) ולבדוק אם $latex G\left(w\right)\ne M\left(w\right)$. אם כן – סיימנו; הוכחנו ש-$latex C$ אינה קנונית. אם לכל $latex n^{2}$ המועמדים שבדקנו התקיים $latex G\left(w\right)=M\left(w\right)$ אנחנו יכולים לעצור ובלב שקט לומר ש-$latex C$ קנונית.

אבל איך נראים המועמדים? ובכן, אני אתן עכשיו את הניסוח המדויק של המשפט שנותן לנו אותם. בהתחלה ממש לא יהיה ברור למה שהמשפט הזה יהיה נכון – מן הסתם מה שאעשה בהמשך יהיה להוכיח אותו. המשפט הוא כזה: נניח ש-$latex w$ היא הדוגמה הנגדית המינימלית. נסמן ב-$latex i$ את האינדקס של הכניסה הראשונה ב-$latex M\left(w\right)$ שאינה אפס וב-$latex j$ את האינדקס של הכניסה האחרונה ב-$latex M\left(w\right)$ שאינה אפס (למשל, אם $latex M\left(w\right)=\left(0,0,1,2,1,0\right)$ אז $latex i=3$ ו-$latex j=5$). כעת הטענה היא ש-$latex M\left(w\right)$ הוא בדיוק מהצורה הבאה: בכניסות $latex 1,2,\dots,j-1$ הוא זהה לגמרי ל-$latex G\left(c_{i-1}-1\right)$; בכניסה ה-$latex j$-ית הוא גדול מהכניסה ה-$latex j$-ית של $latex G\left(c_{i-1}-1\right)$ ב-1; ובשאר הכניסות הוא 0.

שימו לב שכשאנחנו באים להשתמש במשפט הזה, אנחנו לא יודעים מהו $latex w$ ולא מהו $latex M\left(w\right)$ ולכן לא יודעים מהם $latex i,j$; אבל אנחנו יכולים לעבור סדרתית על כולם. לכל $latex i,j$ נתונים אנחנו יכולים לשחק במשחק ה"נניח ש-$latex i,j$ הללו הם הערכים הנכונים, נחשב את $latex M\left(w\right)$ ונראה אם הוא שווה ל-$latex G\left(w\right)$".

זה מבלבל, אז בואו נראה דוגמה. יש לנו את המערכת הבריטית, עם המטבעות $latex 1,3,6,12,24,30,60,240$, כלומר $latex C=\left(240,60,30,24,12,6,3,1\right)$. אנחנו יודעים ש-$latex w=48$ הוא דוגמה נגדית, ואגלה לכם שזו אכן הדוגמה הנגדית המינימלית. עכשיו, $latex M\left(w\right)=\left(0,0,0,2,0,0,0,0\right)$ ולכן $latex i=j=4$. כעת, מהו $latex c_{i-1}-1$? המטבע $latex c_{i-1}=c_{3}$ הוא המטבע 30 (זכרו שאנחנו הולכים מהגדול לקטן), ולכן $latex c_{i-1}-1=29$. מהו $latex G\left(29\right)$? הפעלה של האלגוריתם החמדני נותנת לנו $latex G\left(29\right)=\left(0,0,0,1,0,0,1,2\right)$. כעת, הכניסות $latex 1,\dots,j-1$ של $latex G\left(29\right)$ הן $latex \left(0,0,0\right)$ והכניסה ה-$latex j$ כשמוסיפים לה 1 היא 2, ואם משם והלאה יש לנו אפסים קיבלנו על פי המשפט ש-$latex M\left(w\right)=\left(0,0,0,2,0,0,0,0\right)$, וזה אכן המצב בפועל. קסם!

למה הקסם נכון? או, בואו נתחיל לעשות מתמטיקה.

נתחיל עם עוד הגדרה מתבקשת: נאמר שוקטור $latex U$ הוא חמדני אם $latex U=G\left(C\cdot U\right)$ (ובמילים – אם הפעלת האלגוריתם החמדני על המספר ש-$latex U$ מייצג מחזירה את $latex U$) ונאמר ש-$latex U$ מינימלי אם $latex U=M\left(C\cdot U\right)$ (במילים – אם הייצוג הטוב ביותר למספר ש-$latex U$ מייצג זה הוא עצמו). הטענה שלי היא שוקטורים חמדניים ומינימליים נשארים כאלו גם אם מחסרים להם משהו מהכניסות. בואו נכתוב את זה קצת יותר פורמלית: נשתמש בסימון $latex U\subseteq V$ במקרה שבו קיים וקטור $latex D$ כך ש-$latex U+D=V$ (במתמטיקה יש ל-$latex \subseteq$ לרוב שימוש שונה אבל לא נזדקק לשימוש השונה הזה כאן). למשל, אם $latex U=\left(1,2,3\right)$ ו-$latex D=\left(4,0,3\right)$ אז נקבל $latex U+D=\left(5,2,6\right)$.

שימו לב שהגדרנו על וקטורים פעולות "חיבור" ו"כפל" וגם יחס סדר $latex \le$ שהן שונות למדי מהפעולות והיחסים שאנחנו מכירים על מספרים; היופי בעניין הוא שהתכונות שאנחנו רגילים להן ממספרים משתמרות ברובן גם עבור הפעולות החדשות. למשל, $latex \left(A+B\right)\cdot C=A\cdot C+B\cdot C$. ולמשל $latex A\le B$ אם ורק אם $latex A+D\le B+D$ (בדקו זאת!). זה מאפשר לנו לתת הוכחה אלגנטית לטענה שלנו. בואו נניח אם כן ש-$latex U\le V$ וש-$latex V$ חמדני, ונוכיח ש-$latex G$ חמדני. לשם כך ניקח $latex U^{\prime}$ כלשהו שמייצג את אותו מספר כמו $latex U$, דהיינו $latex C\cdot U=C\cdot U^{\prime}$, ונראה ש-$latex U^{\prime}\le U$ (כלומר, $latex U$ הוא הגדול ביותר מבין כל הייצוגים למספר שהוא מייצג, ולכן מה שהאלגוריתם החמדני יחזיר).

כל מה שנצטרך הוא מניפולציות אלגבריות. אם $latex U^{\prime}\cdot C=U\cdot C$ אז נקבל ש:

$latex \left(V-U+U^{\prime}\right)\cdot C=V\cdot C-U\cdot C+U^{\prime}\cdot C=V\cdot C$

מה שאומר שהוקטור $latex V$ מייצג את אותו המספר כמו $latex V-U+U^{\prime}$. מכיוון ש-$latex V$ חמדני הוא גדול מכל וקטור אחר שמייצג את אותו מספר, ומכיוון ש-$latex V-U+U^{\prime}$ הוא וקטור שכל הכניסות בו חיוביות הוא אכן מייצג מספר. והן כולן חיוביות כי $latex U\subseteq V$ – זה המקום שבו אנחנו משתמשים בנתון הזה. ולכן:

$latex V-U+U^{\prime}\le V$

וכעת ניתן לבצע "העברת אגפים" ממש כמו באי-שוויונות במספרים רגילים, ולקבל $latex U^{\prime}\le U$, כמבוקש.

הוכחה דומה עובדת גם עבור הטענה שאם $latex V$ מינימלי ו-$latex U\subseteq V$ אז $latex U$ מינימלי. רק צריך לשנות קצת את המשמעות של $latex \le$ כך שאם $latex \left|A\right|\ge\left|B\right|$ אז $latex A\le B$ (קצת מבלבל, אבל זכרו את הרעיון – וקטור מינימלי הוא וקטור בעל משקל מינימלי שהוא הגדול ביותר לקסיקוגרפית; כלומר, הסינון הראשוני הוא על פי המשקל, ומשקל קטן יותר הוא טוב יותר). צריך להוכיח שהמשמעות החדשה עדיין מקיימת את התכונות האלגבריות הנחמדות, אבל אין כאן משהו קשה.

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

עוד תכונה שאשתמש בה בהמשך היא שהפונקציה $latex G$ שלוקחת מספר ומתאימה לו את הפתרון החמדני שלו היא משמרת סדר במובן הבא: אם $latex x<y$ אז $latex G\left(x\right)<G\left(y\right)$. כדי לראות את זה, שימו לב לכך ש-$latex U=G\left(x\right)+\left(0,0,\dots,y-x\right)$ הוא ייצוג כלשהו עבור $latex y$ ולכן $latex U\le G\left(y\right)$. כמו כן בבירור $latex G\left(x\right)<U$, כי לקחנו את $latex G\left(x\right)$ והוספנו לו עוד משהו. משני אלו קיבלנו ש-$latex G\left(x\right)<G\left(y\right)$ – המעבר האחרון הוא שימוש בתכונת הטרנזיטיביות של יחס הסדר $latex \le$ ואם זה נראה לכם חשוד, נסו להוכיח שזה עובד.

עכשיו בואו נתחיל את ההוכחה המרכזית שלנו. נניח ש-$latex C$ היא מערכת מטבעות לא קנונית, ויהא $latex w$ הדוגמה הנגדית הקטנה ביותר לכך. כלומר, $latex G\left(w\right)\ne M\left(w\right)$ אבל לכל $latex x<w$ מתקיים $latex G\left(x\right)=M\left(x\right)$ (הגישה הזו של "בואו ניקח את המינימלי" היא מאוד נפוצה במתמטיקה – היא אוטומטית נותנת לנו כלי נשק חדש ומועיל במהלך ההוכחה שסתם לקחת דוגמה נגדית כלשהי לא היה נותן לנו). בואו נתחיל להבין את התכונות של $latex w$ הזה. ראשית כל, אני טוען שאין ל-$latex G\left(w\right),M\left(w\right)$ כניסות משותפות ששונות מאפס. בואו נזכר ב-$latex w=48$ של הבריטים: שם $latex M\left(w\right)=\left(0,0,0,2,0,0,0,0\right)$ ואילו $latex G\left(w\right)=\left(0,0,1,0,1,1,0,0\right)$. ב-$latex M\left(w\right)$ הכניסה היחידה שאינה 0 היא הרביעית, ואילו ב-$latex G\left(w\right)$ הכניסות שאינן אפס הן 3,5,6. כלומר, אין כניסה ששונה מאפס אצל שניהם, ואני טוען שזה לא מקרי. למה? ובכן, נניח שהכניסה ה-$latex k$-ית בשניהם לא הייתה 0. אז הייתי יכול לחסר ממנה 1 ולקבל מ-$latex M\left(w\right)$ ומ-$latex G\left(w\right)$ שני וקטורים חדשים שעדיין מייצגים את אותו מספר (המספר $latex w-c_{k}$ אם אנחנו רוצים להיות מדוייקים), ועל פי הטענה שהוכחתי לפני רגע על $latex U\le V$, הוקטור שנקבל מ-$latex M\left(w\right)$ על ידי החיסור יהיה הפתרון המינימלי עבור המספר הזה והוקטור שנקבל מ-$latex G\left(w\right)$ יהיה הפתרון החמדני עבור המספר הזה. עכשיו, בגלל ש-$latex w$ הוא הדוגמה הנגדית המינימלית לסיטואציה שבה הוקטור החמדני והמינימלי שונים, ינבע ששני הוקטורים שקיבלתי הם זהים, אבל אם כך גם הוקטורים המקוריים שהתחלתי מהם היו צריכים להיות זהים כי כל מה ששיניתי היה לחסר משניהם 1 באותו מקום.

עכשיו בואו נסמן $latex M\left(w\right)=\left(m_{1},m_{2},\dots,m_{n}\right)$ וכפי שהבטחתי, נסמן ב-$latex i$ את אינדקס הכניסה הראשונה שאינה 0 וב-$latex j$ את אינדקס הכניסה האחרונה שאינה 0. אבחנה ראשונה היא ש-$latex M\left(w\right)<G\left(w\right)$ על פי הגדרה (כי כל וקטור שמייצג את $latex w$ קטן לקסיקוגרפית מ-$latex G\left(w\right)$, ואנו מניחים ש-$latex M\left(w\right)\ne G\left(w\right)$). מכיוון ש-$latex M\left(w\right),G\left(w\right)$ אינם חולקים כניסות שונות מ-0, הכניסה הראשונה של $latex M\left(w\right)$ שאינה אפס חייבת להיות כזו שהיא כן אפס אצל $latex G\left(w\right)$; וכדי שעדיין יתקיים $latex M\left(w\right)<G\left(w\right)$ נובע שבהכרח יש ל-$latex G\left(w\right)$ כניסה מוקדמת יותר ששונה מאפס (למה?) ולכן $latex 1<i$. זו לא הסקה טריוויאלית – שוב, אני ממליץ לכם לוודא שאתם מבינים מה הלך פה.

המטרה שלי היא להראות ש-$latex M\left(w\right)$ דומה למדי ל-$latex G\left(c_{i-1}\right)$, אז בואו ננסה להבין קצת את $latex c_{i-1}$ הזה.

מכיוון ש-$latex i>1$ אפשר לדבר על $latex c_{i-1}$ (אם $latex i=1$ ואני כותב $latex c_{i-1}$ אז כתבתי משהו חסר משמעות כי ה-$latex c$-ים מתחילים מ-1). עכשיו, $latex G\left(w\right)$ כולל 1 בכניסה מוקדמת יותר מ-$latex i$, כלומר $latex w$ מורכב לפחות ממטבע אחד שגדול או שווה ל-$latex c_{i-1}$ ומכאן ש-$latex w\ge c_{i-1}$. מצאנו חסם מלעיל (מלמעלה) על $latex c_{i-1}$. עכשיו בואו נמצא חסם מלרע (מלמטה) עליו: אנחנו יודעים שאם ניקח את $latex M\left(w\right)$ אז הכניסה ה-$latex j$ תהיה גדולה מאפס. לכן ניתן לחסר ממנה 1, והוקטור שיתקבל יהיה ייצוג של $latex w-c_{j}$ (למה?). הוקטור הזה הוא ייצוג מינימלי של $latex w-c_{j}$ ומכיוון ש-$latex w-c_{j}$ קטן מ-$latex w$ ו-$latex w$ הוא הערך המינימלי שהייצוג המינימלי שלו אינו חמדני, קיבלנו שהוקטור שלנו (שהוא $latex M\left(w\right)$ שבו הכניסה ה-$latex j$ הוקטנה ב-1) הוא הייצוג החמדני של $latex w-c_{j}$. עכשיו, הייצוג הזה כולל רק את המטבעות שמשתתפים ב-$latex M\left(w\right)$, כלומר המטבע בעל הערך הגדול ביותר שמשתתף בו הוא $latex c_{i}$. מסקנה: $latex w-c_{j}<c_{i-1}$. קחו שניה ותסבירו לעצמכם למה זה נכון, כי עשיתי פה קפיצה קטנה.

ההסבר: אם $latex w-c_{j}\ge c_{i-1}$ אז על פי הגדרתו, האלגוריתם החמדני ייקח לפחות את אחת המטבעות $latex c_{1},\dots,c_{i-1}$. אנחנו יודעים שהוא לא עשה את זה (אמרתי את זה לפני רגע), ולכן.

אם כן, קיבלנו חסם מלרע עבור $latex c_{i-1}$. אם נרכז את מה שכבר מצאנו:

$latex w-c_{j}<c_{i-1}\le w$

זה מראה לנו ש-$latex c_{i-1}$ קרוב מאוד ל-$latex w$. כמה קרוב? הוא נמצא בטווח קטן יחסית שגודלו $latex c_{j}$ וקצהו האחד ב-$latex w$ עצמו. בואו נשתמש בזה עכשיו.

נסמן $latex V=\left(v_{1},v_{2},\dots,v_{n}\right)=G\left(c_{i-1}-1\right)$. מה שבעצם נותר לנו להוכיח הוא ש-$latex v_{k}=m_{k}$ לכל $latex 1\le k<j$ וש-$latex v_{j}=m_{j}-1$. הדרך שבה נעשה את זה תהיה לחסום את $latex V$ בין שני וקטורים: נראה שהוא קטן מ-$latex M\left(w\right)$ אבל שהוא גדול מוקטור אחר שנראה כמעט כמו $latex M\left(w\right)$, מה שלא יאפשר ל-$latex V$ להיות שונה במיוחד מ-$latex M\left(w\right)$ בכל הכניסות עד ה-$latex j$-ית.

נתחיל בלהראות ש-$latex V<M\left(w\right)$. מן הסתם $latex c_{i-1}-1$ קטן מ-$latex c_{i-1}$ ולכן המטבע $latex c_{i-1}$ והגדולות ממנה לא יכולות להיות חלק מהפתרון החמדני עבור $latex c_{i-1}$. אבל המטבע $latex c_{i}$ בוודאי יהיה, כי הוא המטבע הגדול ביותר שעדיין קטן או שווה ל-$latex c_{i-1}-1$. מכאן ש-$latex v_{i}\ne0$. לכן אפשר להשתמש בתעלול שכבר הפך לשגור אצלנו – להפחית 1 מהכניסה ה-$latex i$ הן ב-$latex V$ והן ב-$latex M\left(w\right)$ ולקבל את $latex G\left(c_{i-1}-1-c_{i}\right)$ ואת $latex M\left(w-c_{i}\right)=G\left(w-c_{i}\right)$, בהתאמה. כעת, אי השוויון שיש לנו על $latex c_{i-1}$ מראה ש-$latex c_{i-1}-1-c_{i}<w-c_{i}$, ולכן $latex G\left(c_{i-1}-1-c_{i}\right)<G\left(w-c_{i}\right)$, כשהמעבר האחרון נובע מתכונת "שימור הסדר" של פתרונות חמדניים שראינו קודם.

קיבלנו שוקטור א' יותר קטן מוקטור ב'. אם נחבר לשניהם 1 בכניסה ה-$latex i$-ית זה לא ישנה את הסדר היחסי בין הוקטורים שנקבל, שהם בדיוק $latex V,M\left(w\right)$ בהתאמה, ולכן קיבלנו ש-$latex V<M\left(w\right)$.

עכשיו בואו נחסום את $latex V$ מלרע. לשם כך, בואו ניקח את $latex M\left(w\right)$ ונקטין את $latex m_{j}$ (הכניסה האחרונה שאינה 0) ב-1. נקבל את הוקטור $latex G\left(w-c_{j}\right)$, ומכיוון שכבר ראינו ש-$latex w-c_{j}<c_{i-1}$, כלומר ש-$latex w-c_{j}\le c_{i-1}-1$, נקבל ש-$latex G\left(w-c_{j}\right)\le G\left(c_{i-1}-1\right)=V$.

מכאן שהצלחנו לחסום את $latex V$ כך: $latex G\left(w-c_{j}\right)\le V<M\left(w\right)$. זה מעניין, כי $latex G\left(w-c_{j}\right)$ ו-$latex M\left(w\right)$ הם כמעט אותו וקטור – הם נבדלים רק בכניסה $latex m_{j}$ שב-$latex M\left(w\right)$ גדולה ב-1. מכאן שעד לכניסה הזו גם $latex V$ חייב להיות שווה אליהם (אחרת הוא היה גדול משניהם או קטן משניהם). כעת, מה קורה בכניסה $latex m_{j}$? אנחנו יודעים שקורה אחד משניים: $latex v_{j}=m_{j}$ או $latex v_{j}=m_{j}-1$ (אחרת, שוב, $latex V$ היה גדול או קטן משני הוקטורים). האם יכול להיות ש-$latex v_{j}=m_{j}$? ובכן, לא: זאת מכיוון שכל הכניסות של $latex M\left(w\right)$ שאחרי ה-$latex j$-ית הן אפסים. לכן, אם $latex v_{j}=m_{j}$ זה אומר ש-$latex V$ זהה ל-$latex M\left(w\right)$ ב-$latex j$ הכניסות הראשונות וביתר הכניסות הוא שווה או גדול ממנו, ומכאן נובע ש-$latex M\left(w\right)\le V$ בסתירה לכך שכבר ראינו ש-$latex V<M\left(w\right)$. מכאן ש-$latex v_{j}=m_{j}-1$. ומה על יתר הכניסות של $latex V$? ובכן, הן פשוט לא מעניינות אותנו; השגנו בדיוק את מה שרצינו להשיג. זה מסיים את המשפט ומסיים את כל הטיפול בבעיית "נתונה מערכת מטבעות – האם היא קנונית?"

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

נעבור עכשיו לדבר על הבעיה השניה – בהינתן $latex C,x$ לקבוע האם $latex G_{C}\left(x\right)=M_{C}\left(x\right)$. מכיוון שלחשב את $latex G_{C}\left(x\right)$ זה קל, ברור שה"קושי" של הבעיה מסתמך על כך שבאופן כללי חישוב של $latex M_{C}\left(x\right)$ הוא קשה. מה זה אומר, "קשה"? איך מודדים את זה? נתחיל מהשקר שקל יחסית לעכל ונעבור לאמת המסובכת והעגומה יותר. השקר הוא זה: אין לנו דרך "חכמה" לחשב את $latex M_{C}\left(x\right)$ ולכן אנחנו פשוט עוברים על כל האפשרויות לייצג את $latex x$ בעזרת $latex C$ ובודקים מי מהן הכי חסכונית במטבעות. הבעיה היא שיש מספר גדול של אפשרויות: נניח שיש לנו $latex n$ סוגי מטבעות ואנחנו תוהים אם אפשר לייצג משהו שגודלו גדול מסכום כל המטבעות. אז יש לנו $latex 2^{n}$ אפשרויות לחלוקה שכוללת כל מטבע רק פעם אחת או אפס פעמים, ובפועל יש הרבה יותר חלוקות מזה – מספר החלוקות הוא אקספוננציאלי. לעבור על כולן לוקח המון זמן. זה לא יעיל באופן שבו מודדים "יעילות" במדעי המחשב.

זה סוף השקר, וזה שקר יחסית משביע רצון שמעביר את האינטואיציה. אבל מהי האמת?

האמת היא שאנחנו לא יודעים אם זו בעיה קשה או לא. זה נכון שלחשב את $latex M\left(x\right)$ על ידי האלגוריתם "עבור על כל האפשרויות ובדוק" זה לא יעיל, אבל מי אומר לנו שאין אלגוריתם יותר מתוחכם? אנחנו לא מכירים כזה בהכרח, אבל מי אומר שאין? למעשה, בפועל יש אלגוריתמים יותר מתוחכמים, שאני לא מכניס לפוסט הזה כי גם ככה הוא עמוס, אבל גם הם סובלים מאי-יעילות (דהיינו, הם טובים הרבה יותר מהאלגוריתם הנאיבי שהצגתי, אבל זמן הריצה שלהם עדיין איטי למדי). כדי להגיד שהבעיה קשה, אני צריך להוכיח איכשהו טענה כללית: שכל האלגוריתמים שפותרים את הבעיה הם לא יעילים. איך אפשר להקיף את כל האלגוריתמים? זה בוודאי לא משהו טריוויאלי. ולמען האמת, זה אפילו לא נגמר כאן. הבעיה שאני הצגתי היא הבעיה הבאה: בהינתן $latex C,x$ האם $latex G_{C}\left(x\right)=M_{C}\left(x\right)$? זו בעיה שהתשובה לה היא "כן/לא". ייתכן, תיאורטית, שאפשר לענות עליה בלי שנצטרך בכלל לחשב את $latex M_{C}\left(x\right)$, כלומר זו עשויה להיות בעיה קלה יותר מאשר חישוב של $latex M_{C}\left(x\right)$, ולכן כל הטיעון האינטואיטיבי שנתתי למעלה היה רמאות מובהקת – הוא הסביר למה בעיה אחרת היא קשה. אמנם, אין לי מושג איך לפתור את הבעיה שלי מבלי לפתור את הבעיה האחרת, אבל זה שאני לא חושב על משהו לא אומר שאין.

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

הערה קטנה למתקדמים, שמי שלא בקיא בתחום יכול לוותר עליה: שימו לב שבניסוח שנתתי, הבעיה אינה ב-NP אלא ב-coNP, מכיוון שלא קיים "עד" ברור לכך ש-$latex G_{C}\left(x\right)=M_{C}\left(x\right)$ אבל כן קיים "עד" ברור לכך שהם שונים (בהינתן הפתרון האופטימלי קל לבדוק שהוא שונה מהחמדני). כשאני אומר "הבעיה" אני מתכוון בעצם למשלימה של הבעיה שלנו, וכך גם אפעל בהמשך; הדקות הזו לא קריטית למי שלא מצוי בנבכי ההגדרות הפורמליות.

איך מראים שבעיה היא NP-שלמה? הדרך המקובלת היא באמצעות מעין רקורסיה: לוקחים בעיה שכבר יודעים שהיא NP-שלמה, ומוכיחים שאם אנחנו יודעים לפתור ביעילות את הבעיה החדשה, אז אנחנו יודעים לפתור ביעילות את הבעיה ה-NP-שלמה הישנה (לדבר כזה קוראים רדוקציה). כמובן, רקורסיה צריכה להתחיל מהיכן שהוא, ונקודת ההתחלה הסטנדרטית – השפה ה-NP-שלמה ה"ראשונה", היא בדרך כלל שפה שנקראת SAT שלא אתאר במפורש כאן.

אז כדי להוכיח שבעיית המטבעות היא NP-שלמה אני צריך לקחת בעיה NP-שלמה קיימת ולעשות רדוקציה שלה אל בעיית המטבעות. מה שאומר שאני קצת מרמה: אני יכול לבחור איזו בעיה NP-שלמה שנוח לי לעבוד איתה בתור "נקודת התחלה", ומן הסתם בפוסט הזה לא אוכיח שגם היא NP-שלמה. בפועל יש כמה בעיות "סטנדרטיות" שכולם מכירים ונהוג להשתמש בהן או בוריאציות עליהן, ואני הולך להשתמש בוריאציה על בעיה שנקראת Subset Sum. הבעיה המקורית היא כזו: נתונה קבוצה $latex S=\left\{ x_{1},x_{2},\dots,x_{n}\right\} $ של מספרים ועוד מספר אחד $latex c$. השאלה היא אם קיימת תת-קבוצה של $latex S$, שאסמן $latex S^{\prime}$, שסכום האיברים בה שווה בדיוק ל-$latex c$, כלומר $latex \sum_{x\in S^{\prime}}x=c$.

את הבעיה הזו אפשר לנסח בצורה שונה אבל שקולה לגמרי: נתון הוקטור $latex X=\left(x_{1},\dots,x_{n}\right)$ של מספרים (אפשר לדרוש במפורש שמספר לא מופיע פעמיים בוקטור אבל זה לא חשוב). האם קיים וקטור בינארי $latex A=\left(a_{1},\dots,a_{n}\right)$ כך ש-$latex X\cdot A=c$? כאן "וקטור בינארי" אומר שכל כניסה בוקטור היא 0 או 1.

הוריאציה שאני אשתמש בה מרשה ל-$latex A$ להכיל מספרים טבעיים כלשהם, לא רק 0 ו-1 (אבל לא מספרים שליליים). לא אוכיח כאן שהיא NP-שלמה אבל זה תרגיל טוב. בניסוח הזה, הבעיה נראית כמעט לגמרי כמו בעיית המטבעות, בהבדל אחד – אנחנו לא מדברים על אופטימיזציה אלא על היתכנות. חשבו על $latex X$ בתור מערכת המטבעות שלנו, אבל ללא דרישה ש-1 יהיה שייך אליה, ואז השאלה היא אם אפשר בכלל לייצג ערך $latex c$ נתון במערכת הזו.

אם כן, אני מקבל $latex X=\left(x_{1},\dots,x_{n}\right)$ ו-$latex c$ ורוצה לייצר שני דברים: מערכת מטבעות $latex C$, וערך $latex y$ כלשהו, כך שמתקיים ש-$latex G_{C}\left(y\right)\ne M_{C}\left(y\right)$ אם ורק אם קיים $latex A$ כך ש-$latex X\cdot A=c$. זו המהות של רדוקציה – המרה של מקרה לבדיקה של בעיה אחת למקרה לבדיקה של בעיה אחרת.

לכאורה יש לי מגבלה די מהותית – ה"נשק" היחיד שיש לי הוא הפער שיכול להיות קיים בין הפתרון החמדני והאופטימלי. איכשהו אני צריך לנצל אותו כדי לדעת אם בכלל אפשר לייצג ערך כלשהו בעזרת $latex X$. אבל אם חושבים קצת על האופן שבו אפשר ליצור מערכות של מטבעות שבהן הפתרון החמדני והאופטימלי לאו דווקא מזדהים, זה לא קשה. מה קרה במערכת הבריטית? היה לנו ערך – 48 – שמיוצג בקלות על ידי מספר קטן כלשהו – 24. אלא שיש מעל 24 מספר גדול יותר, 30, ש"מכריח" את הפתרון החמדני לפספס את 24 ולעבור להתעסק עם מספרים קטנים יותר. על זה אני אבנה את הפתרון שלי, וכדי שיהיה קל להבין אותו אני אסביר מה אני עושה במקרה פרטי.

המקרה הפרטי יהיה $latex X=\left(10,20,30,40\right)$ ונראה מה אני עושה עבור $latex c$-ים שונים. יש ב-$latex X$ ארבעה איברים, ולכן אני רוצה לבנות מערכת מטבעות $latex C$ וערך $latex y$ כך שאם $latex c$ ניתן לייצוג בידי $latex X$, אפשר יהיה לייצג את $latex y$ ב-$latex C$ באותה הצורה, עם לכל היותר ארבעה איברים; אבל אם אי אפשר, אז כדי לייצג את $latex y$ אני אצטרך לפחות חמישה איברים. למעשה, די קל לעשות את זה – נגדיר את $latex C$ להיות $latex X$ ועוד שני איברים: $latex 1$ (שחייב תמיד להיות ב-$latex C$) ו-$latex c-4$.

בואו נראה איך זה עובד. קודם כל, ניקח $latex c=60$ שאנחנו יודעים שאפשר לייצג ב-$latex X$. אז $latex C=\left(56,40,30,20,10,1\right)$ ו-$latex y=60$. הפתרון המינימלי במקרה זה הוא $latex 60=40+20$. הפתרון החמדני, לעומת זאת, קודם כל ייקח את $latex 56$, יישאר עם 4, ואז יקח את 1 עוד 4 פעמים – כלומר, גודלו 5.

לעומת זאת, אם ניקח $latex c=64$, שלא ניתן לייצוג על ידי $latex X$, אז נקבל $latex C=\left(60,40,30,20,10,1\right)$ ו-$latex y=64$. במקרה זה, בבירור הפתרון האופטימלי הוא $latex 64=60+1+1+1+1$ וזהו גם הפתרון החמדני.

ומה קורה אם $latex c$ קטן יותר מחלק מהאיברים ב-$latex X$, למשל $latex c=24$? ובכן, בדוגמה הזו אין שום שינוי מהותי – הפתרון החמדני עדיין ייקח את $latex c-4$ בתור האיבר הראשון. מתי כן עשויה להתעורר בעיה? כאשר $latex c-4$ אינו האיבר הגדול ביותר שעדיין קטן מ-$latex y$. למשל, אם ניקח $latex y=32$ אז נקבל $latex C=\left(40,30,28,20,10,1\right)$, ואז הפתרון החמדני יהיה $latex 30+1+1$, שהוא גם הפתרון האופטימלי. עוד בעיה שיכולה להתעורר היא במקרה שבו $latex c$ ממש קטן – למשל, 2.

במקרה הזה אני אבחר את $latex y$ להיות גדול מאוד, עם שתי דרכים שונות להקטין אותו – אחת שתכריח אותנו להשתמש ב-1 מכאן ואילך, ואחת שתאפשר לנו להשתמש ב-$latex X$. פורמלית, $latex y=c+T$ כאשר $latex T$ הוא מספר שגדול מהסכום של כל אברי $latex X$, ונוסיף למערכת שלנו את $latex y-5$ ואת $latex T$ עצמו. במקרה שלנו $latex 40+30+20+10=100$ אז בואו נבחר $latex T=200$ כי אפשר, ואז עבור $latex c=32$ נקבל $latex y=232$ ואת המערכת $latex \left(227,200,40,30,20,10,1\right)$. הפתרון החמדני הוא $latex 227+1+1+1+1$ וקל לראות שהוא אופטימלי.

עוד מקרה קצה אחד שבו צריך לטפל הוא זה שבו $latex c-4$ גדול מאחד מאברי $latex X$. פתרון פשוט? לכפול את כל אברי $latex X$ ב-10 ואת $latex c$ ב-10 ולהמשיך משם. אני אשאיר לכם לטפל בפרטים.

זו הייתה רדוקציה במקרה של $latex X$ ספציפית, אבל תחליפו את $latex 4$ ב-$latex n$ ותקבלו את הרדוקציה עבור $latex X$ כללי – שוב, אני ממליץ לאלו מכם שמעוניינים לשבת ולכתוב אותה פורמלית ולהוכיח שהיא עובדת.

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

---

סכום ריבועי הספרות, מספרים "שמחים" ו"עצובים"

אליהו לוי

נסמן ב-$latex {\mathbb{N}}$ את קבוצת המספרים הטבעיים $latex {1,2,3,\ldots}$.

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

$latex 1\rightarrow 1$

$latex 2\rightarrow 4$

$latex 100\rightarrow 1^2+0^2+0^2=1$

$latex 87\rightarrow 8^2+7^2=64+49=113$

$latex 2506\rightarrow 2^2+5^2+0^2+6^2=4+25+0+36=65 $

זוהי העתקה מהקבוצה האינסופית $latex {\mathbb{N}}$ לעצמה. אמנם די מלאכותית, אבל נושא "לגיטימי" לתרגיל…

אותנו מעניין מה קורה כשחוזרים על פעולה זו.

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

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

$latex 1 \rightarrow 1$

$latex 2 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4$

$latex 3 \rightarrow 9 \rightarrow 81 \rightarrow 65 \rightarrow 61 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37$

$latex 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4$

$latex 5 \rightarrow 25 \rightarrow 29 \rightarrow 85 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89$

$latex 6 \rightarrow 36 \rightarrow 45 \rightarrow 41 \rightarrow 17 \rightarrow 50 \rightarrow 25 \rightarrow 29 \rightarrow 85 \rightarrow$
$latex  89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89$

$latex 7 \rightarrow 49 \rightarrow 97 \rightarrow 130 \rightarrow 10 \rightarrow 1 \rightarrow 1$

$latex 8 \rightarrow 64 \rightarrow 52 \rightarrow 29 \rightarrow 85 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89$

$latex 9 \rightarrow 81 \rightarrow 65 \rightarrow 61 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37$

$latex 10 \rightarrow 1 \rightarrow 1 $

לפחות המספרים שאנו רואים כאן מתחלקים לשתי קבוצות: מספרים, שבעיקבות הספר $latex {R.~Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer-Verlag, 2004}$ (וראו גם בספר "מתמטיקסם" מאת יעל רוטנברג, הוצאת דני ספרים, $latex {2013}$), נקרא להם "מספרים שמחים", שמגיעים בסוף ל $latex {1}$ שמועתק לעצמו, ומספרים "עצובים" שנכנסים לבסוף למחזור

$latex 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 (*)$

מהטבלה אנו רואים שהמספרים $latex {1,7,10}$ הם שמחים, וכן גם $latex {49,97,130}$ בעוד שהמספרים $latex {2,3,4,5,6,8,9}$ הם עצובים, וכן כמובן אברי המחזור $latex {(*)}$ וגם $latex {81,65,61,25,29,85,36,45,41,17,50,64,52}$.

משפט.

כל מספר טבעי הוא או "שמח", כלומר חזרה על פעולת סכום ריבועי הסםרות תביא לבסוף ל $latex {1}$, או "עצוב", כלומר חזרה על פעולת סכום ריבועי הספרות תכניס אותנו לבסוף למחזור המסויים $latex {(*)}$.

הוכחה.

ההוכחה תיעשה בעזרת שורת משפטי עזר.

משפט עזר 1.

אם $latex {n\le162}$ אז גם סכום ריבועי הספרות של $latex {n}$ קטן או שווה ל $latex {162}$.

הוכחה.

אם $latex {n<100}$, סכום ריבועי הספרות לכל היותר $latex {9^2+9^2=162}$. אם $latex {100\le n\le 162}$ אזי סיפרת המאות של $latex {n}$ היא $latex {1}$, וסיפרת העשרות לכל היותר $latex {6}$ ולכן סכום ריבועי הספרות לכל היותר $latex {1^2+6^2+9^2=118}$.

משפט עזר 2.

כל מספר $latex {n\le162}$ הוא או "שמח" או "עצוב".

הוכחה.

יש להמשיך את הטבלה שלעיל עד $latex {162}$ (עדיף ע"י תיכנות מחשב לעשות את העבודה). מכיוון שאף פעם לא נחרוג מהקבוצה $latex {\{1,2,\ldots,162\}}$, הסידרה שתתקבל מכל מספר שנצא חייבת לחזור אי-פעם למספר שכבר היה בה, ואז היא תיכנס למחזור. בודקים שהמחזור הוא תמיד או $latex {1 \rightarrow 1}$ (ואז המספר "שמח" או $latex {(*)}$ ואז המספר "עצוב".

משפט עזר 3.

אם $latex {n>1000}$ אזי סכום ריבועי הספרות של $latex {n}$ קטן או שווה מ $latex {\textstyle{\frac12} n}$.

הוכחה.

מספר הספרות של $latex {n}$ קטן או שווה מ- $latex {\log_{10}n+1}$. לכן סכום ריבועי הספרות קטן או שווה מ $latex {81(\log_{10}n+1)}$. אנו צריכים להוכיח ש

$latex 81(\log_{10}n+1)\le\frac12 n$
$latex 162(\log_{10}n+1)\le n $

את זה אםשר להוכיח באינדוקציה עבור $latex {n\ge1000}$. עבור $latex {n=1000}$ בודקים שזה נכון. אם זה נכון עבור $latex {n}$, המקיים $latex {n\ge1000}$,

$latex 162(\log_{10}(n+1)+1)=162(\log_{10}n+1)+162\log_{10}\left(\frac{n+1}n\right)\le n+162\log_{10}\left(1+\frac1n\right)$

בשביל שזה יהיה קטן או שווה מ $latex {n+1}$ אנו צריכים ש

$latex \log_{10}\left(1+\frac1n\right)\le\frac1{162}$

וזה נכון כי עבור $latex {x>0}$ מתקיים $latex {\log_{10}(1+x)\le\ln(1+x)\le x}$ ואצלנו $latex {n\ge1000}$.

שימו לב שהיינו צריכים להשתמש באי-שוויון לא טריוויאלי של םונקציית ה $latex {\log}$.

משפט עזר 4.

מכל מספר טבעי $latex {n}$ נגיע, ע"י הפעלה חוזרת של םעולת סכום ריבועי הספרות, למספר קטן או שווה ל $latex {162}$.

הוכחה.

לפי משפט עזר 3. נקטיו את $latex {n}$ לפחות פי שניים בכל צעד עד שנגיע למספר קטו מ $latex {1000}$. עבור מספר זה סכום ריבועי הספרות יהיה לכל היותר $latex {3\times9^2=243}$. כעת יהיה סכום ריבועי הצלעות לכל היותר $latex {2^2+9^2+9^2=166}$, ואם מספר זה גדול מ $latex {162}$ אזי סכום ריבועי הצלעות שלו לא יעלה על $latex {1^2+6^2+9^2=118}$ וגמרנו.

וטענת המשפט נובעת כעת ממשפטי העזר 2 ו 4.

---

מה זו "מתמטיקה"

רון אהרוני

1. קשיי הגדרה

"אוֹמְרִים, אַהֲבָה יֵשׁ בָּעוֹלָם.
מַה זֹּאת אַהֲבָה?"
("הכניסיני תחת כנפך",חיים נחמן ביאליק)
"אינני יודע להגדיר "פורנוגרפיה", אבל אני יודע לזהות פורנוגרפיה כשאני רואה אותה."
(פּוֹטֶר סטיוארט, חבר בית המשפט העליון האמריקאי)
"איננו יודעים למה אנחנו מתכוונים ב"שיר יפה", אבל זה לא מונע מאיתנו להכיר ביופיו של שיר כשאנו קוראים אותו."
(גודפרי הרולד הרדי, מתוך "התנצלותו של מתמטיקאי")

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

2. הפשטה

מה מייחד אפוא את המתמטיקה? ארשה לעצמי לצטט סיפור מספרי חשבון להורים (הוצאת שוקן, תשס"ד). בכיתה א' אני מבקש מן הילדים שיבדקו כמה הם (נאמר) 3 עפרונות ועוד 2 עפרונות. הילדים למדו שחיבור פירושו צירוף. הם מצרפים 3 עפרונות ל-2 עפרונות, ומוצאים שמתקבלים 5 עפרונות. עתה אני שואל: כמה הם 3 מחקים (נאמר) ועוד 2 מחקים? 5 מחקים, הם משיבים מייד. מנין אתם יודעים? כי ראינו זאת עם עפרונות. אז מה? אני טוען. אולי עם מחקים זה אחרת?
הילדים צוחקים. אבל השאלה שלי אינה מצחיקה כלל. בה טמון כל סודה של המתמטיקה: הכלליוּת. המתמטיקה מפשיטה את הסיטואציה מן הפרטים הטפלים, ומותירה את העיקר. במקרה זה, העיקר הוא ששני עצמים ועוד שלושה הם חמישה, ללא קשר לטיבם או לסידורם בחלל. כל תחום חשיבה עושה הפשטות מסוג זה. המייחד את המתמטיקה הוא שהיא מביאה זאת לקיצוניות. היא מפעילה הפשטה על תהליכי החשיבה הבסיסיים ביותר.
הדוגמה הקלאסית לכך היא מושג המספר. המספרים נולדו מהפשטה של תהליך החשיבה הבסיסי ביותר: חלוקת העולם לעצמים. היסוד לחשיבה הוא חלוקת העולם ליחידות, וכינוין בשם: "תפוח", "משפחה", "מדינה". מתוך התהליך הזה הומצאו המילים, וגם מושג המספר. הבחנה ביחידה אחת יוצרת את המושג "1": "תפוח אחד". כאשר אנו מבחינים בקיומן של יחידות נוספות מאותו סוג, אנחנו אומרים "2 תפוחים, 3 תפוחים, 4 תפוחים…".
אולם קיצוניות ההפשטה אינה המאפיין היחיד של המתמטיקה, ואינה הדרך היחידה לתהות על טבעה. אפשר לראות את המתמטיקה גם מזווית אחרת, פורמלית יותר, ולכך אנו מגיעים עתה.

3. פְרֶגֶה

למהפכה התעשייתית באירופה של המאה ה-19 היו תוצאות מרחיקות לכת לא רק לגבי איכות חייו של האדם, אלא לא פחות מכך גם על דרך תפיסתו של האדם את עצמו. משהתברר שמכונה יכולה להחליף שרירים ומיומנויות, התקצר המרחק למחשבה שהאדם בעצם דומה למדי למכונה. לא פלא הוא שתורתו של דרווין, שמיקמה את האדם כחבר בממלכת בעלי החיים, נולדה באותה תקופה, ודווקא באנגליה. מכאן לא היה המרחק רב לרעיון שמכונה תוכל להחליף את האדם גם בחשיבה. לא במפתיע, גם הרעיון הזה פותח בתחילה באנגליה, ערש המהפכה התעשייתית. באמצע המאה ניסה צ'רלס בבג' לבנות את מכונת חישוב המעשית הראשונה (רעיונות תיאורטיים באותו כיוון היו כבר לפסקל וללייבניץ, כמאתיים שנים קודם לכן). הוא לא השלים את המלאכה, אבל הרעיון היכה גלים.
כעשרים שנים מאוחר יותר, בשנות ה-70 של המאה, הגיע מתמטיקאי-פילוסוף בשם גוטלוב פְרֶגֶה (Gottlob Frege, 1848-1925) מן האוניברסיטה הלא כל כך מרכזית בעיר הגרמנית יֶנָה, לרעיון מרחיק לכת עוד יותר. לא זו בלבד, כך אמר, שמכונה יכולה לבצע פעולות מתמטיות, אלא שהחשיבה האנושית עצמה מתנהגת כמכונה. ואם אכן החשיבה מכאנית, הרי אפשר לחקור אותה בצורה מתמטית, כפי שחוקרים כל תופעה גשמית בעולם, כמו תנועת גרמי השמיים, או זרימה של נוזל בצינור. ומכיוון שמתוך כלל החשיבה האנושית החשיבה המתמטית היא זו המצייתת לחוקים הברורים והמוגדרים ביותר, המועמדת הראשונה לתיאור מתמטי היא בדיוק החשיבה המתמטית. זה היה רעיון מהפכני: לחקור בצורה מתמטית את החשיבה המתמטית. במילים אחרות, לעשות מתמטיקה של המתמטיקה. שם אחר לחקירה הזאת הוא "מטא-מתמטיקה".
בעידן המחשב הרעיון הזה נראה טבעי למדי. כיום אנו יודעים שחשיבה יכולה להיות נחלתה של מכונה, ומכונות מצייתות לכללים מוגדרים היטב, שאפשר לחקור אותם בצורה מתמטית. אבל בשלהי המאה ה-19, כאשר אפילו תורת דרווין הייתה חדשה וטרייה ונתונה במחלוקת, זו הייתה תובנה אמיצה מאוד. היא מצריכה את האדם לוותר על ייחודיותו, באותו תחום שבו נראה שהוא אכן שונה מכל שאר תופעות העולם: החשיבה המופשטת. בדיעבד, כאשר בוחנים את ההיסטוריה של התפתחות המחשב, זו הייתה נקודת מפנה משמעותית לא פחות מן המכונה של בבג'.
החשיבה המתמטית מורכבת מחלקים רבים. יש בה בניית מושגים כך שיתאימו לתופעות בעולם, יצירתן של השערות, בניית תורות וקישורן זו לזו. אבל בתוך כל אלה יש פעילות אחת שנחשבת בעיני המתמטיקאים למשמעותית ביותר: ההוכחה. להשערה טובה יש ערך, אבל הצעד המכריע הוא ההוכחה שלה. פרגה הגביל את עצמו לצד זה של החשיבה המתמטית, בעיקר משום שהתאים לתבנית שלו. הוכחה, כך אמר פרגה, היא תהליך מכאני, משחק בסמלים על נייר, שמציית לחוקים ברורים ואפילו פשוטים למדי. זהו "משחק" במובן זה, שיש לו כללים נוקשים וקלים לניסוח, לא שונים עקרונית מכללי משחק השחמט, למשל. יש צעדים מותרים, ויש צעדים אסורים. פרגה הגדיר "הוכחה" כסידרת משפטים הכתובים (נאמר) על נייר, שכל אחד מהם נובע מקודמיו על פי אחד מתוך מספר מצומצם של "כללי היסק". גם את הרעיון הזה קל לבני דורנו לקבל, משום שזוהי הדרך בה פועל המחשב. המחשב "חושב" על ידי כך שהוא לוקח סידרה של סמלים – אף כי לאו דווקא על נייר (במחשב הם מקודדים באותות חשמליים), ופועל עליהם לפי הכללים שֶמוֹרָה לו התוכנית המריצה אותו. הוא מקבל כקלט סידרת סמלים אחת, ומוציא כפלט סידרת סמלים שנייה. כיום כל זה מובן מאליו; בזמנו של פרגה, ההבנה שפעולה פורמלית על סמלים הכתובים על נייר יכולה להיות "חשיבה" הייתה תובנה חדשנית.

4. ראסל

עבודתו של פרגה, שפורסמה ב-1879, נתקלה בהתעלמות כמעט מוחלטת. המגיב היחיד עליה היה המתמטיקאי גיאורג קנטור, מייסד תורת הקבוצות, והוא קטל אותה (כפי שנראה בהמשך, קנטור עצמו זכה בתורו לטיפול דומה מצד מתמטיקאים אחרים). פרגה הפך למר נפש, ופרסם התקפות על המתמטיקאים של ימיו. ייתכן שהיה לוקח לאנושות זמן רב עוד יותר לעכל את תגליותיו, לולא פגש ברטראנד ראסל (Bertrand Russell, 1872-1970) בעבודתו. לראסל האנגלי הייתה בילדותו אומנת גרמניה, שבזכותה למד גרמנית, וכך הגיע בבחרותו לגרמניה לצורך לימודיו. הוא קרא את מאמריו של פרגה, הבין את גודל חשיבותם, וכשחזר לאנגליה גייס את אלפרד נורת' וויטהד, מורהו בקיימבריג', למשימת נפילים: לכתוב חלקים מן המתמטיקה של זמנם בשפתו של פרגה. לתוצר עבודתם, הספר "פרינציפיה מתמטיקה", הייתה השפעה עצומה. זהו ספר כבד עד כדי אי ניתנות לקריאה. אבל רבים הבינו את המסר שבו, שחשיבה יכולה להיתפס כעניין מכאני, המציית לכללים מוגדרים היטב. מכאן ועד ליצירת המחשב הדרך לא הייתה ארוכה במיוחד – כארבעים שנים בלבד.
בעיני פְרֶגֶה המתמטיקה היא אם כך משחק בסמלים. המתמטיקאי בוחר לעצמו מערכת אקסיומות, כמו למשל האקסיומות של תורת המספרים (דוגמה לאקסיומה: "לכל  $latex n $ מספר מתקיים $latex n+0=n $"). אחר כך הוא חוקר אילו משפטים אפשר להוכיח מן האקסיומות, על פי חוקי הוכחה נוקשים וידועים מראש. כמובן, זוהי זווית ראייה אחת, צרה למדי, על המתמטיקה, מכיוון אחד בלבד – ההוכחות. היא מתעלמת, למשל, מן השלב של בחירת האקסיומות: מדוע נבחרת מערכת זו, ולא אחרת? מערכות אקסיומות אינן מופיעות סתם כך. הן נועדות לתאר את המציאות. טיב מערכת האקסיומות יקבע אם יהיה לחקירה ערך, אם היא תוביל למסקנות עמוקות או תתגלה כריקה ומשמימה. בדרך כלל, אם האקסיומות באמת מגיעות מן המציאות, הן מתגלות כפוריות.
מעבר לכך, מעשה ההוכחה אינו באמת מכאני. עד היום אין יודעים דרך לתכנת מחשב כך שיגלה הוכחות בצורה יעילה. הדרך היחידה המוכרת לנו היא ניסוי וטעייה, ומכיוון שיש יותר מדי אפשרויות לבדוק, יותר מדי אפילו יחסית למהירותו של מחשב, זו אינה דרך מעשית. המתמטיקאי אינו עוסק בניסוי וטעייה. הוא מתבונן בבעיה ומנסה ליצור במוחו מבני חשיבה המתאימים לה. הוא חושב בצורה אינטואיטיבית. אני עצמי מאמין שיום אחד יבינו גם צד זה של החשיבה המתמטית, ויצליחו לתכנת גם אותו למחשבים. כאשר זה יקרה, המחשבים יידעו לשער השערות ולהוכיח משפטים מתמטיים מתוחכמים. וכשזה יקרה, זה יהיה בזכות תרומתו של פרגה.

---

השערה בת מאות שנים נפתרה בטכניון

אנה ליזהטוב

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

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

כידוע, גולדבך לא היה מתמטיקאי ידוע. אבל הוא התפרסם בזכות מכתב עם השערה ששלח ב-$latex {1742}$ למתמטיקאי הגדול של המאה השמונה עשרה, לאונרד אוילר. אוילר וגולדבך עבדו שניהם בסנט פטרסבורג, וגולדבך היה יכול לומר את ההשערה שלו בעל פה, אבל הוא העדיף לכתוב. ההשערה ששלח היא זאת:

האם כל מספר זוגי גדול מ-2 הוא סכום של שני מספרים ראשוניים?

למשל, $latex {100}$ יכול להיכתב כסכום של שני מספרים ראשוניים בחמש דרכים:

$latex \displaystyle 3+97,~~11+89,~~17+83, ~~29+71, ~~41+59$

ההשערה הזאת ידועה עד ל-$latex {10}$ בחזקת $latex {18}$, ואין איש מפקפק בנכונותה. אבל זוהי ראיה, ולא הוכחה, אפילו בשביל מתמטיקאים ניסוייים.

כהרגלו, תקף ד"ר פז את הבעיה מזווית לא צפויה. הוא לקח את תקנון האקדמיה הרוסית למדעים, שבה עבדו גם גולדבך וגם אוילר, בתרגומו של י. ברוידא, ודילג בו בקפיצות של $latex {17}$ אותיות - $latex {17}$ היה כידוע המספר החביב על אוילר. והנה, זה פלא, ראו מה גילה:

"כל מספר זזוגי גדול הוא סססכום שששל מממספרים ראששפסקלרך"

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

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

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

---

חידות לילדים

רון אהרוני