לדף הכניסה של ישרא-בלוג
לדף הראשי של nana10
לחצו לחיפוש
חפש שם בלוג/בלוגר
חפש בכל הבלוגים
חפש בבלוג זה




מלאו כאן את כתובת האימייל
שלכם ותקבלו עדכון בכל פעם שיעודכן הבלוג שלי:

הצטרף כמנוי
בטל מנוי
שלח

RSS: לקטעים  לתגובות 
ארכיון:


9/2017

משפט ארו והצבעות הוגנות


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

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


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

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

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

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

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

הוכחת משפט ארו
זו הוכחה שיש בה הרבה דברים שצריך לעקוב אחריהם, אז יש מצב שיש חלקים ששווה להתעכב עליהם ולקרוא אותם יותר מפעם אחת (אפשר גם להוציא דף ועט כדי לעשות תרשימים שיבהירו בכל שלב בדיוק מה קורה). ההוכחה מורכבת משלושה חלקים:
חלק א' - נוכיח כי תמיד קיים שחקן מכריע שיכול לשנות הצבעתו באופן שישנה את הדירוג הסופי של אופציה B ביחס לאופציה A כלשהי.
כדי להבין למה, ניקח את המקרה הכי קיצוני ונדמיין שכולם דירגו את A במקום הראשון ואת B במקום האחרון (על פי כלל הקונצנזוס, A יופיע במקום הראשון ו-B במקום האחרון בדירוג הסופי). עכשיו נעמיד פנים שאנחנו מסדרים את n השחקנים שלנו בשורה מסודרת כך שאחד אחד, כל שחקן משנה את ההצבעה שלו כך ש-B מופיע מעל A. בסוף התהליך הזה, על פי כלל הקונצנזוס, הדירוג הסופי של B יהיה יותר גבוה משל A. אם בתחילת התרחיש B היה מדורג מתחת ל-A ובסופו הוא מדורג מעליו, אז מן הסתם איפשהו באמצע התהליך היה שחקן מכריע שההצבעה שלו בעד B שינתה את התוצאה הסופית (ושאם הוא לא היה מצביע בעד B אלא בעד A אז B היה נשאר בתחתית). נכנה את השחקן הזה k.
אגב, שימו לב לתובנה החשובה הבאה - מפני שפונקציית הבחירה שלנו אדישה למניפולציות, המשפט הזה תופס לכל תרחיש שבו A דורג בהתחלה מעל B (לא משנה אם הם היו במקומות הראשונים והאחרונים), מפני שהתעלמות מהמתמודדים האחרים לא אמורה לשנות את הדירוג היחסי ביניהם.
חשוב לציין שאותו שחקן k לא "בוחר" להכריע את התוצאות במקרה הזה, זה פשוט משהו שהתקבל בדיעבד כתוצאה מהבחירות שלו ושל הקבוצה (באותה מידה, כל שחקן אחר יכול להיות המכריע בין A ל-B, הוא פשוט צריך להיות המצביע שמטה את לשון המאזניים).
חלק ב' - נוכיח כי השחקן המכריע k הוא דיקטטור על הדירוג של B מעל אופציה C כלשהי. כלומר - הדירוג היחסי שהוא יבחר עבור אופציות B ו-C חייב להישמר בתוצאה הסופית.
נסתכל על התרחיש הבא - כל שחקן עד השחקן k-1 (כולל) מדרג את B מעל C ואת C מעל A, השחקן המכריע k מדרג את A מעל B ואת B מעל C ובנוסף כל שארית השחקנים החל מ-k+1 ועד השחקן האחרון n מדרגים את A מעל B ואת B מעל C. נשים לב שהתרחיש הזה דומה מאוד לתרחיש הראשון, רק שדחפנו פנימה את האופציה הלא רלוונטית של C. מפני שפונקציית הבחירה שלנו אדישה למניפולציות, אפשר להתייחס אל זה כעל תרחיש דומה כמעט לגמרי לקודם.
(הדירוגים הנוכחיים)

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

(הדירוגים החדשים)

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

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

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

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

נכתב על ידי קרל שוורצשילד , 23/9/2017 17:16   בקטגוריות הוכחות, מתמטיקה  
13 תגובות   הצג תגובות    הוסף תגובה   הוסף הפניה   קישור ישיר   שתף   המלץ   הצע ציטוט
 



מתי שורש הוא מספר רציונלי?


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

 

נתחיל מעוד מקרה פרטי

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

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

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

כמובן, 5 הוא מספר ראשוני בפני עצמו, אז המכפלה שלו מורכבת ממספר אחד בלבד - 5.

קל לקחת את המשפט הזה ולפתח אותו למשפט העזר הבא:

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

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

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

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

אז הגענו לסתירה! המסקנה שלנו היא -  לא יכול להיות מספר רציונלי.

 

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

 

ועכשיו למקרה הכללי

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

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

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

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

בואו נסתכל על שתי דוגמאות:

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

- לעומת זאת, למספר  יש שורש רציונלי, מפני שניתן לבטא אותו בצורה , ולכן השורש שלו הוא פשוט , שהוא כמובן רציונלי. 

 

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

 

ההוכחה עצמה

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

א) אם למספר n יש שורש רציונלי, זה אומר שקיימים a, b כך שמתקיים - . נעלה בריבוע את שני הצדדים של המשוואה ונקבל - .

המסקנה - אם ל-n יש שורש רציונלי, אז ניתן לייצג אותו בתור מנה של שני ריבועים שלמים - מש"ל א'.

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

המסקנה - אם מספר ניתן לייצוג בצורה , אז השורש שלו הוא רציונלי. מש"ל ב'.

וזהו!

 

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

 

תרגילים למי שמעוניין

1) האם אתם יכולים לחשוב על משפט דומה שיעזור לקבוע מתי  רציונלי? ומה עם משפט כללי שקובע מתי  רציונלי?

2) הוכיחו את משפט העזר שהשתמשנו בו - יהיו j, k שני מספרים טבעיים, כך שאת j ניתן לחלק ל-r גורמים ראשוניים ואת k ניתן לחלק ל-s גורמים ראשוניים. למכפלה  יש  גורמים ראשוניים. (רמז - הרבה יותר קל משאתם חושבים. פשוט כללי כפל.)

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

__________________________________________________________________________________

 

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

כמו תמיד - אשמח לשמוע מה חשבתם על הפוסט ואם יש חלקים שדורשים הבהרות/שינויים.

שיהיה חג שמח ושנה טובה!

נכתב על ידי קרל שוורצשילד , 16/9/2017 16:52   בקטגוריות הוכחות, מתמטיקה  
24 תגובות   הצג תגובות    הוסף תגובה   הוסף הפניה   קישור ישיר   שתף   המלץ   הצע ציטוט
 



האלגוריתם של אוקלידס


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


האלגוריתם של אוקלידס - הקדמה

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

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

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

 

הנחות יסוד

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

1) עבור כל שני מספרים שלמים a, b (כל עוד b שונה מ-0) מתקיים , כאשר q הוא מספר שלם כלשהו, ו-r הוא מספר שלם המקיים  ומכונה "שארית החלוקה".

2) עבור כל a, b, הערך של q, r הוא ייחודי - אין יותר מזוג אחד q, r שמקיים את התנאי הזה. אם r=0, כלומר -  - אז אומרים ש-b מחלק את a, ומסמנים .

3) חלוקה היא יחס טרנזיטיבי. כלומר - אם  וגם  אז בהכרח גם מתקיים .

 

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

 

משפט 1 - אם  וגם  אז  עבור כל ערך של אלפא ובטא.

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

מ.ש.ל.

הערה - לצירוף מהסוג הזה של שני מספרים בתור סכום של של מכפלות קוראים "צירוף ליניארי". אם  אז נהוג לומר ש-x הוא צירוף ליניארי של y ו-z. זה מונח שיהיה חשוב בהוכחה של משפט העזר הבא.


משפט 2 - תהא S הקבוצה של כל הצירופים הליניאריים השלמים של a ו-b, ויהא d האיבר החיובי הכי קטן ב-S. עבור כל איבר u כלשהו ב-S מתקיים .

מפני ש-d הוא צירוף ליניארי של a, b, אז מתקיים . באותו אופן, u מקיים . נניח בשלילה שלא מתקיים  ונראה מה קורה:

אם d לא מחלק את u, אז על פי הנחת היסוד הראשונה שלנו מתקיים  כאשר . אם כן,

                                                   (מבודדים את r)

                    (מציבים את הערכים של d ו-u)

                  (מבטאים את r כצירוף ליניארי של a ו-b)

