tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
בשנת 2006 טען החוקר רולאנד ואיובל (Roland Vaubel) שבארגונים בין ממשלתיים ובעיקר בגופים שהוקמו במסגרת משטר ברטון-וודס, קיימת בעיית הנציג.
לטענת ואיובל המדינות מודעות לבעיה אך אינן מסוגלות לפתור אותה.
ואיובל טוען שמכיוון שנציגי המדינות בארגונים, ועובדי הקבע בארגונים אינם נבחרי ציבור אלא ממונים על ידי הממשלות, הם אינם מרגישים מחויבות כלשהי לאזרחי המדינות ששלחו אותם.
יתרה מזאת, חלק גדול הם עובדי קבע המתמנים על ידי הארגון עצמו (לדוגמה עובדי הבנק העולמי) ולא על ידי המדינות מהן הגיעו, כאשר עובדים אלו כלל לא מרגישים במחויבות אל המדינות עצמן אלא אך ורק לארגון הבין ממשלתי בו הם עובדים.
אפשר לשים לב שהטענה של ואיובל דומה מאוד לטענה של אלג'י בנוגע לגרעון הדמוקרטי באיחוד האירופי.
ואיובל מוסיף וטוען שארגונים בין ממשלתיים גם כמעט ולא עומדים למבחן וביקורת של הציבור.
הוא מסביר זאת בגלל שילוב של מספר גורמים: שוני בשפה המדוברת בארגון מאשר במדינות, התעניינות מועטה של התקשורת המקומית בארגונים שכאלו, המרחק הרב בין מקום הקבע של הארגון לבין המדינות והנושאים הטכניים והמורכבים בהם עוסקים ארגונים שכאלו.
מורכבות שיוצרת קושי לביקורת ללא רקע חזק בתחום.
כל הגורמים האלו יחדיו יוצרים מצב בו הארגונים פועלים באופן כמעט חף מביקורת ומבצעים אך ורק את מה שהם מרגישים לנכון.
סוגיה נוספת אליה מתייחס ואיובל במחקרו היא סוגיית ההישרדות של ארגונים.
ואיובל טוען שאחת הסיבות שארגונים בין ממשלתיים פועלים בניגוד לכתב האמנה אותו קיבלו, נובעת מיצר ההישרדות שלהם.
זאת מכיוון שלאחר שהוקם ארגון מסוים, הוא הופך לישות קיימת וחיה.
הוא מעסיק עובדים רבים ומקבל זהות ונוצר מצב בו עובדיו והאנשים הנהנים ממנו עושים הכול כדי לשמר אותו בחיים.
אחת הדרכים לעשות זאת היא לעכב ביצוע של החלטות, במטרה למשוך זמן חיים לארגון או להרחיב את תחומי הפעילות כדי שהארגון לא ייתפס על ידי שולחיו כלא רלוונטי.
בכך מצטרף ואיובל לחוקר נוסף בשם רוברט מקאלה (Robert McCalla) שניסה להסביר בשנת 1996 מדוע נאט"ו (NATO) ממשיכה להתקיים למרות שברית המועצות התפרקה מזמן, והאיום על אירופה כביכול הוסר.
אחת מהמסקנות אליהן הגיע מקאלה היא שבנאט"ו, כמו בארגונים רבים אחרים, ישנו ייצר הישרדות מובנה.
יצר ההישרדות גורם לארגון להמציא עצמו מחדש, ולחפש תחומי אחריות וסמכויות חדשים בכל פעם שהוא מרגיש בסכנה או לא רלוונטי.
את הרחבת הסמכויות הוא עושה בהסכמת המדינות שהקימו אותו או אפילו בלעדיה.
במחקר מאוחר יותר שעשה ואיובל, הפעם יחד עם שני חוקרים נוספים, דרהר (Axel Dreher) ואורלוסוילו (U'urluSoylu), מצא ואיובל חיזוק לטענותיו.
המחקר המורחב מצא שבעוד קצב גידול המדינות בארגונים בין ממשלתיים הוא כ-2 אחוז בשנה, קצב הגידול בתקציבי הארגונים הוא כ-3 אחוז בשנה.
זהו גם גידול רחב הרבה יותר מאשר הגידול הממוצע בתקציבי ארגונים פנים מדינתיים.
את הפער בין קצב גידול הארגונים לתקציבם, ובין גידול הארגונים הבין ממשלתיים לפנים ממשלתיים מסבירים החוקרים על ידי מודל הנציג.
לטענתם, הארגונים הבין ממשלתיים פועלים באופן עצמאי בצורה רחבה הרבה יותר מארגונים פנים מדינתיים, ולכן יכולים לדרוש ולהגדיל את תקציבם בקלות רבה הרבה יותר, גם אם הדבר מנוגד לאינטרסים של המדינות ששלחו אותם.
כאשר ואיובל מנסה להסביר מדוע המדינות אינן פותרות את בעיית הנציג בעזרת אותם פתרונות שמציע מדע הכלכלה, הוא מגלה שהיכולות של מדינות לשנות ארגונים היא חלשה ביותר.
לטענתו ברגע שארגון נוצר הוא מקבל חיים משלו.
כדי לשנות אותו או לכפות עליו את דעת המדינות יש צורך בהחלטה משותפת של כל המדינות החברות בארגון, או לפחות רוב יחסי גדול.
השגת תמיכה ורוב כה גדול בקרב המדינות הוא מצב מסובך עד חסר סיכוי.
זאת בגלל אתגר הפעולה הקולקטיבית.
כך קורה שגם אותן ממשלות עצמן שמפעילות את הארגון אינן יכולות לפתור את בעיית הנציג, מה שהופך את הבעיה בארגונים בין ממשלתיים לבעיה קיצונית במיוחד.
אפשר לומר שקל הרבה יותר ליצור ארגון חדש מאשר לשנות ארגון קיים וזו, אולי, גם הסיבה לכך שאנו רואים תופעה שכזאת מדי פעם.
שימוש בבעיית הנציג על ידי גופים ציבוריים
מעבר לשימוש שנעשה באקדמיה ובמחקר כדי לנתח פעולות של גופים ופירמות באמצעות בעיית הנציג, ישנם גופים רבים המשתמשים במודל כדי לזהות, לנתח ולפתור בעיות עתידיות שאיתן הם מנסים להתמודד.
דוגמאות כאלו ניתן לראות גם בישראל וגם ברחבי העולם.
אגף החשב הכללי במשרד האוצר הזמין בשנת 2006 מחקר שינתח באמצעות בעיית הנציג את כל הגופים הנתמכים על ידי ממשלת ישראל באמצעות משרד האוצר.
זאת על מנת לבדוק באילו מאותם גופים הנתמכים ישנו סיכוי להיווצרות בעיית הנציג העלולה לגרום לבזבוז כספים מיותר ולניגוד עניינים בין משרד האוצר (המתפקד כמנהל) והגוף הנתמך (המתפקד כנציג).
בעיית הנציג בתאגידים ובדיני תאגידים
הבעיה נחקרה רבות בעיקר בהקשר של אופן ניהולן של חברות ציבוריות על ידי מנהלים שכירים ונמצאו לקיומה אישושים רבים בממצאים אמפיריים.
כך למשל, הונאת הבקדייטינג אשר הייתה נפוצה בחברות ציבוריות בשנות ה-90 של המאה ה-20, היא דוגמה לדפוס התנהגות של מנהלים הנוגד את אינטרס בעלי המניות.
דוגמה קונקרטית לבעיה היא מנהל המתוגמל לפי רווחיות החברה.
המנהל מתומרץ לקחת סיכונים מיותרים, משום שבמצב של הצלחה הוא יתוגמל בתגמול גבוה, אך אם פעולותיו תהיינה כושלות הנפגעים העיקריים יהיו בעלי המניות.
סוגיה נוספת מוכרת בשם דחיסת הדירוגים.
ישנן חברות רבות המשתמשות בהערכת ביצועים סובייקטיבית בשל חוסר במדדי ביצועים.
במקרים אלו, מנהלים מדרגים את ביצועיהם של עובדיהם.
עובדה מבוססת היא שהמנהלים מעריכים את עובדיהם בצורה טובה מידי (הטיית סלחנות) ושהערכה זו משתנה לעיתים נדירות (הטיית יציבות).
שתי הטיות קרובות - אלו תועדו (לאנדי ופאר בשנת 1980, מרפי וקליבלנד בשנת 1991).
הטיית הסלחנות של המנהלים נובעת מכך שהם חוששים להציג הבדלים מהותיים בין העובדים (מחשש לשבור את רוח הצוות) כאשר הטיית היציבות נובעת מהתנגדות מנהלים לתת דירוגים נמוכים לכפופים להם, במיוחד במקומות שדרוג זה קובע שכר ועלול ליצור דה-מוטיבציה לעבודה יותר מאשר מוטיבציה להשתפר.
המשפט מנסה להתמודד עם הבעיה בעיקר במסגרת דיני התאגידים והיא ידועה יותר כ"בעיית הנציג".
נהוג להתייחס לשלושה סוגים של בעיות נציג, המתארים שלושה מצבים של ניגודי אינטרסים המתעוררים במהלך חיי החברה:
בעיות נציג בין בעלי המניות להנהלת החברה - בעוד שבעלי המניות מעוניינים שכספי החברה יושקעו כך שהם יניבו עבורם רווחים, המנהלים (אשר מנהלים בפועל את תקציב החברה) נוטים לא פעם להשתמש בכסף לשם קבלת טובות הנאה (מכונית גדולה, מטוס מנהלים) על פני השקעות עסקיות.
בעיה במישור זה יכולה להתעורר גם כאשר המנהלים מעדיפים להימנע מנטילת סיכונים (בשל חששם למקום עבודתם), על אף שלבעלי המניות אינטרס בנטילת סיכונים (בשל אחריותם המוגבלת).
הפתרונות לבעיית נציג זו הם תקנון החברה (אשר מגדיר את מרחב שיקול הדעת ועצמאות המנהלים), הדירקטוריון וועדת הביקורת (כגופים מפקחים) וחובתם של בעלי התפקידים בחברה לפעול לקידום טובתה.
בעיות נציג בין בעלי מניות רוב לבעלי מניות מיעוט - בעלי מניות הרוב עשויים לקבל החלטות שמטיבות עימם, על חשבון בעלי מניות המיעוט.
דוגמה לכך היא בעל השליטה בחברה שעשוי לקדם עסקה בינו לבין החברה, אשר משרתת אותו אך פוגעת בחברה (מכירת נכס במחיר יקר בצורה קיצונית ממחיר השוק).
כך, בעוד שבעל השליטה הרוויח מן העסקה, בעלי מניות המיעוט נפגעו כיוון שהחברה בה הם מחזיקים עשתה עסקה לא כדאית והפסידה כסף.
הפתרונות לכך הם חובת האמונים של בעלי השליטה בחברה והליכי אישור מיוחדים לעסקאות עם בעלי השליטה.
בעיות נציג בין בעלי המניות לנושים של החברה - בעלי המניות מעוניינים שהחברה תיקח סיכונים עסקיים שעשויים להשיא רווחים גדולים, כיוון שהם לא חשופים לסיכונים אם החברה תפורק.
מנגד, הנושים (בעלי החוב) מעוניינים בניהול שמרני שיבטיח החזרת ההלוואות שניתנו לחברה.
כדי להבטיח הגנה נאותה לנושי החברה קיימים מנגנונים כמו הרמת מסך (המאפשרת תביעה אישית של בעל מניות בגין חובות החברה) וכללי שמירת ההון (המבטיחים שחלק מהון החברה לא יחולק כדיבידנד, ויישמר להחזרת חוב).
הבעיה קיימת גם עם נציגים לא אנושים כמו למשל מבחנים.
מקימים מבחן כדי לבדוק התאמה.
כמו למשל מבחן בגרות או פסיכומטרי כהתאמה ללימודים אקדמאים.
אבל מהר מאוד אנשים לומדים רק איך לעבור את המבחן, ואז המבחן בודק מי למד טוב למבחן ולא בהכרח מי מתאים.
אמנם ייתכן ויש מתאם בין השנים, אבל בשולים ייתכנו אנשים לא מתאימים שלמדו הרבה למבחן ויתקבלו לאקדמיה, ומצד שני אנשים מתאימים ללימודים אקדמאים שלא למדו למבחן לא יתקבלו.
המטופל שואף לעצמאות בעוד המטפל נהנה מהתלות של המטופל בו
המערכת מעוניינת בגמישות ועצמאות, המנהל מעוניין להיות בלתי ניתן להחלפה
ז'אק פרסקו מציע במתודולוגיית "פרויקט ונוס" מערכת כלכלית שונה המצמצמת את ניגוד האינטרסים בדינמיקות השונות תוך התבססות על מערכות בקרה, תמיכת החלטה, אוטומציות וממשול מבוזר, בסיוע טכנולוגיות שונות כגון בלוקצ'יין ובינה מלאכותית
בעיית ההתאמה של פוסט היא בעיה ידועה במדעי המחשב, שתוארה לראשונה בשנת 1946 בידי אמיל פוסט ומהווה דוגמה פשוטה יחסית (ועל כן שימושית) לבעיה בלתי כריעה, כלומר שאינה ניתנת לפתרון באמצעות מודלי החישוב המקובלים (ובפרט על ידי מחשב).
הבעיה עוסקת במחרוזות - רצפי אותיות מעל אלפבית כלשהו.
נתונה קבוצה סופית של זוגות של מחרוזות (בלי מגבלה על האורכים האפשריים שלהן), מהצורה .
השאלה היא האם ניתן לבחור חלק מהזוגות (אולי יותר מפעם אחת) ולשרשר את כל ה- בזוגות שנבחרו ואת ה- בזוגות שנבחרו (כלומר, לכתוב אותם בזה אחר זה) כך ששני השרשורים יתנו את אותה המחרוזת.
בכתיבה פורמלית, השאלה היא האם קיימת סדרת אינדקסים, , כולם בתחום כך ש-.
בדוגמה זו ניתן ליצור את המילה "בללייקה" סימולטנית באמצעות סדרת האינדקסים 1,2,2,3,4: החזרה על אינדקס ה-2 מכפילה את הל' בסדרת ה-, ואת ה-י' בסדרת ה-.
אם יוסר זוג מספר 2, לא ניתן יהיה למצוא התאמה.
בדוגמה זו ניתן להיווכח בקיום/אי קיום התאמה על ידי שיקולים פשוטים יחסית; בדוגמאות מורכבות יותר השיקולים הללו לא יעבדו יותר, ומכאן המוטיבציה לניסיון למציאת אלגוריתם כללי לפתרון הבעיה - אלגוריתם שכאמור, אינו יכול להתקיים.
ההוכחה המקובלת לאי כריעות בעיית ההתאמה מבוססת על אי כריעותה של בעיית העצירה.
הרעיון הבסיסי של ההוכחה הוא להראות כי ניתן לבצע מעין סימולציה של ריצת מכונת טיורינג באמצעות מופע של בעיית ההתאמה, כך שהמכונה מסיימת את ריצתה אם ורק אם קיימת התאמה במופע זה.
אם בעיית ההתאמה הייתה ניתנת לפתרון, אז בהינתן מכונת טיורינג וקלט ניתן היה לתרגם אותן למופע המתאים של בעיית ההתאמה, לפתור את המופע הזה (כלומר, לגלות האם קיימת בו התאמה או לא) ולהכריע בשאלת עצירתה של מכונת הטיורינג המקורית.
מכיוון שבעיית העצירה אינה כריעה, נובע מכך שגם בעיית ההתאמה חייבת להיות אי כריעה.
ראשית, במקום לעסוק ישירות בבעיית ההתאמה של פוסט עוסקים בווריאנט שלה, הזהה לה כמעט לחלוטין פרט לכך שזוג המחרוזות הראשונות שייבחר נתון מראש, ולא ניתן לבחירה מתוך כלל המחרוזות.
שלב א' - מעבר לבעיית התאמה עם מחרוזת ראשונה נתונה
הווריאנט על בעיית פוסט שבו משתמשים בהוכחת אי הכריעות הוא כדלהלן: נתון אוסף של זוגות של מחרוזות, , ובנוסף נתון עוד זוג אחד מיוחד, .
השאלה היא האם קיימת סדרת אינדקסים , כולם בתחום כך ש-.
בחלק הבא של ההוכחה מוכיחים כי בעיה זו אינה כריעה.
מכאן שכדי להראות כי בעיית פוסט המקורית היא בלתי כריעה, יש להראות כי ניתן "לתרגם" כל מופע של הבעיה החדשה למופע של הבעיה המקורית בצורה כזו שהמופע של הבעיה החדשה פתיר אם ורק אם המופע של הבעיה הישנה פתיר (דבר שכזה מכונה רדוקציה חישובית).
אם כן, נניח כי נתון אוסף זוגות וכמו כן נתון הזוג המיוחד .
הרעיון הבסיסי בהמרת בעיה זו לבעיית פוסט המקורית היא לקחת סימן שאינו באלפבית הנוכחי של המחרוזות (למשל, ) ו"להשתיל" אותו בתוך כל הזוגות באופן כזה שבאיבר הימני של כל זוג הכוכביות מופיעות לפני כל אות, ואילו באיבר השמאלי הכוכביות מופיעות אחרי כל אות.
מכאן שלא ניתן להתחיל את בניית המילה המשותפת עם אף אחד מהזוגות ש"טופלו" באופן שכזה, כי האיבר הימני בזוג מתחיל בכוכבית, ואילו השמאלי לא.
כדי שעדיין יהיה ניתן ליצור מילה משותפת, יש לתקן את הזוג בהתאם, וכמו כן להוסיף זוג אחד נוסף, ש"יסיים" את בניית המחרוזת וישווה את מספר הכוכביות שבכל אחד מהעותקים.
כדי לתאר בצורה פורמלית את הבנייה נוח להגדיר שתי פונקציות על מילים, , שעבור המילה "משתילות" כוכביות באופן הבא:
כעת, אם הוא אוסף הכללים של הבעיה שאותה מתרגמים, אז אוסף הכללים החדש יהיה
כאשר גם הוא סימן שאינו שייך לאלפבית של הבעיה המקורית.
שלב ב' - סימולציה של מכונת טיורינג באמצעות בעיית ההתאמה
חלקה השני של ההוכחה מסתמך על כך שהמודל החישובי של מכונת טיורינג הוא פשוט מאוד לתיאור, ועל כן ניתן לבצע מעין "סימולציה" שלו באמצעות בעיית ההתאמה.
הרעיון הבסיסי הוא לתאר חישוב של מכונת טיורינג בתור סדרה של תצורות (קונפיגורציות) שכל אחת מהן מתארת את מצבו הנוכחי של סרט הקלט, מיקום הראש הקורא והמצב הפנימי הנוכחי של המכונה.
קונפיגורציה שכזו נוח לתאר באמצעות סדרת תווים מהאלפבית של המכונה, המציינת את תוכן סרט הקלט הנוכחי (עם סימן מיוחד המצביע על הנקודה שבה מסתיים החלק של הסרט שבו נעשה שימוש עד כה), אשר בתוכה "מושתל" סימן המתאים למצב הפנימי הנוכחי של המכונה, והוא נמצא משמאל לתא בסרט שהמכונה קוראת.
מייצגת את הקונפיגורציה שבה החלק של הסרט שבשימוש מכיל את המחרוזת "01001010", המכונה נמצאת במצב הפנימי מס' 3, והראש הקורא מצביע על ה-"0" הלפני אחרון.
ניתן כעת לחשוב על חישוב שלם של המכונה כסדרה עוקבת של קונפיגורציות שמופרדות על ידי סימן מיוחד (למשל, כוכבית) כך שכל אחת מהן מתקבלת מקודמתה באמצעות פונקציית המעברים של מכונת הטיורינג.
הסימולציה של מכונת הטיורינג מתבצעת כך: ראשית, הזוג ההתחלתי של מילים בבעיית ההתאמה יהיה הזוג , כאשר היא המילה שעבורה נבדקת עצירת המכונה.
כלומר - האיבר השמאלי בזוג מתאר את הקונפיגורציה ההתחלתית של המכונה, ואילו האיבר הימני הוא "ריק".
מכאן שכדי שהזוגות ירכיבו את אותה המילה, בחירת האיברים הבאים צריכה להיות כזו ש"תעתיק" את הקונפיגורציה שקיימת באגף שמאל לאגף ימין.
הרעיון הוא שתוך כדי ביצוע ההעתקה הזו לאגף ימין, תיווצר (על ידי האיברים השמאליים בזוגות שיתווספו) קונפיגורציה חדשה באגף שמאל - כזו שנובעת מיידית מהקונפיגורציה הקודמת.
כך למשל לכל תו , הזוג מבטיח העתקה של תוכן הסרט מהקונפיגורציה הקודמת לנוכחית, וזוגות כמו (שמתאים למעבר ) מבטיחים את שינוי הקונפיגורציה החדשה על פי פעולה אפשרית עבור מכונת הטיורינג המסמלצת.
כל עוד המכונה לא הגיע למצב מקבל, אגף ימין לא יכול להדביק את אגף שמאל; על כן, מוסיפים זוגות שמאפשרים, בהינתן שאגף שמאל מייצג קונפיגורציה שהגיעה למצב מקבל, "למחוק" חלקים מהקונפיגורציה בכל העתקה שלה, עד שלבסוף אגף ימין מדביק את אגף שמאל.
בצורה זו מובטח שקיים פתרון לבעיית ההתאמה אם ורק אם המכונה המסומלצת מגיעה למצב מקבל.
במתמטיקה בכלל ובקומבינטוריקה בפרט, בעיית הנהגים הגחמנים (ידועה גם בשמות בעיית הנשים הגחמניות או בעיית החניה) היא בעיה העוסקת במספר הדרכים לשבץ n עצמים ב-n מקומות, כאשר לכל עצם יש מקום מועדף, ועצם שהמקום המועדף עליו תפוס, מוסט באופן עקבי כלפי מעלה.
אל חניון שבו יש מקומות חניה המסודרים בטור, מגיעים נהגים, בסדר קבוע.
לכל נהג יש מקום אחד מועדף (ללא קשר בין ההעדפות של הנהגים השונים).
כל נהג נוסע תחילה אל המקום המועדף עליו.
אם המקום פנוי הוא חונה בו, ואם הוא תפוס, הוא ממשיך בנסיעה ומחפש מקום חניה אחר.
הנהג אינו יכול לחזור אחורנית - ואם הוא לא מצא מקום פנוי, הוא יאלץ לוותר על החניה ולהתרחק מהמקום.
אם כל נהג בוחר את ההעדפה שלו בנפרד, כמה אפשרויות יש שעבורן כל הנהגים יחנו בסוף התהליך?
פונקציה, המתאימה את הנהגים למקומות החניה, כך שלכל נהג יש מקום חניה, קרויה פונקציית חניה.
הדיון בפונקציות כאלה החל במאמר
נניח שבחניון ישנם 3 מקומות חניה ומגיעים אליו 3 נהגים.
הנהג הראשון מעדיף את המקום 2, ושני הנהגים הבאים מעדיפים את המקום 1. הנהג הראשון יתפוס את המקום 2; אחריו יתפוס הנהג השני את המקום 1; הנהג השלישי לא יוכל לחנות במקום המועדף עליו, אבל יוכל לחנות במקום זאת במקום 3. הבחירות 2,1,1 מאפשרות חניה מסודרת.
לעומת זאת, אם הנהג הראשון מעדיף את המקום 1 ושני האחרים מעדיפים את 3, אז הראשון יחנה במקום 1, השני יסע למקום 3 ויחנה בו, והשלישי, שיסע בתחילה למקום 3, יאלץ לוותר ולעזוב.
הבחירות 1,3,3 אינן מאפשרות חניה מסודרת.
לבעיה זו נמצא פתרון אלגנטי המיוחס להנרי פולק ממעבדות בל בתחילת שנות ה-60, והוא כזה:
סדרה של מספרים בתחום 1 עד n תקרא פונקציית חניה, אם כאשר לכל , הנהג ה- בוחר במקום החניה ה בתור מקום מועדף, כל הנהגים מוצאים חניה.
נוסיף לחניון מקום חניה וירטואלי, , ונאפשר לבחור בו כמקום מועדף.
(כלומר, לאחר מקום החניה ה-, מגיעים למקום החניה הראשון).
כעת, כל הנהגים יכולים לחנות, משום שכל נהג ממשיך לחפש ואינו נוטש, ויש יותר מקומות מנהגים.
רשימה של העדפות (כמתואר מלמעלה) היא פונקציית חניה, אם ורק אם אף נהג אינו חונה במקום חניה ה:
אם אחד הנהגים עזב את החניון, מישהו יצטרך לחנות לאחר מקום החניה ה, ולכן יחנה במקום החניה ה (כי הוא הראשון אחרי ה).
אם מישהו חונה במקום החניה ה, זאת אומרת שמישהו הגיע למקום החניה ה והוא היה תפוס, ולכן היה אמור לעזוב את החניון, או שמישהו בחר במקום ה, אבל בפונקציית חניה זה לא אפשרי (הרי ).
נשים לב שהזזה ציקלית של הרשימה, מזיזה ציקלית את התוצאה הסופית של המעגל.
כלומר, תהי רשימת העדפות של הנהגים.
(כלומר, לכל , הוא המקום חניה המועדף על הנהג ה), ותהי רשימת הסיום במקרה זה (כלומר, בסוף התהליך סיים הנהג ה, במקום ה).
אזי רשימת הסיום של רשימת ההעדפות היא
כלומר, כל פונקציית חניה מופיעה ברשימות של ההעדפות האפשריות פעמים:
פעם אחת בתור פונקציית חניה (מתקבל מעגל בו במקום ה הוא ריק).
פעמים בתור עזיבת חניון של אחד הנהגים (שהרי, ניתן לסובב את המעגל n פעמים, כך שהמקום ה יהיה לא ריק).
נשים לב שבמקרה כזה תתקבל פונקציית חניה תקנית בה כל ההעדפות קטנות מ משום שאילו אחת ההעדפות הייתה המקום ה מקום זה היה נתפס, ולא הייתה מתקבלת פונקציית חניה.
כעת נסתכל על מספר הרשימות של ההעדפות האפשריות עם מקום החניה הנוסף: ישנן כאלה (כי לכל נהג יש אפשרויות למקום מועדף, ויש נהגים.
מכיוון, שכל פונקציית חניה מופיעה פעמים במספר הרשימות של ההעדפות האפשריות, ישנן בסה"כ פונקציות חניה, כלומר ישנן רשימות העדפות המאפשרות לכולם לחנות לפי הכללים.
בכלכלה ובמדע המדינה, בעיית הטרמפיסט היא כינוי למצב שבו קבוצה מסוימת נהנית משירות או ממוצר מסוים מבלי שהיא נושאת בעלויות שלו, או שהיא נושאת בהן באופי חלקי בלבד.
מקור השם הוא בדוגמה נפוצה לבעיה: אדם המשתמש בתחבורה ציבורית בלי לשלם.
אם אנשים רבים ינהגו כך, למערכת לא יהיה מספיק כסף כדי לפעול.
בדוגמה בדיונית נוספת מתוארת עיר ובה מערכת תחבורה ציבורית, הפועלת באופן בו רק האדם הראשון בכל יום שנכנס לאוטובוס משלם 10,000 ש"ח עבור הנסיעה, ואילו שאר האנשים נוסעים בחינם.
במצב זה, יש תמריץ לאנשים להימנע מלהיות ראשונים, ובכך להתחמק מתשלום עבור השירות.
בעיית הטרמפיסט מאפיינת מוצרים ציבוריים, ובדרך כלל הציפייה היא שהממשלה היא שתפתור אותה, באמצעות מיסוי או אסדרה.
דוגמה אופיינית לכך היא הצבא.
לו היה הצבא גובה תשלום מהאזרחים עבור שירותיו, גם מי שלא היה משלם היה נהנה מהגנתו.
מאחר שניתן לקבל את המוצר גם מבלי לשלם עליו, איש לא היה מוכן לשלם עבור קבלת השירות, והשירות לא היה מסופק כלל.
מסיבה זו ממשלות מתערבות ומממנות את פעילות הצבא באמצעות המיסים שהן גובות מהאזרחים.
גם במקרה זה הבעיה עשויה להתעורר, שכן גם אזרחים המתחמקים מתשלום מיסים נהנים מהגנת הצבא.
המדינה לא תקרוס אם מעטים יתחמקו מתשלום מיסים, אך אם התופעה תהפוך לנפוצה, המדינה לא תוכל להתקיים.
בעיית הטרמפיסט יכולה להיווצר גם במקרים בהם אין הממשלה מתערבת.
לדוגמה, אם מפעיל זיקוקי די-נור יגבה תשלום עבור הפעלתם, הוא לא יוכל למנוע גם ממי שלא שילם לצפות בהם.
דוגמה נוספת היא תוכנות לשיתוף קבצים, שמשתמשים רבים בהן מורידים קבצים, אך לא מעלים קבצים משלהם.
רוב אתרי שיתוף הקבצים פותרים בעיה זו באמצעות מתן שירותים טובים יותר למעלי הקבצים (מהירות הורדה גבוהה יותר, גישה לקבצים מוגבלים וכו') או הגבלה של המשתמשים שאינם מעלים קבצים.
מס ארגון מהווה דוגמה להתמודדות עם בעיה זו ביחסי העבודה.
בחקר תנועות חברתיות, מהווה בעיית הטרמפיסט דילמה עימה מתמודדים מארגנים, פעילים ופעילות ותיקים בתנועות חברתיות: כיצד לשכנע פעילים ופעילות חדשים להגיע להפגנות ופעילויות הכרוכות בזמן, מאמץ וסיכון, כאשר אם ההפגנה או השביתה תצלח ויעשה שינוי לטובת כלל התושבים, גם אלו שלא הסתכנו במעצר, אלימות וטירחה יהנו מפירות המאבק?
אחד הפתרונות שניתנו לבעיה זו היא הפיכת המחאה לאירוע מהנה חברתית או המאפשר רישות וקישוריות חברתית, וכך הפעילים יוכלו להרוויח גם אם המחאה בסופו של דבר תכשל.
דוגמה לכך ניתן למצוא באירועי מחאת "יוקר המחיה" שנערכו בשנת 2011 בתל אביב, בהם נעשה שימוש רב בפתרון זה.
בעיית הדוור הסיני היא בעיה בתורת הגרפים, העוסקת בדוור, שבמסגרת תפקידו עליו לצאת מבית הדואר העירוני, לעבור על פני כל הרחובות בעיר, כדי לחלק מכתבים לדיירי רחובות אלה, ולחזור לבית הדואר העירוני.
יש למצוא כיצד יעבור הדוור על כל הרחובות (הנפגשים בצמתים, שבהם אפשר לעבור לרחוב אחר) במסלול הקצר ביותר.
במונחים של תורת הגרפים דורשת הבעיה למצוא את המסלול הסגור הקצר ביותר העובר על כל הקשתות של גרף ממושקל בלתי מכוון.
בעיה מקבילה בתורת הגרפים היא בעיית הסוכן הנוסע, שבה נדרש מסלול העובר על כל הצמתים שבגרף.
בעיית הדוור הסיני נוסחה על ידי המתמטיקאי הסיני מיי-קו קואן בשנת 1962, ושמה ניתן לה על ידי אלן גולדמן.
כאשר בגרף יש מסלול אוילרי, שהוא מסלול בגרף העובר בכל קשת בו בדיוק פעם אחת, מסלול זה הוא כמובן הקצר ביותר.
בגרף שבו יש מסלול אוילרי, כל הצמתים הם מסדר זוגי (כלומר בכל צומת עובר מספר זוגי של קשתות), ולכן כאשר בגרף אין מסלול אוילרי, יש בו צמתים מסדר אי-זוגי.
על פי למת לחיצות הידיים, מספר הצמתים הללו הוא זוגי.
כדי לעמוד בתנאי הבעיה, יש לעבור פעמיים על קשתות היוצאות מצמתים אלה.
לשם כך נכפיל קשתות המחברות בין שני צמתים מסדר אי-זוגי (צעד השקול למעבר פעמיים על אותה קשת), ובכך נהפוך את המסלול לאוילרי.
בעת הכפלת הקשתות נבחר את אלה שאורכן הכולל הוא הקצר ביותר, ונקבל מסלול אוילרי הפותר את הבעיה.
נחקרו גם וריאציות אחדות של הבעיה, שנמצאו כבעיות NP-שלמות:
בעיית הדוור הסיני בגרף מעורב: בווריאציה זו, חלק מהקשתות מכוונות, כלומר ניתן לנוע בהן רק בכיוון אחד.
בעיית הדוור הסיני ב-k מסלולים: מציאת k מסלולים היוצאים כולם מצומת מסוימת, כך שכל קשת נכללת במסלול אחד לפחות.
המטרה היא להוזיל את מחירו של המסלול היקר ביותר.
בעיית הדוור הכפרי: נתונה גם תת-קבוצה של קשתות במשקל מינימלי.
יש למצוא מסלול מעגלי שכולל לפחות מעבר אחד על כל אחת מקשתות אלו (בנוסף למעבר אפשרי על קשתות נוספות).
בעיית הבקר של ארכימדס היא בעיה באנליזה דיופנטית העוסקת במספר ראשי הבקר של אל השמש הרועים, כביכול, בסיציליה.
הבעיה מיוחסת לארכימדס, אף כי יש על-כך עוררין.
הבעיה מבקשת למנות את בני הבקר, פרות ושוורים בארבעה צבעים, כשהיא משווה בין מספר בעלי החיים מכל מין וצבע.
מכיוון שמספר בני הבקר מכל סוג הוא שלם, יוצרים התנאים מערכת של משוואות דיופנטיות בשמונה נעלמים.
פתרון הבעיה מעלה שגודל העדר הוא מספר בן 206544 ספרות לפחות.
אפילו בגרסה מצומצמת, שבה יש תנאים ליניאריים בלבד, כולל הפתרון הקטן ביותר כ-50 מיליון בני בקר.
בעייתו של ארכימדס, שפרטיה נשכחו והתגלו רק במאה ה-18, הפכה לשם דבר: בעיה חישובית קשה במיוחד הייתה זוכה בספרות העתיקה לכינוי Problema Bovinum, "בעיית שוורים".
ב-1769 מונה המחזאי גוטהולד אפרים לסינג לספרן בספרייתו של ההרצוג אוגוסט שבעיירה וולפנביטל, גרמניה, שבה היו כתבי יד יווניים ורומיים רבים.
ב-1773 פרסם לסינג תרגום של כמה מכתבי היד האלה, עם הערות.
גרסה מקוצרת של הבעיה פרסם נֶסֶלמן (Nesselmann) ב-1842, בגרמנית.
גרסה זו מבקשת מן הקורא "...
מנה את מספר בני-הבקר אשר לשמש, הרועים בסיציליה, וצבעים להם ארבעה: לבנים כחלב, שחורים, נקודים וחומים ...", ומספקת אילוצים כגון "מספר השוורים הלבנים יגדל במחצה ושליש [היינו ב-5 שישיות של] מספר השחורים ממספר החומים", וכן הלאה.
המשוואות האלה מהוות מערכת משוואות ליניארית שאפשר לפתור בקלות יחסית; מספרם הכולל של בני הבקר, לפיה, הוא כפולה של 50,389,082.
הבעיה ממשיכה: "אם תוכל, רעי, למנות את העדרים בזכר ובנקבה; באשר אף אם רב כחך במספר, לא יגיע עד הנה:", ומוסיפה עוד שני תנאים - מספר השוורים השחורים והלבנים, יחד, הוא ריבועי; ומספר הנקודים והחומים הוא משולשי.
תנאים אלו מוסיפים זוג אילוצים ריבועיים, שאותם אפשר לתרגם למשוואת פל , כאשר .
הופעה זו של משוואת פל, שלא הייתה ידועה במערב עד המאה ה-18, היא סיבה נוספת לחשוד שלא מדובר במתמטיקה בת דורו של ארכימדס.
כיוון שהבעיה דורשת חישוב במספרים מרובי ספרות, היא נותרה בלתי פתורה עד ש-A.
Amthor תיאר ב-1880 דרך למצוא את הפתרון הכללי, העולה לכ- פרות ושוורים, והתוצאה המדויקת חושבה בעזרת מחשב ב-1965. חבילות-תוכנה מודרניות המסוגלות לאריתמטיקה במספרים גדולים, יכולות להציג את מאות אלפי הספרות של הפתרון, ללא קשיים מיוחדים.
בתורת הגרפים, בעיית המסלול הארוך ביותר היא בעיה המתייחסת לגרף נתון ועניינה מציאת המסלול הפשוט (שאינו חוזר לאותו צומת פעמיים), שאורכו מרבי מבחינת מספר הקשתות בו או מבחינת סכום משקלי הקשתות (במקרה של גרף משוקלל).
בעיית המסלול הארוך היא בעיה NP-קשה; לא ידוע אלגוריתם יעיל (אלגוריתם עם זמן ריצה פולינומי) שפותר את בעיית המסלול הארוך ביותר, ומציאת אלגוריתם כזה תוכיח ש-P=NP (ולכן הסברה היא שאלגוריתם כזה לא קיים).
בעיית ההכרעה המתאימה: השאלה האם קיים מסלול פשוט בגרף ארוך יותר ממספר מסוים היא בעיה NP שלמה.
כמו מושגים רבים אחרים במתמטיקה, גרף הוא מושג מופשט, המוגדר באופן פורמלי, ואשר עשוי לייצג מערכות ראליות מן המציאות החומרית (כגון, כבישים, רשתות מחשבים, רשתות חברתיות, ועוד) ובעצם כך לשמש לפתרון בעיות מעשיות.
כהגדרה פשטנית, גרף הוא אוסף של צמתים או מקומות נקודתיים (הנקראים גם קדקודים), המחוברים ביניהם באמצעות "ענפים" הנקראים צלעות או קשתות.
החיבור בין כל שני צמתים עשוי להיעשות על ידי קשתות שונות, בעלות משקל או אורך שונה, וגרף עשוי להיבדל ממשנהו רק בקשתות המחברות את הצמתים בו.
חיבור כל הקשתות בגרף נתון נקרא מסלול.
גרף נקרא פשוט אם ניתן לחבר את כל הקשתות בו למסלול העובר בכל קדקוד פעם אחת בלבד.
מציאת המסלול הקצר ביותר המחבר בין כל קדקודי הגרף, כמו גם המסלול הארוך ביותר, אינה אפשרית תמיד ותלויה בסוג הגרף.
ידוע כי ניתן למצוא את המסלול הקצר ביותר באופן יעיל (בזמן ריצה פולינומי).
לעומת זאת, מציאת המסלול הארוך ביותר, היא בעיה NP קשה - שאפשרות פתרונה בסיבוכיות זמן פולינומית מוטלת בספק ושמציאת פתרון יעיל עבורה משמעה פתרון יעיל עבור כל בעיות מחלקת NP.
נראה כי בעיית המסלול הארוך ביותר היא בעיית NP קשה (קשה לפתרון מבחינה חישובית לפחות כמו כל בעיה השייכת ל-NP), על ידי רדוקציה פולינומית של הבעיה (המרה אלגוריתמית בסיבוכיות פולינומית) לבעיית מציאת המסלול ההמילטוני שהיא בעיה NP שלמה.
נציג טרנספורמציה שתיקח כל מופע של הבעיה המוכרת, ותהפוך אותו למופע של הבעיה החדשה.
הרדוקציה היא זו: ניקח את הגרף, נסמן ב-V את מספר הקדקודים בו, ונגדיר שמשקל כל צלע בו שווה ל-1; כעת נשאל האם משקל המסלול הארוך ביותר שווה למספר הקדקודים בגרף V.
נוכיח כי תשובה חיובית לבעיה החדשה שקולה (כלומר: נכונה אם ורק אם) לתשובה חיובית גם לבעיה המוכרת:
אם יש בגרף הנתון מסלול המילטוני, אזי יש מסלול שעובר בכל הקדקודים בגרף פעם אחת בדיוק.
כלומר, למסלול יש V קדקודים וצלעות.
כיוון שמשקל כל צלע הוא 1, אז משקל המסלול הוא V, ולכן התשובה חיובית גם לבעיה החדשה.
אם יש בגרף מסלול באורך V, הרי שהמסלול עובר ב V קדקודים; אבל V הוא מספר הקדקודים בגרף, ולכן יש גם מסלול המילטוני.
מכיוון שלא משנים את הגרף, אלא רק סופרים את מספר הקדקודים בו, הרי שזמן הספירה הדרוש כדי לעבור את כל הקדקודים יהיה לכל היותר V.
לכן, הטרנספורמציה ניתנת לביצוע בזמן ליניארי והרדוקציה היא אכן פולינומית.
בעיית היפהפייה הנרדמת היא בעיה פילוסופית-מתמטית מתחום תורת ההחלטות העוסקת בתפיסה של הסתברות והתמצאות עצמית.
הבעיה מתוארת כניסוי מחשבתי במהלכו מטילים מטבע הוגן ובהתאם לכך מעירים את היפהפייה הנרדמת פעם (כאשר התוצאה היא "עץ") או פעמיים (כאשר התוצאה היא "פלי"), בעוד שזיכרון ההתעוררויות הקודמות נמחק.
בכל פעם שהיא מתעוררת, היא נשאלת למידת אמונה בכך שתוצאת ההטלה שהביאה לאותה התעוררות הייתה "עץ" (כלומר, מהי בעיניה ההסתברות לתוצאה זו).
הבעיה התפרסמה לראשונה בשנת 2000 על ידי אדם אלגה, בהתבססו על מאמר מאת ארנולד זובוב (Arnold Zuboff), שטרם ראה אור באותה עת.
מאז פרסומה עוררה הבעיה מחלוקת בין החוקרים, שנחלקו לשתי קבוצות.
בעוד שרובם דגלו בתשובה "שליש" כתשובה הטובה ביותר שיכולה היפהפייה הנרדמת לתת, צידדו היתר בתשובה "חצי".
ביום ראשון פורשת היפהפייה הנרדמת לישון.
לפני הירדמה, מספרים לה מבצעי הניסוי כי יעירו אותה פעם או פעמיים, בהתאם לתוצאת הטלת מטבע הוגן: אם תוצאת ההטלה תהיה "עץ" - אזי תוער היפהפייה ביום שני בלבד.
אם "פלי" - היא תוער פעם אחת ביום שני ופעם נוספת ביום שלישי.
כמו כן, מודיעים לה כי לאחר כל התעוררות תקבל סם שכחה, שימחק את זיכרון ההתעוררות הקודמת, וירדים אותה שוב.
כשהיא מתעוררת נשאלת היפהפייה מהי מידת אמונה בכך שתוצאת הטלת המטבע הייתה "עץ".
כאמור, נחלקים החוקרים לשתי קבוצות: בעוד שרוב החוקרים סבור כי תשובתה של היפהפייה צריכה להיות "שליש" (מכאן כינויים באנגלית, Thirders), סבורה קבוצת המיעוט כי על תשובתה להיות "חצי" (ומכאן כינויים, Halfers).
אם נחזור על הניסוי פעמים רבות, בערך במחצית מההטלות יתקבל "פלי", בעוד שבמחצית השנייה יתקבל "עץ".
אם התקבל "פלי" בהטלה מסוימת - נוספות שתי התעוררויות למניין ההתעוררויות שבהן המטבע הורה "פלי".
אם התקבל "עץ" - נוספת התעוררות אחת בלבד למניין ההתעוררויות שבהן המטבע הורה "עץ".
כלומר, בשליש מן ההתעוררויות המטבע הורה על "עץ".
לכן, טוענים הדוגלים בשיטת ה"שליש", מידת אמונה של היפהפייה בכך שהמטבע הורה "עץ" בהתעוררות כלשהי צריכה להיות שליש.
הסיכוי לקבלת תוצאת "עץ" בהטלת מטבע הוגן הוא חצי.
מאחר שהיפהפייה יודעת כבר בתחילת הניסוי שיעירו אותה פעם אחת לפחות, ולאור העובדה שהיא איננה מסוגלת לזכור את ההתעוררויות הקודמות (אם היו כאלה), הרי שהיא אינה מקבלת כל ידע חדש במהלך הניסוי.
לכן, גורסים הדוגלים בשיטת ה"חצי", על היפהפייה להאמין כי ההסתברות לתוצאת "עץ" היא חצי.
על פניו נראה כי שתי התשובות הגיוניות.
אם כך, מה על היפהפייה לענות?
הדיון בין החוקרים מתמקד בעיקר בשאלה האם השיגה היפהפייה מידע חדש מההתעוררות הנוכחית שלה.
נסמן את שלוש ההתעוררויות האפשריות כדלהלן:
ע1 - המטבע הראה "עץ" וזהו יום שני
פ1 - המטבע הראה "פלי" וזהו יום שני
פ2 - המטבע הראה "פלי" וזהו יום שלישי
אם נגדיר, כפי שמציע אלגה, "היגד ממוקד" (centered proposition) כהיגד המסמן אדם מסוים במרחב או בזמן, הרי ש-פ1 ו-פ2 מהווים שני היגדים ממוקדים שונים.
לעומת זאת, שניהם מתארים את אותו עולם לא-ממוקד (uncentered), שבו הורה המטבע "פלי".
בכך מסביר אלגה את המקור לשינוי בתשובתה של היפהפייה לשאלה: אם לפני תחילת הניסוי היה עליה להשיב כי היא מאמינה שהסיכוי ל"עץ" הוא חצי, הרי שלאחר ההתעוררות עליה להשיב "שליש".
הסיבה לשינוי אינה ידע חדש שקיבלה, אלא מעברה ממצב שבו היא אינה מייחסת למיקומה הנוכחי (בזמן) חשיבות ביחס לשאלת אמיתות ההיגד "המטבע הורה 'עץ'", למצב שבו היא כן מייחסת לכך חשיבות.
במאמר משנת 2001 חלק הפילוסוף דייוויד לואיס על אלגה, בטענה שהיפהפייה לא קיבלה שום מידע חדש, ממוקד או לא, במהלך הניסוי, שכן היא ידעה מראש שיעירו אותה, והיא עדיין אינה יודעת באיזו התעוררות מדובר.
לב ויידמן וסיימון סונדרס חיזקו את טיעונו של אלגה בעזרת הצגת וריאציה על הניסוי המקורי: בגרסה שלהם, מבוצע הניסוי בכל שבוע במשך 100 שנים.
על מנת להימנע מהמוזרות העולה מטיעונו של אלגה, שלפיו היפהפייה משנה את דעתה על טענה לא-ממוקדת מבלי שהשיגה שום מידע לא-ממוקד חדש, הם הציעו להחליף את השאלה בשאלה ממוקדת: מהי מידת האמונה של היפהפייה בכך שהמטבע הורה "עץ" בשבוע הנוכחי.
מאחר שמצבה של היפהפייה זהה בכל השבועות (משום שכל המטבעות הוגנים), אין זה משנה שהיא איננה יודעת באיזה שבוע היא נמצאת.
מידת אמונה בתוצאה בגרסה החדשה של הניסוי צריכה להיות זהה לזו של הניסוי המקורי.
בנוסף לכך הציעו ויידמן וסונדרס גרסה בה חוזרים על הניסוי במשך שבועיים בלבד.
במקרה זה מידת אמונה של היפהפייה בתוצאה "עץ" (שהוא "Heads", באנגלית, לעומת "פלי" - "Tails") צריכה להיות שווה לסכום הסיכויים לתוצאה "עץ" בהינתן כל אחד מהצירופים האפשריים של שתי הטלות המטבע בשני השבועות (עץ-עץ (HH), פלי-פלי (TT), עץ-פלי (HT), פלי-עץ (TH)), כפול הסיכוי לאותו רצף הטלות (נוסחת ההסתברות השלמה):
אם מתייחסים למספר ההתעוררויות הנובע מכל תוצאה אפשרית של הטלות מטבע, התשובה המתקבלת מחישוב זה היא שליש:
ניתן לראות מיידית כי הסיכוי ל"עץ" בהינתן "עץ-עץ", , הוא 1, בעוד שהסיכוי ל"עץ" בהינתן "פלי-פלי", , הוא 0.
אם באחד מהשבועות התקבלה התוצאה "עץ" בעוד שבשני "פלי", הרי שישנן שלוש התעוררויות (אחת עבור התוצאה "עץ", ושתיים עבור התוצאה "פלי").
מכאן שהסיכוי ל"עץ" בהינתן "עץ-פלי" או "פלי-עץ" הוא שליש, .
אם ננרמל את הסיכויים שקיבלנו באמצעות חלוקה במספר ההתעוררויות בכל אפשרות, נקבל , , ו-.
מהצבה של כל התוצאות שקיבלנו בנוסחת ההסתברות השלמה הנ"ל, נקבל , כלומר - שהסיכוי ל"עץ" הוא שליש, כמו בגרסה המקורית של הניסוי.
אם, מאידך, משתמשים בהנחתו של לואיס, שלפיה לכל האפשרויות סיכוי זהה:
התוצאה המתקבלת עבור הניסוי בן השבועיים היא , בניגוד לתוצאה ("חצי") שהייתה מתקבלת מאותה הנחה בניסוי בן השבוע.
אם נניח כי מידת אמונה של היפהפייה צריכה להיות זהה בשני המקרים, טוענים ויידמן וסונדרס, הרי שיש בכך כדי להפריך את טענתו של לואיס.
מאוחר יותר ב-2001 הצביע ויידמן על כך שהבעיה ניתנת לפתרון במסגרת פירוש העולמות המרובים של מכניקת הקוונטים.
מאז התגלתה מחלוקת נוספת באשר לפרשנות הניתנת לבעיה בפירוש העולמות המרובים.
בניסיון לפתור את בעיית המדידה העולה ממכניקת הקוונטים, לפיה לא ברור מה קורה לפונקציית הגל כאשר מתבצעת מדידה, הוצעו מספר פרשנויות לתורת הקוונטים לאורך השנים.
הפרשנות הפופולרית ביותר כיום היא זו המכונה פרשנות קופנהגן, שנוסדה על ידי נילס בוהר.
לפי פרשנות קופנהגן, קיימת אי-ודאות אמיתית באשר לתוצאת ניסוי קוונטי עתידי.
כך, אם לניסוי מסוים מספר תוצאות אפשריות, לפני ביצוע הניסוי אנו יכולים להעריך את הסיכוי לקבלת כל אחת מהן, ואין לנו כל דרך לחזות בצורה מדויקת את התוצאה מראש.
בעת המדידה מתרחשת קריסה, המותירה רק אחת מהתוצאות האפשרויות.
היקום המתואר על ידי פרשנות קופנהגן הוא לא-דטרמיניסטי ולא-לוקלי.
שני מאפיינים אלה נחשבים בעיני חלק מהפיזיקאים, ביניהם אלברט איינשטיין, כחסרון משמעותי לכל תאוריה פיזיקלית.
אחת מהפרשנויות המתחרות בפרשנות קופנהגן היא פירוש העולמות המרובים, שהוצע לראשונה על ידי יו אוורט בשנת 1957. לפי פרשנות זו לא קיימת קריסה: כל התוצאות האפשריות מתגשמות, והעולם מתפצל למספר עולמות אפשריים (כמספר התוצאות האפשריות).
בצורה זאת התאוריה נותרת דטרמיניסטית ולוקלית.
לכאורה, מאחר שפירוש העולמות המרובים הוא דטרמיניסטי אין במסגרתו משמעות למושג הסתברות.
ואכן, אין הסתברות אמיתית בפירוש העולמות המרובים.
כך לדוגמה, אם נבצע ניסוי במסגרתו נשלח את הצופה לאחד משני חדרים זהים, א' או ב', על סמך תוצאת הטלת מטבע, יהיה זה חסר משמעות לשאול אותו לפני הניסוי מהי ההסתברות לכך שהוא ימצא עצמו בחדר א'.
זאת משום שהצופה שלפני הטלת המטבע הוא "אביהם הקדמון" של שני הצופים שיתקיימו לאחר ההטלה (אחד בכל חדר אפשרי), כך שההסתברות לכל אחת מהאפשרויות היא 1.
ובכל זאת, ניתן לדבר על אשליה של הסתברות, כפי שמתאר ויידמן: נניח כי ניתן לצופה גלולת שינה לפני הטלת המטבע, ונעיר אותו רק לאחר העברתו לחדר המתאים.
בצורה זו נוכל לשאול כל אחד מה"צאצאים" (הצופים שיתקיימו לאחר הטלת המטבע), לפני שנגלה להם מה הייתה תוצאת הניסוי, באיזה מבין החדרים הם סבורים כי הם נמצאים.
אשליית ההסתברות מושגת באמצעות זכרונותיו של הצופה בעולם מסוים, הכוללים זכרונות מעולם אחד בלבד מכל התפצלות קודמת.
כך שלמעשה צופה בפירוש העולמות המרובים וצופה זהה בפרשנות הכוללת קריסה (כמו פרשנות קופנהגן) יחלקו את אותם הזכרונות.
בפירוש העולמות המרובים, לכל עולם אפשרי מוגדרת מידת קיום (measure of existance) המקבילה לסיכוי לקבלת אותה תוצאה בפירוש ההסתברותי (הוא פרשנות קופנהגן).
ניתוח בעיית היפהפייה הנרדמת בפירוש העולמות המרובים
מושג ה"אשליה של הסתברות", בייחוד כפי שהוא בא לידי ביטוי בניסוי "גלולת השינה" המתואר לעיל, מזכיר באופיו את בעיית היפהפייה הנרדמת.
לפי ויידמן אין משמעות ישירה להסתברות לפני הניסוי, משום שכל המידע (ממוקד או לא) נמצא בידי היפהפייה לפני ביצוע המדידה.
ה"צאצאיות" שלה, לעומת זאת, בורות באשר לתוצאת הניסוי, ולכן מחזיקות באמונות זהות לגביה.
למרות זאת, בשונה מניסוי "גלולת השינה" בבעיית היפהפייה הנרדמת היפהפייה אינה מודעת לא רק לתוצאת המטבע, אלא גם ליום בשבוע.
השאלה שעלינו לשאול במסגרת פירוש העולמות המרובים היא "מהי מידת אמונה של היפהפייה בתוצאה 'עץ' בעולם שבו היא נשאלת?".
לטענת ויידמן, מאחר שמידת הקיום של כל שלושת העולמות האפשריים (ע1, פ1, פ2) זהה, ורק אחד מהם מתאים לתוצאה "עץ", עליה לענות "שליש".
לעומתו מאמין פיטר לואיס שלפי פירוש העולמות המרובים התשובה לשאלה היא "חצי".
על מנת להסביר זאת משתמש לואיס תחילה בגרסה פשטנית יותר של הניסוי, בה לא מטילים מטבע כלל, אלא מודיעים ליפהפייה כי יעירו אותה גם ביום שני וגם ביום שלישי, אך שהיא לא תזכור את ההתעוררות הראשונה.
כאשר מעירים אותה היא נשאלת מהי מידת אמונה בכך שהיום הוא יום שני.
לואיס מצביע על הדמיון בין גרסה זו של הניסוי לבין מצב הדומה לניסוי "גלולת השינה" הנ"ל בפירוש העולמות המרובים.
בשני המקרים על הצופה להאמין במידה שווה בשתי התוצאות האפשריות (כלומר - "חצי").
לואיס טוען כי קביעת הסתברות השווה ל-1 לכל אחת מהתוצאות האפשרויות לפני פיצול העולמות אינה לגיטימית, משום שהיא סותרת את חוק בורן, המגדיר את הסיכוי לקבלת תוצאה מסוימת בניסוי קוונטי.
מכאן מסיק לואיס כי ההסתברות טרם הפיצול שווה לחצי בשני המקרים (היפהפייה הנרדמת ו"גלולת השינה").
מעבר לכך, הוא גורס כי ניתן לתאר את הגרסה המלאה של בעיית היפהפייה הנרדמת בעזרת הגרסה הפשטנית: מטילים מטבע.
אם תוצאת ההטלה היא "עץ", מעירים את היפהפייה ביום שני בלבד, ואם "פלי" - הגרסה הפשטנית של הניסוי נכנסת לפעולה.
כתוצאה מכך, לטענת לואיס, ניתן לראות בבעיה שתי הטלות מטבע: אם בהטלה הראשונה הורה המטבע "עץ", היפהפייה תתעורר ביום שני בלבד.
אם הורה "פלי", מטילים מטבע נוסף.
אם הוא הורה "עץ", מעירים אותה ביום שני בלבד, ואם "פלי" - רק ביום שלישי.
כך שגם במקרה של הבעיה המלאה התוצאה היא "חצי", כפי שמאמין לואיס.
דייוויד פפינו וויקטור דורה-וילה תוקפים את טענתו של לואיס לפיה הבעיה המלאה מקבילה לשתי הטלות מטבע.
לדעתם בגרסה המלאה המקורית, כאשר היפהפייה מתעוררת פעם אחת בלבד, היא אינה יכולה להתייחס להתעוררותה כאל עדות כלשהי לתוצאת הטלת המטבע.
מעבר לכך, הם טוענים כי האנלוגיה שיצר לואיס בין הגרסה הפשטנית של הבעיה לבין ניסוי "גלולת השינה", עליה הוא ביסס את טיעוניו, איננה נכונה: בעוד שבניסוי "גלולת השינה" מתקיימים שני עולמות אחרי המדידה, הרי שקיים רק עולם אחד (בו מעירים את היפהפייה פעמיים) בגרסה הפשטנית לבעיית היפהפייה הנרדמת.
לכן ההסתברות לכך שהיפהפייה תתעורר ביום שני (וביום שלישי) תמשיך להיות 1.
בתגובה לפפינו ודורה-וילה ענה לואיס לשאלת הפיצול בכך שטען כי מאחר שהצופה (מניסוי "גלולת השינה" או היפהפייה הנרדמת) אינו מודע לתוצאה, שני המקרים "זהים אפיסטמית" (כלומר, בשניהם הצופה נמצא במצב תודעתי דומה).
מעבר לכך טען לואיס כי אין פיצול אמיתי של המציאות גם במקרה של פירוש העולמות המרובים, אלא רק בורות של הצופה באשר למיקומו.
בנוסף הבהיר לואיס כי בתארו את הבעיה כשתי הטלות מטבע הוא לא תיאר את מהלך האירועים האמיתי, אלא את הבסיס לניחוש של היפהפייה.
כמו כן, המשיכו פפינו ודורה-וילה, טענתו של לואיס לפיה גם במקרה שקיימים הבדלים מטאפיזיים בין המצבים הם מקבילים אפיסטמית, סותרת את העיקרון העיקרי (Principal Principle), שטבע דייוויד לואיס, לפיו מידת האמון בתוצאה מסוימת צריכה להתאים להסתברות האובייקטיבית שלה.
הוויכוח באשר לפתרון בעיית היפהפייה הנרדמת, הן בניסוחה הרגיל והן במסגרת פירוש העולמות המרובים, עדיין ניטש.
בעיית המעגל של גאוס, היא הבעיה של ההערכה המדויקת של מספר נקודות הסריג (כלומר נקודות ששיעוריהן הם מספרים שלמים) הנמצאות בתוך מעגל שמרכזו בראשית הצירים ורדיוסו r.
הראשון שעסק בבעיה ועשה התקדמות לקראת פתרון היה קרל פרידריך גאוס, ומכאן שמה.
נסתכל על מעגל ב- עם מרכז בראשית ורדיוס r ≥ 0. בעיית המעגל של גאוס מבקשת לדעת כמה נקודות יש בתוך המעגל הזה עם הצורה (m,n) כאשר m ו-n שניהם מספרים שלמים.
מכיוון שהמשוואה של המעגל הזה בקוארדינטות קרטזיות היא x2 + y2 = r2, הבעיה שקולה לשאלה כמה זוגות של מספרים שלמים m ו-n יש כך ש-:
אם התשובה עבור r נתון תסומן ב- אזי הרשימה הבאה מראה את הערכים הראשונים של עבור r טבעי בין 0 ל-10:
השטח בתוך מעגל בעל רדיוס r הוא πr2, ומכיוון שריבוע בעל צלע 1 משמעותו נקודת סריג אחת, אזי התשובה המצופה אמורה להיות לכאורה בערך πr2. למעשה התוצאה ברוב המקרים גבוהה במקצת מזו, מכיוון שמעגלים יותר יעילים בתחימת שטח מאשר ריבועים.
אפשר לבטא את התשובה בצורה: כאשר היא פונקציית שגיאה לא ידועה כלשהי.
מציאת חסמים נכונים ל- תביא לפתרון הבעיה.
הארדי, ובאופן בלתי תלוי לנדאו, מצאו חסם תחתון נמוך יותר והראו:
באמצעות סימן o הקטן, קיימת השערה שהחסם הנכון הוא:
אם נכתוב , החסמים העכשוויים על t הם : כאשר החסם התחתון נמצא על ידי הארדי ולנדאו בשנת 1915 ואילו החסם העליון הוכח על ידי מרטין הוקסלי בשנת 2000.
הערך של ניתן לביטוי באמצעות מספר טורים.
במונחים של סכום שכולל בתוכו את פונקציית הרצפה הוא ניתן לביטוי כ-:
סכום הרבה יותר פשוט מופיע אם פונקציית סכום הריבועים מוגדרת כמספר הדרכים לרשום את n כסכום של שני ריבועים:
אף על פי שהבעיה המקורית עוסקת במניית נקודות הסריג שבתוך מעגל, טבעי להכליל את הבעיה לשאר חתכי החרוט ועקומים נוספים.
בעיית המחלקים של דיריכלה היא למעשה הבעיה השקולה לבעיה הזו אלא שהמעגל מוחלף בהיפרבולה ישרה.
ניתן גם להכליל את הבעיה משני ממדים לממדים גבוהים יותר, ולשאול מהי כמות נקודות הסריג שבתוך כדור או אובייקטים אחרים.
הכללה אחרת היא לנסות ולמצוא את מספר הזוגות המספרים הזרים m ו-n כך ש- :
בעיה זו נקראת בעיית המעגל הפרימיטיבית ומכיוון שהיא עוסקת במציאת הפתרונות הפרימיטיביים בלבד לבעיה המקורית.
אם מספר הזוגות הנ"ל יסומן
(V(r אזי הערכים של (V(r עבור הערכים הטבעיים הראשונים של r הם:
באמצעות אותם הרעיונות כמו אלו שבבעיית המעגל של גאוס ובאמצעות העובדה שההסתברות ששני מספרים טבעיים יהיו זרים היא , ניתן להסיק כי:
כמו בבעיית המעגל הרגילה, החלק הבעייתי בבעיית המעגל הפרימיטיבית הוא הורדת האקספוננט שבאיבר השגיאה.
נכון לעכשיו האקספוננט הידוע הכי טוב הוא 221/304 + ε אם מניחים כי השערת רימן נכונה.
אם לא מניחים את השערת רימן, החסם העליון הידוע הטוב ביותר הוא:
באמידה, הבעיה של אמידת המקסימום של התפלגות אחידה בדידה ממדגם ללא החזרה ידועה באנגלית כבעיית הטנק הגרמני (German tank problem), בשל השימוש בה בהקשר של מלחמת העולם השנייה על מנת להעריך את מספר הטנקים הגרמניים.
בעיה זו מדגימה את ההבדל בין הסקה שכיחותנית (Frequentist) לבין הסקה בייסיאנית.
במהלך מלחמת העולם השנייה נעשו מאמצים ממושכים על ידי בעלות הברית כדי לקבוע את היקף הייצור הגרמני, וניסו לפתור זאת בשתי גישות: באמצעות איסוף מודיעין בצורה קונבנציונלית ובאמצעות אמידה סטטיסטית.
במקרים רבים הניתוח הסטטיסטי עלה באיכותו על המודיעין הקונבנציונלי.
במקרים מסוימים נעשה שימוש במודיעין קונבנציונלי בצירוף ניתוח סטטיסטי, כמו במקרה של הערכת ייצור טנקי הפנתר לפני הפלישה לנורמנדי.
הפיקוד של בעלות הברית סבר כי טנקי פנצר סימן 5 (פנתר) שנצפו באיטליה, שלהם מהירות גבוהה ותותחי 75 מ"מ/L70, הם טנקים כבדים נדירים במיוחד, ויהיו רק במספר קטן בצפון צרפת, באופן דומה לטנקי הטיגר I שנצפו בתוניסיה.
צבא ארצות הברית היה משוכנע כי טנקי שרמן ימשיכו לתפקד היטב, כפי שתפקדו נגד טנקי פנצר סימן 3 ופנצר סימן 4 בצפון אפריקה ובסיציליה.
זמן קצר לפני הפלישה לנורמנדי הגיעו שמועות על כך שהגרמנים עושים שימוש במספר גדול של טנקים מסוג פנצר סימן 5. כדי לברר את נכונות השמועות, ניסו בעלות הברית להעריך את מספר הטנקים שיוצרו.
הם ביססו את הערכותיהם על המספרים הסידוריים של טנקים שנתפסו או נהרסו.
המספרים העיקריים ששימשו לניתוח זה היו מספרים סידוריים של תיבות ההילוכים, מאחר שאלו פוצחו על ידי בעלות הברית.
מספרי השלדה והמנוע שימשו אף הם לניתוח, אך השימוש בהם היה מסובך יותר.
מידע מרכיבים נוספים שימש לביסוס נוסף של הניתוח.
ניתוח דומה נעשה גם על פי מספרים סידוריים של גלגלי מרכוב, שלהם ניתנו מספרים ברצף (1, 2, ...N).
ניתוח גלגלי הטנקים הניב ההערכה של מספר סוגי הגלגלים שהיו בשימוש.
בדיקות שנעשו יחד עם מומחים בריטיים לייצור גלגלים העריכו את מספר הגלגלים שניתן היה לייצר מסוגים אלו, וכך את מספר הטנקים המיוצרים מדי חודש.
ניתוח של גלגלים משני טנקים (בכל אחד מהם 32 גלגלים) הוביל להערכה של 270 טנקים שיוצרו בפברואר 1944.
ממסמכים גרמניים שנתפסו לאחר המלחמה התברר כי מספר הטנקים שיוצרו בפברואר 1944 היה 276 טנקים.
הניתוח הסטטיסטי התברר כמוצלח יותר מהערכות המודיעין הקונבנציונליות, ו"בעיית הטנק הגרמני" הפך לשם שגור לתיאור בעיות מסוג זה.
השימוש במספרים סידוריים ובניתוחים סטטיסטים לא היה מוגבל רק להערכת מספר הטנקים, ושימש את בעלות הברית גם להערכת הייצור הגרמני באופן כללי, ובפרט מספר המפעלים וחשיבותם, אורך שרשרת האספקה (הזמן מהייצור ועד הכנסה לשימוש), שינויים בייצור ושימוש במשאבים כדוגמת גומי.
על פי הערכות המודיעין הקונבנציונלי של בעלות הברית, ייצרו הגרמנים בסביבות 1,400 טנקים מדי חודש בין יוני 1940 לספטמבר 1942. אבל תוך שימוש בניתוח הסטטיסטי שיוצג להלן, הוערך מספר הטנקים שיוצרו ב-246 מדי חודש בלבד.
לאחר המלחמה, מסמכים עם פרטי הייצור שנתפסו ממשרדו של אלברט שפר הראו כי המספר האמיתי היה 245.
הערכות עבור מספר חודשים מוצגות להלן:
ניתוחים סטטיסטיים דומים נעשו על פי מספרים סידוריים גם בהקשר לציוד צבאי אחר במלחמת העולם השנייה, ובפרט לטילי V-2. במהלך מלחמת העולם השנייה העריך הצבא הגרמני את היקף הייצור הצבאי הסובייטי, ובמהלך מלחמת קוריאה, נעשה ניתוח של מספרים סידוריים של ציוד סובייטי.
גם ברית המועצות העריכה את ייצור הטנקים הגרמניים באופן דומה במהלך מלחמת העולם השנייה.
בשנות ה-80 מספר אמריקאים קיבלו גישה לקווי הייצור של טנקי מרכבה.
היקף הייצור סודי, אך לטנקים היו מספרים סידוריים, שאפשרו להעריך את היקף הייצור שלהם.
על מנת להגן מפני ניתוח המבוסס על מספרים סידוריים ניתן להימנע מציונם, או להעניק מספרי ייצור מוצפנים או כאלו שאינם קשורים למספרים המיוצרים בפועל.
אינטואיטיבית האומד הוא המקסימום במדגם ועוד ההפרש הממוצע בין התצפיות במדגם.
המקסימום במדגם נבחר כאומד ראשוני מאחר שהוא אומד נראות מקסימלית, והוספת ההפרש מפצה על ההטיה מטה של המקסימום במדגם לעומת המקסימום באוכלוסייה כולה.
אם m הוא המקסימום במדגם, ו-k הוא מספר הדגימות, הנוסחה תהיה:
ניתן להמחיש זאת בכך שהדוגמאות נמצאות בהפרש קבוע ביניהן בתוך הטווח, ודוגמאות נוספות נמצאות ממש מעבר לטווח של 0 ו N+1. אם מתחילם בהפרש ראשוני של בין 0 למינימום במדגם הפרש הממוצע בין הדוגמאות הוא ; ההחסרה של נעשית משום שהדוגמאות עצמן אינן נספרות בהפרש בין הדוגמאות.
הרעיון שבבסיס תיאור זה מנוסחות בצורה פורמלית באמצעות אמידת רווח מקסימלי (maximum spacing estimation).
אומד חסר הטיה בעל שונות מינימלית
עבור אמידה נקודתית (אמידת נקודה יחידה מסה"כ ), אומד חסר הטיה בעל שונות מינימלית (minimum-variance unbiased estimator; MVUE) ניתן באמצעות:
כאשר m הוא המספר הסידורי הגבוה ביותר שנצפה ו-k הוא מספר התצפיות.
כאשר מרגע שנצפה מספר סידורי מסוים, הוא לא יצפה בשנית.
כך שסטיית התקן היא בערך N/k, הגודל הממוצע (של האוכלוסייה) של ההפרש בין הדוגמאות; בהשוואה ל m/k לעיל.
ההסתברות שהמקסימום במדגם הוא m ניתנת באמצעות ; כאשר הוא המקדם הבינומי.
בהינתן גודל אוכלוסייה N וגודל מדגם k התוחלת של המקסימום במדגם היא:
מערך לא ידוע זה ניתן לבטא את N מתוחלת וגודל המדגם:
ולכן האומד הבלתי מוטה של N ניתן באמצעות החלפת התוחלת במדגם ומכאן:
על מנת להראות שזה אומד שונות מינימלית:
מראים כי המקסימום במדגם הוא סטטיסטי מספיק עבור המקסימום באוכלוסייה
שנית מראים כי הוא סטטיסט מלא
באמצעות משפט להמן-שיף (Lehmann–Scheffé) מראים כי המקסימום במדגם עם תיקון להטיה כמוצג לעיל הוא אומד שונות מינימלית
הגישה הבייסיאנית לבעיית הטנק הגרמני היא לבחון את ההסתברות של כך שמספר הטנקים של האויב N שווה ל־n, מספר הטנקים שנצפו K שווה ל־k והמספר הסידורי הגבוה ביותר שנצפה M הוא m.
לשם הקיצור נשתמש ב־ לציון .
מכללים של הסתברות מותנת מקבלים:
הנוסחה היא ההסתברות המותנית שהמספר הסידורי הגבוה ביותר שנצפה הוא כאשר ידוע שמספר הטנקים של האויב הוא ו־ טנקים נצפו:
כאשר המקדם הבינומי הוא מספר הקבוצות של דוגמאות בגודל מאוכלוסייה של .
הביטוי הוא ההסתברות שהמספר הסידורי המרבי הוא m כאשר k טנקים נצפו, אך לפני שנצפו המספרים הסידוריים.
את ניתן לכתוב מחדש במונחים של יתר הנתונים באמצעות סכימה באמצעות האפשרויות השונות של :
הביטוי מתאר את ההסתברות לכך שמספר הטנקים הכולל הוא n כאשר k טנקים נצפו אך לפני צפייה במספרים הסידוריים.
בהנחה שההתפלגות היא התפלגות אחידה (בדידה):
החסם העליון חייב להיות סופי כיוון שהפונקציה: תקבל ואינה פונקציית הסתברות.
אם אז המשתנה מוסר מהנוסחה.
עבור השכיח של ההתפלגות של מספר הטנקים של האויב הוא m.
עבור ההסתברות שמספר הטנקים שווה ל־n היא:
וההסתברות שמספר הטנקים של האויב, , הוא גדול מ־, היא:
עבור , מספר הטנקים הוא בעל ערך תוחלת סופי:
עבור , מספר הטנקים הוא בעל סטיית תקן סופית של:
הזהות הבאה של המקדם הבינומי תשמש להלן לפישוט סדרות הקשורות לבעיית הטנק הגרמני:
סכום זה אנלוגי במידת מה לאינטגרל הבאה:
נוסחאות אלו תקפות עבור .
תצפית בטנק יחיד באקראי מתוך אוכלוסייה של n טנקים, ולו מספר סידורי m בהסתברות של עבור ובהסתברות של אפס עבור .
באמצעות שימוש בסוגרי אייברסון ניתן לכתוב זאת:
זו פונקציית הסתברות מותנית של.
כאשר מתייחסים לכך כפונקציה n עבור מספר קבוע m זו פונקציית נראות:
האומד נראות מקסימלית למספר הטנקים הכולל הוא .
הנראות הכוללת היא אין סוף כזנב של הסדרה ההרמונית:
אבל, כאשר הוא מספר הרמוני:
פונקציית ההסתברות אשר תלויה בהגבלה הניתנת כידע מוקדם:
אם נצפים שני טנקים, אז ההסתברות שזה עם המספר הסידורי הגדול יותר שווה ל־m, היא
כאשר מתייחסים לכך כפונקציה של n עבור m קבוע זו פונקציית נראות:
ופונקציית ההסתברות של מספר הטנקים הכולל N כתלות בתצפית במספר הסידורי הגדול m ובצפייה בשני טנקים היא:
אך התוחלת של N היא אינסופית:
ההסתברות המותנית שהערך הגדול מבין k תצפיות של מספרים סידוריים {1,...,n}, שווה ל־m, היא:
פונקציית הנראות של n היא:
הנראות הכוללת היא סופית עבור :
פונקציית ההסתברות של מספר הטנקים הכולל N כתלות בתצפית עם הערך הגדול ביותר m מ-k תצפיות היא:
התפלגות הזנב (המשלים לפונקציית הצטברות) עבור :
נניח כי קצין מודיעין צפה בארבעה טנקים בעלי מספרים סידוריים 2, 6, 7 ו-14. נסמן את מספר הטנקים בהם צפה ב- ואת המספר הסידורי המרבי שנצפה ב-.
מספר הטנקים של האויב, שאותו נסמן ב-, אינו ידוע ואותו רוצים להעריך על פי תצפיות אלו.
הערכה למספר הטנקים של האויב על פי הגישה השכיחותית:
לעומת זאת הערכה בייסיאנית של מספר הטנקים:
ועל פי ההערכה זו נוכל לאמוד את מספר הטנקים כך:
להתפלגות זו צידוד חיובי, הקשור לכך שמספר הטנקים אינו קטן מ-14.
בעיית הטאוטוכרון (או איזוכרון) היא בעיה בפיזיקה ומתמטיקה.
מקור המילה מיוונית, ומשמעותה "אותו הזמן".
בעיית הטאוטוכרון היא הניסיון לזהות את העקומה כך שהזמן שלוקח לכל חפץ המחליק עליה (ממנוחה, ללא חיכוך, תחת שדה כבידה אחיד) להגיע לנקודה התחתונה שלה יהיה בלתי תלוי בנקודת ההתחלה שלו.
העקומה הפותרת את הבעיה היא ציקלואידה.
הזמן הלוקח לכל גוף המחליק עליה להגיע לתחתית הוא , כאשר הוא רדיוס המעגל היוצר את הציקלואידה, היא תאוצת הכובד, ו- הוא הקבוע המתמטי פאי.
בעיית הזזת הספּה היא הפשטה גאומטרית דו-ממדית של בעיה ממשית בעולם האמיתי, הנובעת מהזזת ריהוט בתוך מבנה צר.
במוקד הבעיה ניסיון לגלות את שטחהּ המקסימלי A של צורה דו-ממדית ("הספה") אותה ניתן לתמרן דרך אזור מישורי בצורת האות "L" (ה"מסדרון"), שרוחבו יחידה אחת.
חישוב הערך המדויק של A הוא בעיה פתוחה במתמטיקה.
הפרסום הרשמי הראשון של הבעיה היה בשנת 1966, על ידי המתמטיקאי האוסטרי-קנדי ליאו מוסר .
ידוע כי עוד קודם לכן היו התייחסויות בלתי-רשמיות לבעיה.
בשנת 2024 טען מתמטיקאי קוריאני בשם ג'ינאון בק, מאוניברסיטת יונסיי בקוריאה, כי הוא פתר את בעיית הזזת הספה.
הוא פרסם הוכחה באורך של מעל 100 עמודים, בה טען שהספה שתכנן גרבר היא בעלת השטח המקסימלי.
ההוכחה צפויה לעבור בחינה מעמיקה על ידי מתמטיקאים אחרים.
למרות שגודלו המדויק של השטח A לא חושב, חושבו במרוצת השנים חסמים עליונים ותחתונים לגודלו האפשרי.
לדוגמה, ניתן לראות בקלות כי , אם נבחר ספה בצורת חצי עיגול בעל רדיוס יחידה, אותה ניתן לסובב בפינת המסדרון.
המתמטיקאי הבריטי ג'ון המרסלי חישב בשנת 1968 את החסם התחתון , תוך שימוש בצורת שפופרת טלפון: שני רבעי-עיגול ברדיוס יחידה בשני קצותיו של מלבן בגודל , ממנו הוסר חצי עיגול ברדיוס .
בשנת 1992 חישב ג'וזף גרבר חסם תחתון גדול יותר, שערכו , באמצעות שינויים קלים שביצע על צורת הספה שגילה המרסלי.
מאידך, המרסלי חישב חסם עליון לשטח הספה, והוכיח כי הוא לא יכול לעלות על .
יואב קלוס ודן רומיק הוכיחו ביוני 2017 כי חסם עליון לשטח הספה הוא 2.37.
בסטטיסטיקה, בעיית ההשוואות המרובות מתרחשת כאשר מבצעים מספר הסקות סטטיסטיות במקביל, או כשאומדים במקביל קבוצה של פרמטרים על בסיס נתונים שנצפו.
כשמבצעים מספר רב של בדיקות, הסיכוי להגיע למסקנה שגויה באחת מהן לפחות גדל באופן משמעותי (לעומת הסיכוי לטעות באחת מסוימת מהן).
למשל, אמידה של רווחי סמך רבים מגדילה את הסיכוי שאחד מהם לא יכיל את הפרמטר שהוא נועד להכיל.
דוגמה נוספת היא ביצוע בדיקות השערות מרובות, דבר הגורם לכך שהסיכוי לכך שלפחות באחת מהן השערת האפס תידחה למרות היותה נכונה (מה שידוע כטעות מסוג I), גדל באופן משמעותי.
לאורך השנים פותחו מספר טכניקות המאפשרות להתמודד עם בעיה זו, ומאפשרות להגיע גם במקרים של השוואות מרובות לאותה רמת מובהקות (הסיכוי לטעות מסוג I) כמו של השוואה יחידה (שבה מקובלת לרוב רמת מובהקות של 5% או של 1%).
שיטות אלו בדרך כלל דורשות רמת מובהקות גבוהה יותר עבור בדיקה יחידה, על מנת לפצות על ריבוי הבדיקות שגורמות לירידה ברמת המובהקות.
העניין בבעיית ההשוואות המרובות החל בשנות ה-50 של המאה ה-20 עם עבודותיהם של ג'ון טוקי ושל הנרי שֶפֶה בתחום.
במהלך השנים פותחו שיטות וטכניקות חדשות להתמודדות עם הבעיה: טכניקה הקרויה "Closed testing procedure" פורסמה בשנת 1976, שיטת הולם-בונפרוני בשנת 1979, ובמהלך שנות ה-80 מספר שיטות נוספות.
בשנת 1995 פורסם לראשונה מאמר המציג את שיטת שיעור התגליות השגויות, יחד עם רעיונות חדשים נוספים בתחום.
הכנס הראשון העוסק בבעיית ההשוואות המרובות (MCP Conference) התקיים בישראל בשנת 1996. הכנסים הבאים התקיימו בברלין, גרמניה (2000), בת'סדה, מרילנד (2002), שאנגחאי, סין (2005), וינה, אוסטריה (2007), טוקיו, יפן (2009), וושינגטון די.
נניח שאנו רוצים לבדוק אם מטבע הוא הוגן (השערת האפס היא שהוא הוגן), כלומר אם הסיכוי לקבלת "עץ" שווה לסיכוי לקבלת "פלי" (סיכוי של 0.5 לכל אחד).
סיכוי של כ-2% הוא נמוך למדי, ואם הקריטריון שלנו לדחיית השערת האפס הוא p-value < 0.05, אז במצב זה נדחה את השערת האפס ונסיק שהמטבע לא הוגן.
בעיית ההשוואות המרובות מתעוררת כאשר אנו רוצים לבדוק לא את ההוגנות של מטבע בודד, אלא את ההוגנות של מטבעות רבים.
נניח למשל שהיינו בוחנים 100 מטבעות שהם באמת הוגנים, לפי שיטה זו; אמנם הסיכוי של מטבע בודד להימצא לא-הוגן הוא עדיין כ-2% בלבד, אבל הסיכוי שלפחות אחד מהם יימצא לא-הוגן (על אף שכאמור כולם הוגנים) הוא כמעט 90%!
במילים אחרות, כלל ההחלטה שלנו (להחליט שהמטבע לא הוגן אם יצאו 9 או 10 פעמים אותה תוצאה מתוך 10 הטלות) שהיה מוצלח עבור ניסוי בודד, מתברר כבעייתי עבור 100 ניסויים שכן במצב זה דווקא רוב הגדול של הסיכויים שנבצע טעות ונקבע שמטבע הוא לא-הוגן למרות היותו הוגן.