בעיית סידור הפנקייקים

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

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

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

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

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

הידוע אודות הבעיה

בעיה זו אמנם קלה לניסוח, אך עדיין לא נמצא לה פתרון כללי. ידוע שעבור ${\displaystyle n=2}$ המספר המקסימלי של היפוכים הוא ${\displaystyle f(2)=1}$. עבור ${\displaystyle n=3}$ זה ${\displaystyle f(3)=3}$ וככל ש-n גדל, כך נעשה יותר ויותר מורכב לחשב את מספר ההיפוכים. כמו כן, ידוע כי ${\displaystyle f(17)=19}$, ${\displaystyle f(18)=20}$, ${\displaystyle f(19)=22}$. אך טרם ידוע מהו מספר ההיפוכים עבור ${\displaystyle n=20}$.

הבעיה עוררה עניין רב ובתגובה הראשונה לפרסומה גרי, ג'ונסון ולין ב-1977 הראו כי ${\displaystyle n+1\leq f(n)\leq 2n-6}$^[2]. זמן קצר לאחר מכן הראו ביל גייטס, שהיה אז סטודנט בהארוורד, והמרצה שלו כריסטוס פאפאדימיטריו^[3] כי הטווח למספר ההיפוכים, עבור n מכפלה של 16 הוא: ${\displaystyle {17n \over 16}\leq f(n)\leq {(5n+5) \over 3}}$.

התוצאה הטובה ביותר הידועה היום היא ${\displaystyle {\frac {15}{14}}n\leq f(n)\leq {\frac {18}{11}}n}$^[4].

סידור פנקייקים שרופים

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

שימושים בתחומים שונים

לבעיית סידור הפנקייקים, יש שימושים בתחומים שונים. ניתן להגדיר רשת או גרף של פנקייקים, בו כל צומת מתאים לפרמוטציה של הפנקייקים ושני צמתים קשורים אם ניתן להגיע מסידור אחד למישנהו בפעולת הפיכה יחידה. זהו גרף רגולרי עם דרגה קטנה מ-log מספר הצמתים. השאלה אודות הערך של f(n) שקולה לשאלה מה קוטר הגרף הזה. לרשת זו תכונות של עמידות בנפילות צמתים והיא הוצעה כבסיס לרשת P2P^[5].

השאלה קשורה גם לבעיות מרחק בין גנומים של מינים שונים^[6][7]. למשל, הבנת מספר הפעולות הנדרשות למיון יכולה לסייע לביולוגים לדעת מה הזמן הדרוש לשינוי סדר הגנים בדנ"א, כשאורגניזמים שונים מכילים את אותם הגנים רק ברצף שונה.

קישורים חיצוניים

מדיה וקבצים בנושא בעיית סידור הפנקייקים בוויקישיתוף

• בעיית סידור הפנקייקים, באתר MathWorld (באנגלית)

• William H. Gates, Christos Papadimitriou, BOUNDS FOR SORTING BY PREFIX REVERSAL, Discrete Mathematics 27, 1979
• David S. Cohen, On the problem of sorting burnt pancakes, Discrete Applied Mathematics Volume 61, Issue 2, 28 July 1995
• B. Chitturi, W. Fahle, Z. Meng, L. Morales, C.O. Shields, I.H. Sudborough,, W. Voit, An (18/11)n upper bound for sorting by prefix reversals, Theoretical Computer Science Volume 410, Issue 36, 31 August 2009
• Simon Singh, Flipping pancakes with mathematics, באתר theguardian
• David S. Cohen, Manuel Blum, On the problem of sorting burnt pancakes, Discrete Applied Mathematics Volume 61, Issue 2, 28 July 1995

הערות שוליים

1. בעיה E2569
2. Stack of Pancakes
3. William H. Gates Christos Papadimitriou, BOUNDS FOR SORTING BY PREFIX REVERSAL, Discrete Mathematics 27, 1979
4. An 18/11 n upper bound for sorting by prefix reversals
5. A Churn-Resistant P2P-SystemBased on the Pancake Graph
6. Combinatorics of Genome Rearrangements By Guillaume Fertin, Anthony Labarre, Irena Rusu, Stéphane Vialette, Eric Tannier
7. Vineet Bafna and Pavel A. Pevzner Sorting by Transpositions