בעיית סידור הפנקייקים של גודמן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בעיית סידור הפנקייקים (באנגלית: pancake sorting problem) - היא בעיה בקומבינטוריקה מתמטיקה שהגה המתמטיקאי ג'ייקוב גודמן (Jacob E Goodman) בשנת 1975.

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

נוסח החידה כפי שהופיע בירחון האמריקאי למתמטיקה[עריכת קוד מקור | עריכה]

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

פתרון החידה[עריכת קוד מקור | עריכה]

חידה זו אמנם נשמעת פשוטה, אך עדיין לא נמצא לה פתרון כללי. ידוע שעבור n=2 המספר המקסימלי של היפוכים הוא f(2)=1. עבור n=3 זה f(3)=3 וככל שn גדל, כך נעשה יותר יותר מורכב לחשב את מספר ההיפוכים. כמו כן, ידוע כי f(17)=19,f(18)=20, f(19)=22. אך טרם ידוע מהו מספר ההיפוכים עבור n=20. במאמרם המשותף‏[1], ביל גייטס וכריסטוס פאפאדימיטריו הראו כי הטווח למספר ההיפוכים, עבור n מכפלה של 16 הוא: {17n \over 16} \le f(n) \le {(5n+5)\over 3}

סידור פנקייקים שרופים[עריכת קוד מקור | עריכה]

גייטס ופאפאדימיטריו הציגו במאמרם וריאציה נוספת של הבעיה לפיה תחתית הפנקייקים שרופה ויש לסדרם כך שהצד השרוף ישאר כלפי מטה, כלומר, על כל פנקייק לעבור מספר זוגי של היפוכים. במצב זה הטווח למספר ההיפוכים הוא {3n \over 2}-1 \le f(n) \le 2n-3

שימושים בתחומים שונים[עריכת קוד מקור | עריכה]

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


לקריאה נוספת[עריכת קוד מקור | עריכה]

מקורות[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]