אבל שימו לב שאם הצלחנו לבטא את r בתור צירוף ליניארי של a, b אז גם r איבר ב-S. אבל מפני ש-  זה סותר את העובדה שבחרנו את d להיות האיבר הכי קטן ב-S. זוהי סתירה שנובעת מהטענה שהנחנו בשלילה, ואנחנו מגיעים למסקנה שבוודאות כל איבר u ב-S מתחלק ב-d.

מ.ש.ל.

זה משפט שימושי, אבל אנחנו נוכיח משהו עוד יותר חזק - אנחנו נוכיח ש-d הוא לא סתם מספר, אלא המחלק המשותף המקסימלי של a, b.

 

משפט 3 - אותו איבר d הוא מ.מ.מ(a, b), והוא גם מתחלק בכל מחלק משותף אחר של a ו-b.

נתחיל בלשים לב לכך ש-d חייב להיות מחלק משותף של a ושל b. ניתן להגיע לכך על ידי הסתכלות על שני המקרים הספציפיים:

מפני ש-d מחלק כל u, ומפני שחלוקה היא יחס טרנזיטיבי, אז אנחנו יודעים ש-d הוא מחלק משותף של a ושל b.

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

.

אם כן, d הוא מחלק משותף של a, b וגם מתחלק בכל מחלק משותף של a, b. מכאן ישירות ניתן להבין ש-d הוא המחלק המשותף הגדול ביותר של a, b (כי מספר לא יכול להתחלק במספר שגדול יותר ממנו), כלומר- .

מ.ש.ל.

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

 

משפט 4 - אם a=qb +r אז .

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

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

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

אבל אם הוכחנו ש- וגם הוכחנו ש- אז למעשה הוכחנו ש-.

מ.ש.ל

אגב, שימו לב למקרה הפרטי שבו r=0 - במקרה זה  וזה אומר ש-b הוא המחלק המשותף המקסימלי (זאת, מפני ש-b הוא המספר הגדול ביותר ש-b מתחלק בו, וגם a מתחלק ב-b). תזכרו את המקרה הפרטי הזה - הוא יופיע שוב בעוד רגע.

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

 

האלגוריתם של אוקלידס - עכשיו באמת

אז אנחנו מחפשים שיטה שתיקח שני מספרים a, b ותחזיר לנו את . כמו שראינו, לעשות רשימה מסודרת של כל המחלקים של כל אחד מהמספרים ואז לראות איזה מספר הכי גדול מופיע בשתי הרשימות זה תהליך איטי ומסורבל. אבל למזלנו, הוכחנו את משפט 4 שנותן לנו את התובנה החשובה - אם a=qb + r אז . המשפט הקטן הזה עושה לנו את החיים הרבה יותר קלים!

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

1. אם  אז . (זה המקרה הפרטי מתוך משפט 4)

2. אם , נבטא את a בצורה .

3. נזכור ש-, ולכן נחזור על האלגוריתם כאשר במקום a נציב את b ובמקום b נציב את r.

 

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

         (אז אנחנו חוזרים על האלגוריתם, רק שהפעם a=816, b=628)

              (a=628, b=188)

                   (a=188, b=64)

                           (a=64, b=60)

                                     (a=60, b=4)

כלומר -  זו התשובה שלנו.

 

הנה אנימציה שממחישה באופן חזותי איך "עובד" האלגוריתם כאשר מחפשים את המ.מ.מ של 1599 ו-650 (שיוצא 13).


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

 

תרגיל קצרצר למי שמעוניין

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

_____________________________________________________________________

 

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

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

אחלה שבוע שיהיה! חיוך

נכתב על ידי קרל שוורצשילד , 9/9/2017 16:50   בקטגוריות הוכחות, מתמטיקה  
10 תגובות   הצג תגובות    הוסף תגובה   הוסף הפניה   קישור ישיר   שתף   המלץ   הצע ציטוט
 



לדף הבא
דפים:  

Avatarכינוי:  קרל שוורצשילד

בן: 22




הבלוג משוייך לקטגוריות: מדע וטכנולוגיה
© הזכויות לתכנים בעמוד זה שייכות לקרל שוורצשילד אלא אם צויין אחרת
האחריות לתכנים בעמוד זה חלה על קרל שוורצשילד ועליו/ה בלבד
כל הזכויות שמורות 2017 © נענע 10 בע"מ