בתשובה לעוזי ו., 19/07/02 16:38
 |
|
 |
||
|
||||
 |
ההבדל המהותי בין חלוקה הוגנת (או נטולת קנאה, מה שבשני שחקנים הוא אותו הדבר) לבין חלוקה צודקת, הוא שחלוקה הוגנת תלויה עבור כל שחקן בהעדפות שלו, והוא לא צריך להניח שום דבר על האחרים. אפשר להשיג חלוקה צודקת לשני חלקים בעזרת שופט, שמזיז את הסכין ושני הצדדים מדווחים לו באופן שוטף מה החלק שהוקצה עד-כה להערכתם; הוא יעצור את הסכין כשסכום ההערכות יהיה אחד. בלי שופט בלתי תלוי ואמין, זה לא ילך (ההתייחסות היא לדוגמת הספריה, כמובן). לחלוקה הצודקת, אגב, יש יתרון נוסף, והוא שהיא יחידה (ליתר דיוק, יש בדיוק שתי חלוקות צודקות: אחת, שאינה הוגנת, בה כל אחד מקבל פחות מחצי, והשניה, ההוגנת, בה כל אחד קיבל יותר מחצי). (הוכחה: הפונקציה h מן המלבן הקודם היא מונוטונית עולה). אני יכול להראות שתמיד קיימת חלוקה צודקת לשלושה חלקים, אבל לא ברור לי איך להפוך חלוקה כזו להוגנת (יתכן שכולם חושבים שקיבלו רק עשירית). באופן מוזר, המקרה של חלוקה לארבעה חלקים נראה הרבה יותר מסובך. האם תמיד קיימת חלוקה צודקת לארבעה חלקים? |
 |
 |
 |
|
|
|
||
|
||||
|
כדי שלא להשאיר את כל האינטרנט במתח: תמיד קיימת חלוקה צודקת. ההוכחה היא כזו. בונים מערכת של סכינים n-1 התלויות כולן בראשונה, באופן כזה שהפרוסה ה-i שווה (לדעתו של השחקן ה-i) לפרוסה הראשונה (לדעת השחקן הראשון). באופן כזה נוצרת חלוקה צודקת של חלק מהעוגה ל- n-1 שחקנים. הפרוסה הנותרת נופלת בחלקו של השחקן האחרון. בתחילת התהליך השחקן האחרון מקבל את כל העוגה, ובסופו (כאשר הסכין האחרונה מגיעה לסוף העוגה) הוא נשאר בלי כלום. לפי משפט ערך הביניים קיים זמן שבו ערך הפרוסה הנותרת לשחקן האחרון (לשיטתו) שווה לפרוסות שחילקנו, וזוהי חלוקה צודקת. |
|
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |