tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
"לבן נוסע וזוכה" - על הלבן לשחק כך שיזכה, בהנחה שהשחור משחק בצורה הטובה ביותר.
"לבן נוסע וכופה תיקו" - על הלבן לשחק כך שיכפה תיקו, בהנחה שהשחור משחק בצורה הטובה ביותר.
ניתוח רטרוגרדי - נתון מצב על הלוח ועל הפותר לגלות מה היה המצב שקדם לו.
שחזור - נתון פתרון של בעיה, על הפותר למצוא את הבעיה המקורית.
בנוסף, בבעיות שחמט נעשה לפעמים שימוש בכלי שחמט אגדתיים שהם כלים מיוחדים שלא קיימים במשחק רגיל, אך הם משמשים בווריאציות של משחק השחמט ובבעיות.
בעיות עם כלים כאלה מכונות "בעיות אגדתיות".
"כפאי" או מהלך כפוי, אלה בעיות שחמט היוצרות מצב בו כל מהלך תשובה יגרור הפסד.
"הכתרה לא צפויה", אלה בעיות שפתרונן טמון בהפיכת הרגלי המגיע לקו הסיום לכלי שאינו המלכה.
"הקרבות", אלה בעיות שניתן לפתור על ידי הקרבת כלים למען השגת המטרה הסופית.
דוגמה ל"גרימשואו"- מט בשני מסעים
ב"דו-מסעיות" (לבן נוסע וכופה מט ב-2) ישנן הזדמנויות למוטיבים מעניינים רבים, כגון:
"גרימשואו": רץ וצריח שחורים שבכל אפשרות אחד מהם נע וחוסם את האחר.
"switch-back": במסע השני, הכלי שנע חוזר למקומו הקודם ומנחית מט.
"אלבינו": במסע השני, בהתאם למסע השחור יש לרגלי הלבן 4 אפשרויות להנחית מט: מסע אחד, מסע כפול, הכאה לימין והכאה לשמאל.
בדוגמה משמאל הפתרון הוא 1. מהב1 (מאיים מהב7).
"אלומוואנדלונג" ("Allumwandlung"): מוטיב המופיע בבעיות שבהן עומדות לרשות הלבן הכתרות לארבעה כלים שונים.
"בריסטול" ("Bristol clearance"): מוטיב שבו מעורבים שני כלים שווי-צבע הנעים על קו זהה (שני צריחים, מלכה ורץ, מלכה וצריח) כאשר כלי אחד נע לאורך הקו ומאפשר לכלי השני לנוע בעקבותיו על הקו.
"גוטהרט" ("Goethart"): כלי שחור חוסם את מסלולו של כלי שחור כפות ומאפשר לכלי לבן להסיר את הכפיתה על ידי מסע המט.
המט יהיה תמיד מט סוללה.
"התעייה" ("Try"): מסע שלכאורה משיג את המטרה, אך נסתר על ידי מסע הגנה (בדרך כלל) אחד, שללבן אין עליו מענה.
האיגוד לקומפוזיציה שחמטית בישראל מארגן תחרויות פתירת בעיות וקומפוזיציה, ומוציא לאור בכל ארבעה חודשים כתב עת ששמו "וריאנטים".
מדי שנה מתקיימת אליפות עולם בפתירת בעיות שחמט, וישראל זכתה מספר פעמים במקום הראשון.
מחברי בעיות ישראלים מפורסמים: ז'אק רוטנברג, עפר קומאי, מרק ארנבורג, יוחנן אפק, אורי אבנר, שלמה זיידר, יוסי רטר, פז עינת, אהרון הירשנזון, מנחם ויצטום, עמנואל נבון, יואל אלוני, הלל אלוני, יהודה הוך, אמציה אבני, גדי קוסטף, לאוניד מקרונץ, דוד רוברט ורטהים ויפים רוחליס.
פותרי בעיות ישראלים מפורסמים: עפר קומאי, רם סופר, עומר פרידלנד, לב גליאצנשפיגל ומוטי צ'ובניק.
המתמטיקאי היהודי נועם אלקיס הוא מחבר ופותר של בעיות שחמט וזכה באליפות העולם ליחידים בפתרון בעיות שחמט בשנת 1996.
מט מסומן ב-#, מט עזר ב-H (קיצור של helpmate) ומט לדעת ב-S (קיצור של selfmate).
לידם מוסיפים את מספר המסעים.
(לדוגמה: 2# פירושו מט בשני מסעים.
3#H פירושו מט-עזר בשלושה מסעים).
רישומי התנועות לפי הכללים שבערך שחמט.
בבעיות מסוג מט ב-n מסעים רושמים את המסע הראשון, איום (אם יש) ואת כל הווריאנטים באורך מלא, מלבד מסע אחרון של שחור ושל לבן.
בבעיות מט עזר רושמים את כל המסעים בכל הפתרונות.
בבעיות מט לדעת רושמים מסע ראשון, "איום" ווריאנטים לכל אורכם, מלבד המט של השחור.
בסיומים רושמים את כל המסעים עד לניצחון ברור (מט או יתרון חומרי מכריע) או לתיקו ברור, כאשר מספיק לציין את המסעים שבהם משחק השחור בצורה הטובה ביותר (לעיתים די בציון הווריאנט העיקרי).
בעיית נתר היא מן הבעיות המרכזיות בתורת גלואה.
הבעיה הוצעה על ידי אמי נתר בשנות השלושים של המאה העשרים, והיא עדיין לא פתורה באופן כללי.
נתון שדה , וחבורת תמורות הפועלת על הקבוצה .
אפשר להרחיב את הפעולה של לפעולה על ההרחבה הטרנסצנדנטית הטהורה , כאשר פועל על המשתנים לפי הפעולה על האינדקסים , והפעולה על שדה הבסיס טריוויאלית.
השאלה היא האם שדה השבת הוא בהכרח הרחבה טרנסצנדנטית טהורה של .
במילים אחרות, האם קיימים בלתי תלויים אלגברית כך ש-.
לדוגמה, ידוע שהתשובה חיובית כאשר היא החבורה הסימטרית .
אם היא חבורת התמורות הזוגיות , התשובה חיובית כאשר , ולא ידועה כאשר .
ב-1969 הראה ריצ'רד סוואן (Richard Swan) שהתשובה לבעיית נתר שלילית מעל שדה המספרים הרציונליים, כאשר היא החבורה הציקלית מסדר 47. לחבורה זו יש אוטומורפיזם מסדר 23, וההוכחה מסתמכת על כך שחוג השלמים של השדה הציקלוטומי אינו תחום אידיאלים ראשיים.
מאוחר יותר, ב־1974 תיאר הנדריק לנסטרה קריטריון לטרנסצנדנטיות של שדה השבת כאשר חבורה אבלית, והראה שהתשובה לבעיית נתר שלילית מעל השדה הרציונלי גם עבור .
את הדוגמה הראשונה לתשובה שלילית מעל שדה סגור אלגברית מצא דייוויד סולטמן ב-1983 (עבור חבורות מסדר ).
דוגמה דומה, עם חבורה מסדר , מצא Bogomolov ב-1986.
נתר הציעה את הבעיה בניסיון לפתור בעיה אחרת, בעיית ההיפוך של תורת גלואה, השואלת אלו חבורות יכולות להיות חבורות גלואה של הרחבות של שדה המספרים הרציונליים.
אם התשובה לבעיית נתר היא חיובית עבור חבורה מסוימת מעל שדה , אז אפשר לממש חבורה זו כחבורת גלואה מעל אותו שדה.
בעילת קטינה הוא כינוי משפטי למספר עבירות העוסקות בקיום יחסי מין עם קטינים.
בחלק מהמדינות, קיום יחסי מין עם קטינים מתחת לגיל ההסכמה נחשב בכל מקרה לאונס ומכונה אונס סטטוטורי.
החוק במדינת ישראל מבחין בין כמה וכמה מצבים בהם מעורבים קטינים ביחסי מין, ובין כמה וכמה דרגות חומרה.
כן רואה החוק את העובדה כי עבירה פלילית בוצעה כנגד קטין, כנסיבה מחמירה המביאה להחמרה בעונש, או להחמרה אחרת, כגון הארכת תקופת ההתיישנות.
כן חלה חובת הדיווח על בעלי מקצועות מסוימים, כגון עובדים סוציאליים, כאשר הם מגלים כי נעברה עבירה מסוג זה כלפי קטין.
המונח "קטין" על פי החוק הישראלי בעבירות אלו הוא גמיש, ויכול להגיע בנסיבות מסוימות עד ל-21 שנים.
בסעיף 345(ג) לחוק העונשין הוגדרה "בעילה", עד אפריל 2025, כהחדרת איבר מאברי הגוף או חפץ לאיבר המין של האישה.
החוק הבחין בין מספר שלבים בהתבגרותה של האישה, ודירג את העבירות הכרוכות בבעילת קטינה (עד לגיל 21) על פי חומרתן -
בעילת קטינה מתחת לגיל 14 אסורה בכל הנסיבות, והיא קרויה אונס סטטוטורי.
ההתייחסות אליה היא בסעיף 345(א)(3) לחוק העונשין, שכותרתו "אינוס".
המדובר בחזקה לפיה קטינה מתחת לגיל 14 אינה יכולה להסכים להיבעל.
הסכמתה או אי הסכמתה של הקטינה אינה מעלה ואינה מורידה, ובכל מקרה בו תוכח בעילת קטינה מתחת לגיל 14, ייאשם הבועל באינוס, עבירה שעונשה 16 שנות מאסר.
בעילת קטינה בין גיל 14 לגיל 16 נאסרה אף היא, על פי סעיף 346 לחוק העונשין, אך כאן יש משמעות להסכמת הקטינה.
אם זו הסכימה להיבעל, הרי שזו בעילה אסורה בהסכמה, שעונשה מאסר חמש שנים.
מבחינה משפטית טכנית, זו העבירה היחידה שכונתה "בעילת קטינה".
על פי סעיף 353 לחוק העונשין, תהא זו הגנה טובה מפני אישום בעבירה זו אם הקטינה הסכימה להיבעל, אם הפרש השנים בינה ובין הבועל הוא פחות משלוש שנים, ואם הדבר נעשה במסגרת יחסי רעות וללא ניצול מרות.
קטינה שגילה למעלה מ-16, מותרת על פי החוק לקיים יחסי מין בהסכמה.
כאמור החוק עד אפריל 2025 הגן רק על קטינה מפני בעילה, ולא עסק בקטין.
סעיף 347(ג) לחוק העונשין הגדיר כמעשה סדום החדרת כל איבר או חפץ לפי הטבעת של אדם, או החדרת איבר המין לפיו.
הסעיף חל בצורה שווה על נשים ועל גברים.
חוק העונשין החיל על ביצוע מעשה סדום את המדרג הגילאי שהוא מחיל על בעילה.
באפריל 2025 תוקן החוק, והמונח "בעילה" הוחלף במונח "חדירה", שהגדרתו "החדרת איבר מאיברי הגוף או חפץ לאיבר מינה של אישה או לפי הטבעת של אדם, או החדרת איבר מין לפיו של אדם", כך שהאיסורים המתוארים לעיל חלים ביחס לבני שני המינים .
החוק אוסר על ביצוע מעשה מגונה, המוגדר כמעשה שנעשה לשם גירוי, ביזוי או סיפוק מיניים, בקטין, אף בהסכמתו, בנסיבות מסוימות.
על פי סעיף 346 לחוק העונשין, אם מעשה אונס בוצע בקטינה, שגילה פחות מ-16 שנים, הרי שזו נסיבה מחמירה שיש בה כדי להחמיר את העונש מ-16 שנים ל-20 שנים.
כך גם, בהתאמה, בנוגע למעשה סדום ומעשה מגונה, ולעבירות בתוך המשפחה.
עבירות מין בקטינים בתוך המשפחה (בנוסף לכל עבירות האונס) נושאות גם עונש מינימלי שלא יפחת מרבע העונש המקסימלי, ולא ירוצה כולו במאסר על תנאי, אלא יש צורך בתקופת מאסר בפועל.
סעיף 354 לחוק העונשין מאריך את תקופת ההתיישנות.
מניין ההתיישנות בעבירה שנעברה בקטין מתחיל, בדרך כלל, בהגיעו לגיל 18. מניין ההתיישנות בעבירת מין שנעברה בקטין על ידי קרוב משפחה או אחראי מתחיל בהגיעו לגיל 28.
כשהקטינה עברה את גיל 14 ובעילתה אינה מסווגת סטטוטורית כאונס, אז בעילתה בהסכמה אסורה על פי החוק רק במקרה בו הבועל אינו נשוי לקטינה.
מכאן שהחוק צופה מצב בו קטינה שגילה פחות מ-16 תהיה נשואה.
על פי חוק גיל הנישואין, תש"י-1950, אין לערוך נישואין או קידושין של נער או נערה שטרם מלאו להם 18 שנים.
כל המעורב בטקס מסוג זה, לרבות בני הזוג, עורך הנישואין והורי הקטינים, דינו מאסר שנתיים.
עם זאת, במקרים מיוחדים הנדונים בחוק רשאי בית המשפט לענייני משפחה להתיר נישואי קטינים.
בניגוד לכך, בעיית שלושת הגופים היא בעיה קשה באופן כללי.
למרות שנחקרה על ידי מתמטיקאים רבים, במיוחד מאז ימי אנרי פואנקרה, לא ידוע על פתרון אנליטי מלא לבעיה, למעט מקרים מיוחדים.
עבודתו הראשונה של פואנקרה בנושא נכתבה במענה לתחרות בחסות אוסקר השני, מלך שוודיה.
השופטים - גוסטה מיטג-לפלר, ויירשטראס והרמיט, התקשו בתחילה לקרוא את פתרונו של פואנקרה, אך לאחר שהלה הגיש הבהרות שארכו כמעט מאה עמודים, בחרו בו כזוכה.
מיטג-לפלר, שתמך בגישתו האינטואיטיבית של פואנקרה, חשש שבית הספר הגרמני בראשותו של קרונקר יראה בשגיאה הוכחה ניצחת לביקורת שלו כנגד עבודתו של פואנקרה, שלא הייתה קפדנית דיה לטעמו.
באופן מעשי פותרים את בעיית שלושת הגופים, ואף את הבעיה הכללית יותר של בעיית n-גופים, בעזרת שיטות נומריות.
לצורך כך, מחלקים את התנועה לפרקי זמן קצרים, ומחשבים את הכוחות הפועלים בין הגופים בכל קטע זמן.
בהינתן נקודת ההתחלה בזמן t=0, בעיית n הגופים אינה אלא פתרון של מערכת משוואות דיפרנציאליות מסדר ראשון.
ככזו, משפטי הקיום והיחידות מבטיחים פתרון אנליטי בקטע זמן , עבור T מקסימלי.
אם T סופי, זה מפני שהמערכת מגיעה בזמן T לנקודה סינגולרית.
ב-1895 חקר פול פנלבה את נקודות הסינגולריות של בעיית n הגופים, והראה שכל נקודה כזו מתקבלת מכך שהמרחק בין שניים מהגופים שואף לאפס.
תופעה כזו מתרחשת כמובן אם הגופים מתנגשים, אבל היא עשויה להופיע למשל גם אם שני גופים בורחים יחד לאינסוף והולכים ומתקרבים זה לזה.
פנלבה הוכיח שבבעיית שלושת הגופים כל נקודת סינגולריות נובעת מהתנגשות.
ב-1908 הראה von Zeipel שנקודת סינגולריות נובעת מהתנגשות אם ורק אם הגבול של אנרגיית האינרציה סופי, וכך יקרה בהכרח אם מקומותיהם של הגופים במערכת חסומים בקטע .
מאידך, von Zeipel לא הוציא מכלל אפשרות נקודות סינגולריות שבהן אנרגיית האינרציה שואפת לאינסוף.
ב-1992 מצא Zhihong Xia פתרון לבעיית חמשת הגופים, שבו מופיעה סינגולריות בזמן סופי, שלא כתוצאה מהתנגשות.
במערכת שבנה Xia יש שני זוגות של גופים קלים ושווי-משקל שמרכזם על ישר סימטריה קבוע, וגוף חמישי, כבד, הנע על אותו ישר.
הגוף הכבד מתנדנד לאורך הישר, ובכל פעם שהוא חולף בסמוך לאחד הזוגות, הוא גורם להם להתקרב, מושך אותם אחריו הרחק מן הזוג השני, ונופל בחזרה.
התנועה ההדדית מקרבת את הגופים בכל אחד מהזוגות ומאיצה את הגוף הכבד באופן שהוא בורח לאינסוף בזמן סופי.
בשנת 2006 יצא ספר מדע בדיוני של הסופר הסיני ליו צשין בשם "בעיית שלושת הגופים".
הכותרת מתייחסת לבעיית שלושת הגופים מהמכניקה, כיוון שבעיה מרכזית בספר היא הימצאותה של פלנטה במערכת בה שלוש שמשות, ובעיית שלושת הגופים מקשה על תושבי הפלנטה לחזות את האקלים, ובמיוחד מתי הוא יציב וידידותי לחיים ומתי לא; בשנת 2024 עלתה בנטפליקס סדרה בעלת אותו השם המבוססת על הספר.
כמו הספר, גם הסדרה זכתה לביקורות חיוביות ולפופולריות רבה.
בעיית שטיינר היא בעיה שהציג הגאומטרן השווייצרי יאקוב שטיינר ב-1850, בירחון המדעי של אוגוסט לאופולד קרל (August Leopold Crelle).
הבעיה בניסוחו של שטיינר (בתרגום מגרמנית לעברית):
"אם מחלקים מספר נתון כלשהו לשני חלקים, ידוע שמכפלתם תהיה הגדולה ביותר אם החלקים יהיו שווי גודל.
עיקרון זה נשמר כאשר מחלקים מספר כלשהו a ל-3, 4, 5, … n חלקים.
כיוון שהמכפלות המתקבלות במקרים השונים האלה הן שונות בגודלן, נשאלת איפוא השאלה, לכמה חלקים שווי גודל, או באופן כללי לכמה חלקים בכלל יש לחלק מספר כלשהו a, כך שמכפלתם של החלקים תהיה הגדולה ביותר מכל המכפלות, דהיינו מקסימום של כל המקסימומים?"
שטיינר שאל על "המכפלה המקסימלית של החלקים של מספר", כלומר, מהו הערך המקסימלי של המכפלה , כאשר הם חלקים של מספר קבוע, n.
לפי אי שוויון הממוצעים, הערך המקסימלי מתקבל כאשר כל החלקים שווים זה לזה, ואם קובעים שערכו של כל חלק הוא m, אז מספר החלקים הוא , וערך המכפלה הוא .
מכאן עולה כי כדי למצוא את הערך המקסימלי (עבור n נתון) יש לבחור m כך שהמספר יהיה מקסימלי.
מכאן פתרון לבעיה שקול למציאת ככה ש .
שטיינר מציין כי "קל למצוא" שהמקסימום מתקבל כאשר m שווה לבסיס הלוגריתם הטבעי (ואכן, זהו תרגיל בסיסי בחשבון אינפיניטסימלי).
במכתבו לירחון הוסיף שטיינר שלכל מספר קיים בן-זוג יחיד , שעבורו (במספרים שלמים יש למשוואה זו פתרון יחיד: ).
חלק מפרסום הבעיה בא לה בעקבות הכללתה בתוך ספרו של היינריך דרי , 100 Great Problems of Elementary Mathematics (100 בעיות גדולות במתמטיקה יסודית), אלא ששם מופיעה הבעיה בצורה מופשטת יותר, דהיינו:
מהו ערך שמביא את הפונקציה
והתשובה, כאמור לעיל, היא קבוע אוילר, ℮.
כפי שראינו הבעיה שקולה למציאת ככה ש .
נראה שעל פי ניסוח השאלה ברור שצריך להתקיים , ומכאן גם , לכן בשביל שהנגזרת תתאפס צריך להתקיים
בעיית קפלר היא בעיה פיזיקלית המבקשת למצוא את המסלול שבו נעים שני גופים, כאשר פועל עליהם רק כוח אחד - כוח הדדי שעוצמתו יורדת עם ריבוע המרחק (כוח ריבועי הפוך), דוגמת כוח הכבידה או הכוח החשמלי.
בעיה זו, שהיא מקרה פרטי של בעיית שני הגופים, היא אחת הבעיות החשובות בפיזיקה.
היא מופיעה למשל בתיאור התנועה של כוכב לכת יחיד סביב כוכב, או בתיאור תנועת האלקטרון והפרוטון באטום המימן לפי המודל הקלאסי.
בעיית קפלר היא בין הבעיות הבודדות במכניקה הניתנות לפתרון באופן מדויק, וזאת במגוון דרכים.
הבעיה קרויה על שם האסטרונום הגרמני יוהאנס קפלר, אשר 'גילה' את פתרון הבעיה בעזרת ניתוח תצפיות של תנועת גרמי השמים.
מאוחר יותר ניסח אייזק ניוטון את חוקי ניוטון ואת חוק המשיכה האוניברסלי, בעזרתם ניתן לקבל את החוקים שניסח קפלר באופן תאורטי מעקרונות יסודיים יותר.
ערך זה עוסק בניתוח מתמטי של בעיית קפלר במכניקה קלאסית וקבלת חוקי קפלר באופן תאורטי מתוך חוקי ניוטון.
תיאור מפורט של חוקי קפלר מופיע בערך חוקי קפלר.
ניתוח מתמטי של בעיית קפלר וקבלת חוקי קפלר מחוקי ניוטון
בעיית קפלר היא בעיה דו-גופית, המערבת שני גופים שמסתם הנמצאים במיקום .
הגופים מפעילים זה על זה כוח ריבועי הפוך, כלומר גוף אחד מפעיל על הגוף השני כוח מן הצורה , כאשר:
הוא וקטור יחידה המצביע בכיוון הווקטור המחבר בין מיקומי שני הגופים.
הוא המרחק בין שני הגופים.
הוא פרמטר התלוי באופי הכוח.
עבור כוח הכבידה (כאשר הוא קבוע הגרביטציה האוניברסלי).
אם הכוח מושך (דוגמת כוח הגרביטציה, או הכוח החשמלי האלקטרוסטטי בין מטענים בעלי סימן שונה).
אם הכוח דוחה (דוגמת הכוח החשמלי בין מטענים שווי סימן).
כיוון שמדובר בבעיה דו-גופית, מרכז המסה של שני הגופים נע במהירות קבועה, ועל ידי שימוש במערכת מרכז המסה ניתן להתעלם ממנו ולטפל רק בתנועה היחסית של גוף אחד יחסית לשני סביב מרכז המסה.
משוואת התנועה של הקואורדינטה היחסית (מיקום הגוף הראשון יחסית לשני) היא:
כאשר היא המסה המצומצמת, ונקודה עילית מסמנת גזירה לפי הזמן.
המשוואה האחרונה היא משוואת תנועה של גוף בעל מסה m הנע בהשפעת כוח מרכזי, ולפיכך:
התנועה מוגבלת למישור קבוע, וניתן לאפיין את מסלול התנועה בעזרת קואורדינטות קוטביות במישור זה.
האנרגיה והתנע הזוויתי משתמרים, וגודלם נתון על ידי:
כאשר היא האנרגיה הקינטית (של תנועה בכיוון הרדיאלי ותנועה סיבובית), ו- היא האנרגיה הפוטנציאלית.
החוק השני של קפלר גורס כי הקו המחבר בין השמש וכוכב הלכת (הווקטור ) מכסה שטחים שווים בפרקי זמן שווים.
חוק זה נובע באופן ישיר משימור התנע הזוויתי:
בפרק זמן קצר הווקטור עובר זווית [ציור 1].
השטח שכיסה הווקטור בזמן זה הוא
(שטח של גזרה ברדיוס ובזווית ).
המהירות בה הווקטור מכסה שטח היא לפיכך:
כלומר מן העובדה שהתנע הזוויתי קבוע נובע כי המהירות בה הווקטור מכסה שטחים קבועה ובפרקי זמן שווים הוא יכסה שטחים שווים.
יש לציין כי כיוון שהחוק השני של קפלר מסתמך אך ורק על שימור תנע זוויתי, הוא נכון לכל כוח מרכזי ולא ייחודי לבעיית קפלר.
מסלול התנועה - החוק הראשון של קפלר
את מסלול התנועה, , ניתן למצוא במספר דרכים.
אחת הפשוטות בהן היא שימוש במשוואת שימור האנרגיה (2).
על ידי ארגון מחדש של אברי המשוואה ניתן להפריד משתנים ולקבל:
נחליף משתנה בשני אגפי המשוואה.
כעת, ניתן לבצע אינטגרציה לשני האגפים.
באגף שמאל האינטגרציה טריביאלית, ובאגף ימין האינטגרל הוא מן הצורה:
שימוש בנוסחה זו עבור ערכי a,b,c המתאימים:
כאשר קבוע אינטגרציה, אותו ניתן לקבוע כאפס על ידי סיבוב מערכת הצירים.
כעת, ניתן לחלץ את ולקבל ממנו את :
המשוואה היא משוואה כללית של חתך קוני עם אקסצנטריות , וניתוח גאומטרי שלה נותן את צורת המסלולים האפשריים [ציור 2] כתלות באנרגיה ובתנע הזוויתי (תנאי התחלה):
צורת המסלול היפרבולה פרבולה אליפסה מעגל
אופי המסלול נקבע על פי האנרגיה.
ניתן לקבל את אופי המסלול מהתבוננות בגרף של הפוטנציאל האפקטיבי [ציורים 3,4].
הגוף יכול לנוע רק בתחום בו האנרגיה הקינטית שלו גדולה או לחלופין: .
באיור מסומן התחום בו בגוף נע עבור ערכים שונים של האנרגיה שלו.
עבור ערכי המותרים מקיימים (הקו הכחול בציור 3).
במקרה זה המסלול חסום (שני הגופים תמיד נמצאים במרחק סופי זה מזה), ובמקרה שלנו המסלול הוא אליפטי.
אם שווה לערך המינימלי של הפוטנציאל האפקטיבי (הנקודה הסגולה בציור 3) ל- יש ערך מותר יחיד.
דבר זה מתאים למסלול מעגלי בו המרחק קבוע.
עבור , ערכי המותרים מקיימים .
במקרה זה המסלול אינו חסום (הגופים מתרחקים למרחק אינסופי זה מזה).
במקרה שלנו, המסלול יהיה פרבולי אם (הקו הירוק בציור 3) והיפרבולי אם (הקו האדום בציור 3 או 4).
אם בין שני הגופים פועל כוח דחייה (דוגמת הכוח החשמלי בין שני מטענים שווי סימן) ניתן לקבל רק מסלולים היפרבוליים.
עבור כוח משיכה ניתן לקבל את כל סוגי המסלול כתלות באנרגיה.
בפרט, ניתן לקבל מצב קשור, בו הגופים סמוכים זה לזה ולא מתרחקים למרחק אינסופי, עבור כוח מושך.
התנע הזוויתי משפיע על הצורה המדויקת של המסלול.
כך לדוגמה, הפריהליון (המרחק המינימלי בין שני הגופים) הוא:
התנע הזוויתי מונע מן הגופים להתקרב למרחק אפס זה מזה (ה"כוח הצנטריפוגלי" דוחה את הגופים) ויחד עם האנרגיה קובע את המרחק המינימלי האפשרי.
המרחק הנ"ל הוא המרחק בין מרכזי המסה של שני הגופים.
כך לדוגמה אסטרואיד הנע בסמוך לשמש יתנגש בה אם המתאים למסלולו קטן מרדיוס השמש.
כמו כן אם התנע הזוויתי שווה לאפס, הפתרון שתואר בסעיף הקודם אינו תקף, והגופים יתקרבו או יתרחקו זה מזה בקו ישר.
ניתוח מפורט יותר של המקרה האליפטי יופיע בהמשך.
מסלול שני הגופים והחוק הראשון של קפלר
הפתרון שקיבלנו הוא עבור הקואורדינטה היחסית בין שני הגופים.
בעזרתו ניתן להביע את מסלול התנועה של שני הגופים במערכת מרכז המסה באופן הבא:
ומכאן שצורת מסלול תנועת כל אחד מהגופים (סביב מרכז המסה) דומה לצורת המסלול שקיבלנו.
ההבדל היחיד הוא סקלת האורך של המסלול הנקבעת על פי הגורמים התלויים ביחס בין המסות של שני הגופים.
עבור תנועת כוכבי הלכת סביב השמש, כיוון שמסת השמש גדולה בהרבה ממסת כוכבי הלכת, , מתקיים עבור השמש ועבור כוכב הלכת .
כלומר, השמש כמעט ואינה נעה, מיקומה מתלכד (בקרוב) עם מיקום מרכז המסה וכוכב הלכת מקיף אותה במסלול אליפטי.
זהו החוק הראשון של קפלר.
+ ציור 5 - הדגמה של תנועת מעגלית של שני גופים סביב מרכז המסה שלהם.
כאשר מסת הגופים שווה (מימין) רדיוס התנועה שווה.
ככל שיחס המסות בין הגופים גדל, גדל רדיוס התנועה של הגוף הקל וקטן רדיוס התנועה של הגוף הכבד.
כאמור, את מסלול התנועה עבור בעיית קפלר ניתן למצוא במגוון דרכים בנוסף לדרך שהוצגה כאן.
שיטות גאומטריות - זו הדרך בה פתר אייזק ניוטון לראשונה את הבעיה.
שימוש בווקטור לפלס-רונגה-לנץ - גודל שמור נוסף הייחודי לבעיית קפלר.
המקרה האליפטי והחוק השלישי של קפלר
מן המשוואה ניתן לקבל את מאפייני המסלול האליפטי (ציור 6):
זמן המחזור - החוק השלישי של קפלר
את זמן המחזור של המסלול ניתן לחשב בעזרת העובדה כי הווקטור מכסה את שטח האליפסה במהירות שווה (החוק השני של קפלר): .
כיוון ששטח האליפסה הוא , הזמן שייקח לווקטור להשלים הקפה ולכסות את כל שטח האליפסה יהיה:
כלומר, ריבוע זמן המחזור פרופורציוני לחזקה השלישית של מחצית הציר הראשי של האליפסה.
זהו החוק השלישי של קפלר.
יש לציין כי מקדם הפרופורציה, , תלוי במסה של שני הגופים.
עבור כוח הגרביטציה ומקדם הפרופורציה הוא .
במקרה של תנועת כוכבי הלכת סביב השמש, מסת השמש גדולה בהרבה ממסת כוכבי הלכת, , ומקדם הפרופורציה יהיה בקירוב , שווה עבור כל כוכבי הלכת.
הייחוד של בעיית קפלר לעומת בעיה דו-גופית כללית
בעיית קפלר, בניגוד לבעיה דו-גופית כללית, ניתנת לפתרון מלא באופן אנליטי ופתרונה ניתן לביטוי על ידי פונקציות אלמנטריות.
גם אופי המסלולים ייחודי ביחס לבעיה כללית, בכך שהמסלולים החסומים המתקבלים, שצורתם אליפסה, אף סגורים (מסלול ה'נסגר' על עצמו, בו הגוף חוזר על עקבותיו באופן מחזורי) עבור כל תנאי התחלה.
על פי משפט ברטראן, תכונה זו ייחודית לכוח ריבועי הפוך, , ולכוח הרמוני מן הצורה .
כל סטייה קלה של הכוח (או הפוטנציאל) מן הצורות הנ"ל, תגרום למסלול הגנרי לשנות את אופיו (ציור 7).
כך לדוגמה הכוחות שמפעילים כוכבי הלכת השונים זה על זה ואפקטים יחסותים, גורמים שהכוח הפועל על כוכבי הלכת אינו באמת כוח ריבועי הפוך.
עובדה זו גורמת לנקיפה של המסלולים האליפטיים של כוכבי הלכת.
תכונה זו של המסלולים בבעיית קפלר, קשורה קשר הדוק לגודל שמור נוסף הקיים עבור בעיה זו - וקטור לפלס-רונגה-לנץ.
וקטור זה מוגדר על ידי: , וניתן להראות שהוא מכוון לאורך הציר הראשי של האליפסה.
כיוון שהווקטור קבוע, גם כיוון הציר הראשי של האליפסה קבוע - היא אינה מבצעת נקיפה.
עובדת קיומו של גודל שמור נוסף בבעיית קפלר, מעידה על הסימטריה המיוחדת שיש לבעיה זו.
בעיה דו-גופית כללית עם כוח מרכזי כללי, אינווריאנטית תחת טרנספורמציות סיבוב של המרחב התלת הממדי - חבורת הסימטריה .
בעיית קפלר, לעומת זאת, אינווריאנטית תחת טרנספורמציות של חבורה גדולה יותר - .
בעיית שני הגופים היא בעיה פיזיקלית העוסקת בתיאור תנועתם של שני גופים המפעילים כוח כלשהו זה על גבי זה וללא כוחות חיצוניים.
בעיה זו היא אחת הבעיות המרכזיות בפיזיקה, בגלל היישומים החשובים שלה וגם מכיוון שהיא אחת הבעיות היחידות הניתנת לפתרון אנליטי (עבור כוחות מסוימים), במכניקה קלאסית, בתורת הקוונטים, ולפתרון מקורב בתורת היחסות.
דוגמאות ליישומים של הבעיה הדו-גופית הם בתיאור תנועת כוכבי לכת מסביב לשמש, בתיאור תנועת האלקטרון סביב הפרוטון באטום המימן, תנועת מולקולה דו אטומית ועוד.
דוגמאות נוספות לכך כוללות מקרים בהם התנועה אינה חסומה (הגופים מתרחקים למרחק אינסופי זה מזה), כגון אסטרואיד העובר סמוך לשמש, מוסט על ידיה, וממשיך במסלולו מבלי לחזור.
מקרים אלו נקראים התנגשויות אלסטיות, והחקר שלהם הוא הבסיס לתורת הפיזורים (scattering theory).
להתנגשויות אלסטיות שימושים רבים, החל בתנועת גופים שמימיים, המשך בתיאור תנועת כדורים בביליארד, וכלה בניסויים המנגשים חלקיקים אלמנטריים במאיצים.
יש לציין שבפועל הבעיה הדו-גופית משמשת קירוב למציאות, כיוון שמוזנחים כוחות חיצוניים (לדוגמה השפעת מאדים על תנועת כדור-הארץ סביב השמש), והמבנה הפנימי של שני הגופים (כגון גאות ושפל על פני כדור הארץ, התנגשויות פלסטיות).
הבעיה הדו-גופית במכניקה קלאסית, עבור כח הכבידה, נפתרה לראשונה בצורה אנליטית על ידי אייזק ניוטון, ואפשרה לתת הסבר תאורטי לחוקי קפלר שתיארו את תנועת הכוכבים סביב השמש.
הישג זה היווה את גולת הכותרת של המכניקה הניוטונית.
הבעיה הדו-גופית באלקטרודינמיקה, תנועת האלקטרון סביב הפרוטון באטום המימן, שיחקה תפקיד חשוב בהתפתחות תורת הקוונטים: ניתוח ספקטרום הפליטה של אטום המימן הוביל למודל האטום של בוהר, ומאוחר יותר למשוואת שרדינגר.
תורת הפיזורים שימשה את ארנסט רתרפורד להסיק את מבנה האטום, מתוך פיזורים של קרינת אלפא על אטומי זהב, ובכך הולידה את הפיזיקה הגרעינית.
מאז הניסוי של רתרפורד ניסויי התנגשויות הפכו לכלי מרכזי בפיזיקה גרעינית ובפיזיקה של חלקיקים אלמנטריים.
פיזורים משחקים תפקיד רב גם בהתפתחות האסטרופיזיקה.
בשנת 1977, הצליחה נאס"א למצוא שימוש מקורי בפיזורים: היא הצליחה לשלוח שתי חלליות, וויאג'ר 1 ווויאג'ר 2, אל כוכבי הלכת הרחוקים ביותר של מערכת השמש באמצעות פיזור של החללית מכוכב אחד לכוכב הבא אחריו בתהליך שנקרא מקלעת כבידתית.
בספר היסודות המתמטיים של פילוסופיית הטבע של אייזק ניוטון, המוקדש ברובו לפתרון הבעיה הדו-גופית, ניוטון מראה את פתרון הבעיה בעזרת פיתוחים גאומטריים מסובכים ואפילו איננו עושה שימוש בחשבון אינפינטיסמלי שאותו המציא על מנת לפתור בעיות מעין זה.
אלא שבעזרת חוקי שימור ניתן להגיע לפתרון הבעיה באופן פשוט.
הפתרון מבוסס על שני שלבים:
פירוק הבעיה לשתי בעיות חד-גופיות: תיאור תנועת מרכז המסה של שני הגופים, שהיא למעשה תנועה חופשית; ותיאור התנועה היחסית של שני הגופים.
הפירוק הזה מתאפשר בזכות חוק שימור התנע, והפיתוח המתמטי שלו מוצג בסעיף הבא.
בעת שאחד הגופים כבד הרבה יותר מהשני, כמו במקרה של תנועת כדור-הארץ סביב השמש, אזי מרכז המסה נמצא סמוך לגוף המסיבי, ולכן הגוף המסיבי כמעט ואיננו נע.
במקרה זה הבעיה מצטמצמת לבעיה של תנועת הגוף הקטן סביב הגוף הגדול.
צמצום הבעיה משלושה ממדים למימד אחד: בעזרת חוק שימור האנרגיה והתנע הזוויתי, ניתן לצמצם את הבעיה לפתרון משוואה המתארת רק את המרחק בין שני הגופים.
התנע הזוויתי הוא המכפלה הווקטורית של המיקום והתנע הקווי.
מכאן, שכיוונו של התנע הזוויתי הוא הכיוון המאונך למישור המוגדר על ידי המיקום והמהירות.
מתוך שימור התנע הזוויתי ניתן לראות מיד שתנועת החלקיק תמיד תהיה במישור המאונך לווקטור התנע הזוויתי.
שימור תנע זוויתי גם נותן הבנה אינטואיטיבית מדוע שני גופים המושכים זה את זה לא יתקרבו לגמרי אחד לשני: ככל ששני הגופים קרובים יותר אחד לשני כך מהירותם תגדל, ולכן הם לבסוף יתרחקו זה מזה.
הרדוקציה הזאת תתואר בפסקה הרביעית.
הרדוקציות הללו הן כלליות: פירוק לשתי בעיות חד-גופיות, ניתן לביצוע תמיד וצמצום לבעיה חד־ממדית ניתן לביצוע עבור כוח מרכזי.
כוח גרוויטציוני, וכן כוח קולון (הכוח החשמלי האלקטרוסטטי) בין שני גופים הם מהצורה , ובמקרה זה הבעיה נקראת בעיית קפלר.
הפתרונות של בעיה זאת הם חתכים קוניים: המסלולים החסומים הם בעלי צורה של אליפסה (כך לדוגמה נע כדור-הארץ סביב השמש) או מעגל, והמסלולים הלא-חסומים הם בעלי צורה של היפרבולה (כך לדוגמה נעים אסטרואידים החולפים בקרבת השמש) או פרבולה.
בתיאור תנועתם של גרעינים בתוך מולקולות דו אטומיות, ניתן להשתמש בעקרונות של הבעיה הדו-גופית, אלא שהכוחות בין הגרעינים הם מורכבים יותר ונגרמים מתנועתם של האלקטרונים הקושרים אותם.
במקרים אלו ניתן לקרב את הפוטנציאל בין שני הגרעינים על ידי פוטנציאל מורס (Morse Potential).
מבעיית שני הגופים לבעיה של גוף יחיד בשדה כוח
נסמן את מסת הגופים ב- ואת מיקומם ב-.
משוואות התנועה הכלליות עבור שני גופים הן:
כאשר הוא הכוח שגוף i מפעיל על גוף j, ו- הוא כוח חיצוני שפועל על גוף i.
על פי החוק השלישי של ניוטון ועבור בעיה דו-גופית מניחים שאין כוחות חיצוניים, כלומר עבור בעיה דו-גופית ניתן לכתוב:
על ידי חיבור וחיסור המשוואות הנ"ל ניתן לקבל משוואות המתארות את תנועת מרכז המסה ואת התנועה היחסית בין הגופים:
על ידי חיבור המשוואות מקבלים:
משוואה זו היא משוואת תנועה עבור מרכז המסה, אשר הקואורדינטות שלו נתונות על ידי (כאשר היא המסה הכוללת).
כלומר את המשוואה האחרונה ניתן לכתוב כ: .
על מרכז המסה לא פועלים כוחות (כיוון שאין כוחות חיצוניים) ולכן על פי החוק הראשון של ניוטון היא נעה במהירות קבועה.
משוואות התנועה של שני הגופים , ניתנות לכתיבה כ:
כאשר כאן נכתבה באופן מפורש העובדה שבשל אינווריאנטיות להזזה הכוח הפועל בין שני הגופים הוא פונקציה של בלבד ולא של או בנפרד.
נגדיר קואורדינטה יחסית , המודדת את מיקום הגוף הראשון יחסית למיקום הגוף השני.
על ידי חיסור המשוואות עבור מקבלים משוואה עבור הקואורדינטה היחסית:
נהוג להגדיר מסה מצומצמת בעזרתה ניתן לכתוב:
כלומר זו פשוט משוואת תנועה של גוף בעל מסה עליו פועל כוח .
בבעיית שני הגופים שקולה מתמטית לשתי בעיות בלתי תלויות פשוטות יותר:
תנועת מרכז המסה - כיוון שעל מרכז המסה לא פועל כל כוח, זוהי בעיה טריוויאלית.
תנועה יחסית סביב מרכז המסה - זו בעיה השקולה לבעיה של גוף יחיד הנע בהשפעת כוח נתון.
במקרים רבים הכוח הנ"ל הוא כוח מרכזי.
במקרים אלו הבעיה פשוטה יחסית.
לאחר פתרון שתי הבעיות הנ"ל, ניתן לשלבן באופן הבא על מנת לקבל את תנועת שני הגופים:
ניתן לראות שכאשר אחת המסות גדולה בהרבה מהמסה השנייה, כמו במקרה של כדור-הארץ והשמש, המסה הכבדה יותר מבצעת תנועה קטנה מאוד, בקירוב טוב היא נשארת נייחת, וכן ניתן לראות שהמסה המצומצמת כמעט שווה למסה הקטנה יותר.
האפקט של תנועת המסה הקטנה על המסה הגדולה אומנם נראה זניח, אך הוא שימש לתצפיות הראשונות של כוכבי לכת חוץ-שמשיים.
בגלל המרחק הרב אל הכוכבים הללו לא ניתן לראות אותם בצורה ישירה, אך באמצעות הסחת דופלר ניתן למדוד את מהירות הכוכב המרכזי בדיוק גדול מספיק כך שניתן לראות תנודות הנובעות מקיומו של כוכב לכת קטן במסלול מסביב לכוכב הגדול.
בהינתן גוף הנע בהשפעת שדה כוחות מרכזי במרחב (זאת אומרת שדה כוח שמפעיל בכל נקודה כוח על הגוף בכיון ראשית הצירים), ניתן להראות, באמצעות חוק שימור התנע הזוויתי, שהגוף נע במישור קבוע.
התנע הזוויתי (של גוף נקודתי ביחס לראשית) נתון על ידי הנוסחה:
- הווקטור המחבר מהראשית לגוף
מהחוק השני של ניטון נובע כי קצב השינוי של התנע הזוויתי הוא מומנט הכוח הפועל על הגוף:
לכן, אם הכוח הוא מרכזי (ז"א מקביל ל- ) אז התנע הזוויתי לא משתנה.
מאידך הווקטור תמיד מאונך לתנע הזוויתי.
לכן הגוף נמצא תמיד במשור המאונך ל- .
אם הכוח הפועל על הגוף תלוי רק במרחק בין הגוף לראשית, ניתן לפשט את הבעיה על ידי מעבר לקואורדינטות קוטביות במישור.
ניתן להביע את גודל התנע הזוויתי על ידי:
ואת האנרגיה הכוללת על ידי:
בביטוי האחרון שני האיברים הראשונים הם האנרגיה הקינטית (המתאימים לתנועה הרדיאלית והסיבובית) והשלישי הוא האנרגיה הפוטנציאלית.
כיוון שהתנע הזוויתי קבוע ניתן להתייחס אל כאל חלק מהאנרגיה הפוטנציאלית, ולהתייחס לגוף כנע במימד אחד (הקואורדינטה r) בהשפעת פוטנציאל אפקטיבי .
ניתן לראות שהפוטנציאל הנובע מהתנע הזוויתי הולך לאין-סוף כאשר r הולך ל-0 ולכן הגופים המושכים זה את זה לא יכולים להתקרב עד למרחק 0 אחד לשני.
משוואת התנועה עבור הקואורדינטה r תהיה:
באיור ישנה המחשה של הפוטנציאל עבור בעיית קפלר, שעקרונותיו נכונים לכל הבעיות בהם ישנו כוח מושך בין שני הגופים.
הקו הכחול מסמן את הפוטנציאל הצנטריפטלי שהוא תוצאה של התנע הזוויתי, והקו הירוק הוא הפוטנציאל המושך הנובע מכוח הגרביטציה.
הקו האדום הוא סה"כ הפוטנציאל האפקטיבי.
ניתן לראות שישנו מינימום של הפוטנציאל: כלומר אם הגופים נמצאים במרחק זה אחד מהשני, אזי המרחק ביניהם לא ישתנה ולכן נקבל תנועה מעגלית.
עבור האזור שליד המינימום, נקבל שתנועת הגופים תתנדנד סביב המינימום ונקבל תנועה אליפטית של הגופים זה סביב זה.
ניתן לראות גם שכאשר האנרגיה הפוטנציאלית גדולה מספיק אזי התנועה לא תהיה סגורה ונקבל תנועה היפרבולית.
בעיית שני הגופים בתורת הקוונטים
כאמור בפתיחה הבעיה הדו-גופית שיחקה תפקיד חשוב בהתפתחות תורת הקוונטים, תוך הניסיון להבין את תנועת האלקטרון סביב הפרוטון באטום המימן.
ניסויים ספקטרוסקופיים הראו שאטום המימן בולע ופולט אור רק בסדרה של אורכי גל מאוד מסוימים.
בניסיון להסביר תופעה זאת, נילס בוהר הציג מודל לאטום, לפיו האלקטרון נע בתנועה קפלריאנית קלאסית סביב הגרעין, אבל רק באותם מסלולים שעבורם התנע הזוויתי הוא כפולה שלמה של קבוע פלאנק.
אורכי הגל שבהם האטום בולע ופולט אור הם מתאימים למעברים בין המסלולים.
הרעיון הבסיסי מאחורי המודל היה שהאלקטרון מתנהג באופן דומה לגלים עומדים במיתר.
המודל של בוהר לא התקבל על כלל הקהילה המדעית מכיוון שאלקטרון הנע בתנועה מעגלית אמור לשדר קרינה ולכן לקרוס לכיוון הגרעין.
בתורת הקוונטים המקובלת היום, לפי הניסוח שלה על ידי משוואת שרדינגר (או משוואת הייזנברג), ניתן לפתור את הבעיה הדו-גופית באופן דומה לאופן שבה היא נפתרת במכניקה הקלאסית: פירוק הבעיה לשתי בעיות חד-גופיות, צמצום הבעיה למימד אחד, ולבסוף פתרון משוואת הגל במימד הנותר.
צמצום הבעיה לשתי בעיות חד-גופיות
ההמילטוניאן של בעיה דו-גופית (עם פוטנציאל מרכזי וללא התחשבות בספין) יהיה מן הצורה:
נגדיר אופרטורים חדשים המתאימים למיקום ולתנע של מרכז המסה:
האופרטורים הנ"ל מקיימים יחסי חילוף קנוניים ובעזרתם ניתן לכתוב את ההמילטוניאן כ:
הוא החלק המתאר את מרכז המסה (המתנהג כחלקיק חופשי).
הוא החלק המתאר את התנועה היחסית, הנע בהשפעת הפוטנציאל המרכזי .
האופרטורים ו- חילופיים ולכן ניתן לטפל בהם בנפרד.
בדומה למקרה הקלאסי, החלק של מרכז המסה הוא טריוויאלי.
השלב השני (המוסבר בפירוט רב יותר כאן), רדוקציה לבעיה חד־ממדית, שוב מתאפשר הודות לשימור תנע זוויתי, או ליתר דיוק מכך שהבעיה סימטרית לסיבובים.
משום כך ניתן להפריד את משוואת שרדינגר לשתי משוואות, אחת עבור המרחק בין הגרעינים, r, ואחת עבור החלק הזוויתי.
הרדוקציה מתבצעת על ידי הפרדת משתנים: כותבים את פונקציית הגל באופן ואזי משוואת שרדינגר נפרדת לשתי משוואות:
פתרון משוואה זאת הן ההרמוניות הספריות .
פתרון המשוואה הרדיאלית לגבי מערב בדרך כלל פונקציות בסל.
בעיית צביעת המסלולים היא בעיה ידועה בתורת הגרפים, העוסקת בצביעה של קשתות בגרף.
לבעיה יישומים תאורטיים בתורת האוטומטים ובדינמיקה סימבולית, ויישומים פרקטיים בדחיסת מידע, תכנון ממוחשב ובדיקת פרוטוקולים.
הבעיה הוצגה ב-1970 במאמר של רוי אדלר ובנג'י וייס
(ונוסחה במפורש ב-1977), בקשר להשערה (שהוכחה לבסוף בדרך אחרת), שהאנטרופיה הטופולוגית של מערכת דינמית בעל אופי סופי, קובעת את המערכת (עד כדי שקילות).
בעיית צביעת המסלולים נפתרה על ידי אברהם טרכטמן, פרופסור למתמטיקה מאוניברסיטת בר-אילן, ב-2007. הוא הראה כי לכל גרף רגולרי מכוון המקיים מספר תנאים (קשיר היטב ואורכי המעגלים שלו צריכים להיות זרים במשותף) קיימת צביעה של הקשתות עבורה יש מילה מסנכרנת..
מבוא: מילה מסנכרנת של אוטומט
גרף סופי מכוון שבו מכל קודקוד יוצאות k קשתות, נקרא גרף רגולרי.
אם הקשתות היוצאות מכל קודקוד מסומנות בתוויות שונות זו מזו, וקבוצת התוויות קבועה לכל הקודקודים, אז הגרף נקרא אוטומט סופי דטרמיניסטי.
ניתן לחשוב על קודקודי האוטומט כאילו הם מתארים מצבים אפשריים של מכונה או מנגנון אחר, ועל הקשתות כאילו הן מתארות הוראות ביצוע: פירושה של קשת מקודקוד x לקודקוד y הנושאת את התווית i הוא "במצב x, אם מתקבלת הוראה i, יש לעבור למצב y".
הדרישה שמכל קודקוד ייצאו קשתות בכל התוויות האפשריות מבטיחה שהאוטומט "יידע" כיצד לבצע כל הוראה, בכל מצב.
באוטומט כזה, מילה מסנכרנת היא סדרה של הוראות, שביצוען בזו אחר זו יביא תמיד לאותו קודקוד סופי, ללא תלות בקודקוד ההתחלתי.
אוטומטים דטרמיניסטיים הם מרכיב בסיסי בתכנות ובתכנון מערכות ממוחשבות.
מילה מסנכרנת מאפשרת "לאפס" את האוטומט, ובכך היא תורמת לחסינות שלו מפני תקלות.
אם "הלכנו לאיבוד" באוטומט, ואיננו יודעים באיזה קודקוד אנחנו נמצאים, ביצוע ההוראות של מילה מסנכרנת יחזיר אותנו לחוף מבטחים, או לפחות לנקודה ידועה.
בתמונה משמאל מופיע גרף מכוון בן שמונה קודקודים, שמכל אחד מהם יוצאות שתי קשתות: אדומה וכחולה (בגרף זה, לכל קודקוד גם נכנסות שתי קשתות, אבל תכונה זו אינה מהותית).
מכל נקודת התחלה, אם מבצעים את סדרת ההוראות "כחול-כחול-כחול כחול-אדום-אדום כחול-אדום-אדום", מגיעים תמיד לקודקוד המסומן בצהוב.
זוהי, אם כך, מילה מסנכרנת.
באופן דומה, ביצוע של סדרת ההוראות "כחול-כחול-אדום כחול-כחול-אדום כחול-כחול-אדום" יביא אותנו תמיד לקודקוד המסומן בירוק.
בגרף מכוון G בן n קודקודים, שבו יוצאות מכל קודקוד k קשתות, ניתן - באופן עקרוני - לצבוע את הקשתות ב- דרכים, שכל אחת מהן הופכת את G לאוטומט דטרמיניסטי.
צביעה שעבורה יש לאוטומט מילה מסנכרנת, נקראת צביעה מסנכרנת.
כדי שתהיה צביעה כזו, הגרף מוכרח לקיים שתי דרישות: הוא צריך להיות קשיר כגרף מכוון, ואורכי המעגלים שלו צריכים להיות זרים במשותף.
בעיית צביעת המסלולים שואלת - האם לכל גרף סופי רגולרי המקיים שתי דרישות אלה, קיימת צביעה מסנכרנת?
כאמור במבוא, התשובה לשאלה זו חיובית.
טרכטמן, שפתר את הבעיה, מצא גם אלגוריתם המוצא צביעה מסנכרנת בסיבוכיות
בעיית פרמי היא בעיה שנועדה ללמד שימוש באנליזה ממדית, אומדן ואת חשיבות המודעות להנחות היסוד.
באופן טיפוסי בעיות מסוג זה כוללות השערות על אודות כמויות שנראות בלתי אפשריות לחישוב במסגרת המידע המוגבל הנתון בהן.
סוג הבעיה קרוי על שם הפיזיקאי אנריקו פרמי, שנודע בזכות יכולת האומדן המדויקת שלו כמעט ללא צורך בנתונים ממשיים.
דוגמה מתועדת לכך היא האומדן שלו לגבי עוצמת הפצצה האטומית בניסוי טריניטי, על פי המרחק שעברו חתיכות דף שנפלו מידו תוך כדי הפיצוץ.
דוגמה קלאסית לבעיית פרמי, המיוחסת לפרמי עצמו, היא השאלה: כמה מכווני פסנתרים יש בשיקגו?
תשובה טיפוסית לשאלה תכלול מכפלה של מספר אומדנים שתיתן הערכה לתשובה המדויקת אם הנחות היסוד נכונות.
כ-5 מיליון תושבים גרים בשיקגו.
בממוצע, גרים 2 אנשים בכל בית.
אחד מתוך כ-20 בתים מחזיק פסנתר.
פסנתרים מכוונים בממוצע פעם בשנה.
למכוון פסנתרים לוקח כשעתיים לכוון פסנתר, כולל זמן הגעה.
מכוון פסנתרים עובד 8 שעות ביום, 5 ימים בשבוע, 50 שבועות בשנה.
על פי הנחות 1-4 נוכל לחשב כי מספר כיווני הפסנתרים בשיקגו בשנה הוא:
על פי הנחות 5-6, מכוון הפסנתרים הממוצע מבצע:
(50 שבועות/שנה) × (5 ימים/שבוע) × (8 שעות/יום) : (כיוון פסנתר אחד בכל שעתיים) = 1000 כיווני פסנתרים בשנה לכל מכוון פסנתרים.
(125,000 כיווני פסנתרים בשנה בשיקגו) : (1000 כיווני פסנתרים לשנה לכל מכוון) = 125 מכווני פסנתרים בשיקגו.
דוגמה נוספת לבעיה דמוית פרמי היא השאלה: כמה ציוויליזציות ישנן בגלקסיה?
נוסחת דרייק מנסה לתת תשובה לשאלה זו בעזרת שימוש במספר אומדנים.
השאלה מדוע לא פגשנו באותן ציוויליזצות משוערות עד כה קרויה פרדוקס פרמי.
לעיתים קרובות, מדענים מחפשים השערת פרמי לפני פניה לשיטות מתוחכמות יותר לפתרון בעיה כלשהי.
העבודה בשיטה זו מאפשרת מנגנון בקרה טוב על התוצאות: עקב הסיבוכיות הגדולה, השאיפה לפתרון מדויק עלולה להוביל לשגיאות גסות, לעומת הפשטות של חישובי פרמי המאפשרים הרבה פחות מקום לטעות.
פתרון מקדים באמצעות פרמי מונע עירוב הטיות שעלולות להיגרם תוך כדי החישוב עצמו.
אומדני פרמי שימושיים גם כאשר ניגשים לבעיה שבה בחירת שיטת הפתרון היעילה תלויה בגודל התשובה הצפוי.
לדוגמה, השערת פרמי יכולה לציין האם הלחצים הפנימיים של מבנה מתוכנן קטנים מספיק כדי שניתן יהיה לתאר אותו באמצעות אלסטיות ליניארית.
לעיתים קרובות חישובי פרמי אינם מספקים תשובה נכונה מספיק, לרוב עקב בעייתיות בהנחות המוצא.
אמנם, בעייתיות כזו עוזרת בניסיון לחפש אומדן מדויק יותר.
למשל בדוגמה של מכווני הפסנתרים אולי ננסה למצוא אומדן טוב יותר של מספר הפסנתרים המכוונים ביום או של מספר התושבים בשיקגו.
בנוסף, לעיתים אין צורך באומדן מדויק, ומספיקה השערה של סדר גודל.
באותה דוגמה, אם אדם מעוניין ליזום כנס מכווני פסנתרים בשיקגו, הוא יכול להניח קהל יעד בסדר גודל של כמה עשרות, ולכן אין צורך לשכור את האצטדיון העירוני, למשל.
בתורת המשחקים, בעיית פשיטת רגל היא סוג של משחק שיתופי, בו נדרש לחלק אובייקט או סכום כספי כלשהו בין קבוצת נושים, כאשר הדגש הוא על מצבים בהם סך החובות לנושים גדול מהסכום אותו מנסים לחלק.
הבעיה היא לחלק את הרכוש בין הנושים בצורה הוגנת כלשהי.
דוגמאות למצבים מסוג זה הן חברה שפושטת רגל ויש לחלק את נכסיה בין הנושים, או חלוקת רכושו של אדם שנפטר בין כמה יורשים.
במשנה דנים במקרה של חלוקת עזבונו של אדם בין שלוש אלמנותיו, כאשר העיזבון אינו גדול דיו כדי לכסות את הסכום שהובטח בכתובה לכל אחת מהנשים.
לאישה הראשונה מגיעים 100 דינר לפי הכתובה, לשנייה 200 ולשלישית 300. המשנה מחלקת את הבעיה לשלושה מקרים, בהם עזבונו של הבעל הוא 100, 200 או 300 ומציעה את הפתרון הבא:
בעיית פשיטת רגל נתונה על ידי:
לכל שחקן מספר ממשי אי שלילי (החוב לנושה).
מספר ממשי אי שלילי (רכושו של פושט הרגל).
מסמנים את הבעיה כ או באופן מקוצר
מגדירים וקטור תשלומים להיות וקטור ב אשר מקיים .
וקטור זה הוא הצעה כיצד לחלק את הרכוש בין הנושים.
פרט למקרה בו וקטור זה אינו יחיד.
ניתן להגדיר הצגה קואליציונית של בעיית פשיטת הרגל:
מגדירים משחק בו קבוצת השחקנים היא קבוצת הנושים והפונקציה הקואליציונית מוגדרת באופן הבא: .
כלומר כשקואליציה רוצה לקבוע מה תוכל להבטיח לעצמה היא מחשבת את המקרה הגרוע ביותר, שבו כל השחקנים שאינם ב מקבלים את חובם במלואו, אם הרכוש מאפשר זאת.
פתרון נקודתי לבעיית פשיטת רגל הוא פונקציה אשר מתאימה וקטור תשלומים יעיל (כלומר ) לכל בעיית פשיטת רגל.
מציאת הפתרון עצמו תלויה בעקרונות אותם מחשיבים להיות "הוגנים".
כל נושה מקבל את אותו אחוז מתביעתו.
זוהי הגישה הנהוגה במשפט המודרני.
בדוגמה לעיל כאשר גודל העיזבון הוא 100 החלוקה תהיה לאישה הראשונה, לשנייה ו-50 לשלישית.
חלוקה של הרכוש שווה בשווה אך לא יותר מאשר מגיע לכל נושה.
בדוגמה לעיל אם גודל העיזבון הוא 400 החלוקה תהיה 100 לאישה הראשונה, 150 לשנייה ו-150 לשלישית.
עקרון שניים אוחזין בטלית הוא כלל הלקוח מהמשנה הראשונה במסכת בבא מציעא, וקובע חלוקה שווה של הסכום השנוי במחלוקת.
הוא מוגדר לחלוקה בין שני נושים.
אם החובות לשני נושים הם ו- בהתאמה וללא הגבלת הכלליות , אז פונקציית החלוקה של הרכוש מוגדרת כך:
פתרון לבעיית פשיטת רגל עבור נושים נקרא עקבי עם כלל "שניים אוחזין בטלית" אם לכל בעיית פשיטת רגל וקטור התשלומים מקיים כי לכל שני שחקנים הווקטור הוא פתרון על פי שניים אוחזין בטלית לבעיה .
ישראל אומן ומיכאל משלר הראו כי פתרון כזה תמיד קיים, יחיד והוא מתלכד עם הגרעינון עבור המשחק הקואליציוני שהוצג קודם.
הפתרון מתאים להצעתו של רבי נתן לחלוקה בסוגיה של מי שהיה נשוי שלוש נשים.
מימוש פיזיקלי עבור n שחקנים
ניתן לחשב את הפתרון המקיים עקביות עם כלל "שניים אוחזין בטלית" בדרך פיזיקלית המבוססת על חוק הכלים השלובים.
בתרשים הבא הדרישות של הנושים מתוארות על ידי מכלים בעלי שטח בסיס של יחידה.
כאשר דרישה של מתוארת על ידי שני מכלים בגובה , האחד מונח על הקרקע והשני תלוי על התקרה.
שני מכלים אלה מחוברים בצינור חסר נפח ושני המכלים מונחים על הקרקע ואף הם מחוברים בצינורות חסרי נפח.
נסדר את המכלים מהקטן לגדול:
כדי לחשב את נזרים לתוך מערכת הצינורות מים בנפח E (בגודל רכושו של פושט הרגל) ולפי חוק הכלים השלובים גובה המים בכל המכלים ישתווה.
נסמן ב- את כמות הנוזל (על שני חלקיו) והוא יסמן את התשלום לנושה (שהוא לכל היותר ).
נקבל ש ולכן הווקטור יגדיר לנו פתרון לבעיית פשיטת הרגל.
בעיית תַּרְבּוּעַ העיגול של טרסקי היא בעיה שהציג המתמטיקאי אלפרד טרסקי בשנת 1925, ובה דרישה לפרק עיגול נתון למספר סופי של חתיכות, שמהם יורכב ריבוע ששטחו שווה לשטח העיגול.
בשנת 1990 הוכיח מיקלוש לצקוביץ שלבעיה יש פתרון.
הוכחתו עושה שימוש נרחב באקסיומת הבחירה ולכן אינה קונסטרוקטיבית.
אי אפשר לחתוך עיגול ולהרכיב מהחתיכות ריבוע, כאשר החיתוך נעשה באמצעות מספריים (כלומר לאורך עקום ז'ורדן).
החתיכות בהוכחה של לצקוביץ הן קבוצות לא מדידות.
לצקוביץ הוכיח שלהרכבה די בהזזות בלבד, ואין צורך בסיבוב של חתיכות.
במהלך ההוכחה הוכיח גם שכל מצולע ניתן לפירוק למספר סופי של חתיכות שמהן ניתן להרכיב ללא סיבובים ריבוע שווה בשטחו (אם מתירים סיבובים, ההוכחה לטענה פשוטה).
במרחב התלת-ממדי ניתן להגיע, על פי הפרדוקס של בנך-טרסקי, לפירוק של כדור למספר סופי של חתיכות כך שלאחר הזזה וסיבוב של החתיכות, ניתן יהיה להרכיב מהם שני כדורים מלאים, זהים במידותיהם לכדור המקורי.
לתוצאה זו אי אפשר להגיע במישור, עקב קיומה של מידת בנך.
בעיית תרבוע העיגול, שבה עסקו היוונים הקדמונים, היא בעיה אחרת.
בעיה זו דורשת לבנות ריבוע השווה בשטחו לעיגול נתון, באמצעות סרגל ומחוגה בלבד.
בשנת 1882 הוכיח פרדיננד לינדמן את משפט לינדמן שממנו עולה שלבעיה זו אין פתרון.
בעיית קורוש היא בעיה בתורת החוגים, העוסקת באלגברות אלגבריות נוצרות סופית.
את הבעיה העלה אלכסנדר קורוש באנלוגיה לבעיית ברנסייד מתורת החבורות, והיא שואלת האם אלגברה אלגברית נוצרת סופית היא בהכרח מממד סופי.
לשאלה זו, כלשונה, יש פתרון שלילי, אך התשובה לחלק מן הווריאציות עדיין אינה ידועה.
אלגברה קומוטטיבית הנוצרת על ידי מספר סופי של איברים אלגבריים, היא בעלת ממד סופי.
תכונה זו אינה נכונה באלגברות לא קומוטטיביות (האלגברה הנוצרת על ידי איברים המקיימים היא בעלת ממד אינסופי), ולוז הבעיה, אם כך, הוא באופן שבו האלגבריות של כל האיברים אמורה לצמצם את המימד.
אם אלגברת החבורה של חבורה היא אלגברית, אז החבורה מפותלת (ההפך אינו נכון).
במובן זה, בעיית קורוש על אלגברות חבורה חלשה מבעיית ברנסייד, העוסקת בחבורה נוצרת סופית שכל אבריה בעלי סדר סופי.
מצד שני, החבורה הנלווית של אלגברה נילית מעל שדה ממאפיין חיובי היא מפותלת.
יבגני גולוד בנה, בעזרת למת גולוד-שפרביץ', אלגברה נילית נוצרת סופית בעלת ממד אינסופי (1964).
זוהי דוגמה נגדית לבעיית קורוש, משום שכל איבר נילי הוא אלגברי.
בנייה זו פתרה את בעיית ברנסייד הכללית, משום שכאשר מממשים אותה מעל שדה סופי, מתקבלת אלגברה שחבורתה הנלווית מפותלת אך לא סופית-מקומית.
דוגמה חזקה יותר לבעיית קורוש, בעלת ממד גלפנד-קירילוב סופי, נבנתה על ידי לנגן וסמוקטונוביץ'.
מאידך, בעיית קורוש עדיין פתוחה עבור חוגים עם חילוק (וכל חוג אלגברי ללא מחלקי אפס הוא כזה).
אפילו ללא הנחת האלגבריות, לא ידועה אלגברת חילוק נוצרת סופית (כאלגברה) מממד אינסופי; בעיה זו הוצעה על ידי לטישב ואיקדה.
קפלנסקי הראה שלבעיית קורוש פתרון חיובי עבור אלגברה עם זהויות.
פתרונו הקומבינטורי של Shirshov לאותה בעיה מכסה גם אלגברות אלטרנטיביות ואלגברות ז'ורדן המקיימות זהויות.
פתרונו של זלמנוב לבעיית ברנסייד המצומצמת עובר דרך הוכחה כי אלגברת לי נילית המקיימת זהות פולינומית היא נילפוטנטית מקומית.
בעיית שני הצבאות (נקראת גם בעיית ההתקפה המתואמת או בעיית שני הגנרלים) היא ניסוי מחשבתי המציג את הבעייתיות בתקשורת על גבי ערוץ לא אמין.
הבעיה עוסקת בשני צבאות או גנרלים הצרים על עיר.
העיר חזקה מכל אחד מהצבאות בנפרד, אך לא משניהם יחד.
לכן, על מנת לנצח, על שני הצבאות לתקוף את העיר בעת ובעונה אחת.
שני הצבאות מסוגלים לתקשר באמצעות שליחים בלבד, אך אלה עשויים להיתפס על ידי שומרי העיר בדרכם לצבא האחר, והצבא ששלח אותם אינו מסוגל לדעת האם הודעתו הגיעה ליעדה או שונתה בדרך.
כלומר בעיה זו מכילה שני אתגרים עיקריים:
מהימנות המידע - שתוכן המידע שנשלח אכן הגיע בשלמותו ולא שונה בדרכו אל היעד, והגיע מהמקור הרצוי.
אישור הגעת המידע - שהמידע אכן הגיע לצבא השני.
ניתן להוכיח שאין כל שיטה אשר תאפשר לאחד הצבאות לצאת להתקפה בוודאות מוחלטת שהצבא השני יצא להתקפה בו זמנית.
הבעיה הוצגה לראשונה בשנת 1975 בצורה של שתי קבוצות גנגסטרים המנסות לתאם פעילות.
למרות שלא קיים פתרון לבעיה בצורתה המקורית, ניתן לפתור גרסה דומה עם הנחות מקלות, ובכך להציג פתרון הולם מספיק לבעיות בעולם האמיתי.
דוגמה לאחת מבעיות אלו היא תקשורת נתונים, אשר פרוטוקולים מסוימים (בדרך כלל בצורה אסינכרונית) פותרים בצורה חלקית.
כאשר משתמש ושרת מנסים לתקשר זה עם זה על גבי ערוץ לא מאובטח, המשתמש והשרת נמשלים לגנרלים המנסים לתקשר זה עם זה, בעוד שהערוץ הלא מאובטח נמשל למקום שבו נמצאת העיר.
מהימנות המידע ניתנת לפתרון במקרה זה אם נשתמש בהנחות מסוימות, דוגמה לאחת מהן היא שימוש בפרוטוקול דיפי-הלמן (ההנחה שהגנרלים החליפו מראש מפתחות ציבוריים), איתם יוכלו לתקשר באופן בטוח על גבי רשת לא מאובטחת.
כלומר, ההנחה המקלה שמבצעים בדוגמה זו היא שקיימת מוסכמה אוניברסלית על מספר שליחות ואישורי קבלה חזרה שהצבאות יבצעו בעת קבלת/שליחת מסרים (כמו כן מה לעשות במידה ולא מתקבל מסר או במקרי קצה נוספים), ובכך להשיג סיכוי טוב להגעה וקבלה של המסר, או זיהוי של תקלות בהעברתו.
אלו לא פתרונות שמבטיחים את הגעת הפרטים או נכונותם בוודאות מוחלטת, הם רק מעלים את הסיכויים להגעת המסר ולמהימנות תוכנו, מה שיביא את הצדדים המתקשרים לביטחון טוב מספיק כדי להשתמש בערוץ התקשורת.
בעיית סידור הפנקייקים היא בעיה בקומבינטוריקה, שהגה המתמטיקאי מהסיטי קולג' של ניו יורק בשנת 1975.
גודמן חשב על בעיה זו בביתו, בזמן שעסק בקיפול מגבות.
הוא התבונן בערימה המבולגנת והחליט שהוא רוצה לסדר אותה מהמגבת הגדולה לקטנה, אך לא היה לו מקום לערימה נוספת אז הוא פשוט הפך את הערימה מספר פעמים על ראשה (כל פעם הוא לקח מספר שונה של מגבות) עד שהערימה הייתה מסודרת באופן הרצוי.
גודמן שאל את עצמו מה התרחיש הגרוע ביותר?
כלומר, עבור מספר כלשהו של מגבות מה מספר ההיפוכים הרב ביותר אותו יש לבצע על מנת שהערימה תסתדר?
הוא החליט לשלוח שאלה זו לירחון האמריקאי למתמטיקה "American Mathematical Monthly" כבעיית סידור פנקייקים, ופרסם אותה בשם בדוי, "הארי דוויטר" (נשמע כמו "harried waiter" - מלצר נחפז).
לבעיה הוצעו מספר ואריינטים ויש לה השלכות על תכנון רשתות ובעיית של סידור גנום.
נוסח הבעיה כפי שהופיע בירחון האמריקאי למתמטיקה
השף במסעדה שלנו מעט מרושל.
כאשר הוא מכין פנקייקים, הם יוצאים בגדלים שונים והוא עורם אותם באקראי.
לכן, בדרכי לסועד אני מארגן אותם מחדש כך שהגדול ביותר למטה והקטן ביותר למעלה על ידי כך שאני לוקח מספר פנקייקים מראש הערימה והופך אותם.
אני חוזר על פעולה זו מספר פעמים (כל פעם עם כמות שונה של פנקייקים) עד שהערימה מסודרת בסדר המבוקש.
והשאלה היא: אם יש n פנקייקים, מהו המספר המקסימלי של היפוכים (כפונקציה של n) שאני אאלץ לבצע?
בעיה זו אמנם קלה לניסוח, אך עדיין לא נמצא לה פתרון כללי.
ידוע שעבור המספר המקסימלי של היפוכים הוא .
עבור זה וככל ש-n גדל, כך נעשה יותר ויותר מורכב לחשב את מספר ההיפוכים.
אך טרם ידוע מהו מספר ההיפוכים עבור .
הבעיה עוררה עניין רב ובתגובה הראשונה לפרסומה גרי, ג'ונסון ולין ב-1977 הראו כי .
זמן קצר לאחר מכן הראו ביל גייטס, שהיה אז סטודנט בהארוורד, והמרצה שלו כריסטוס פאפאדימיטריו כי הטווח למספר ההיפוכים, עבור n מכפלה של 16 הוא: .
התוצאה הטובה ביותר הידועה היום היא .
גייטס ופאפאדימיטריו הציגו במאמרם וריאציה נוספת של הבעיה לפיה תחתית הפנקייקים שרופה ויש לסדרם כך שהצד השרוף יישאר כלפי מטה, כלומר, על כל פנקייק לעבור מספר זוגי של היפוכים.
במצב זה הטווח למספר ההיפוכים הוא
לבעיית סידור הפנקייקים, יש שימושים בתחומים שונים.
ניתן להגדיר רשת או גרף של פנקייקים, בו כל צומת מתאים לפרמוטציה של הפנקייקים ושני צמתים קשורים אם ניתן להגיע מסידור אחד למישנהו בפעולת הפיכה יחידה.
זהו גרף רגולרי עם דרגה קטנה מ-log מספר הצמתים.
השאלה אודות הערך של f(n) שקולה לשאלה מה קוטר הגרף הזה.
לרשת זו תכונות של עמידות בנפילות צמתים והיא הוצעה כבסיס לרשת P2P.
השאלה קשורה גם לבעיות מרחק בין גנומים של מינים שונים.
למשל, הבנת מספר הפעולות הנדרשות למיון יכולה לסייע לביולוגים לדעת מה הזמן הדרוש לשינוי סדר הגנים בדנ"א, כשאורגניזמים שונים מכילים את אותם הגנים רק ברצף שונה.
בְּעֵין-דּוֹר היא בלדה עברית מאת המשורר שאול טשרניחובסקי, שנכתבה בנעוריו באודסה ב-1893 ופורסמה בחודש תשרי תרנ"ח (אוקטובר 1897).
הבלדה, אחת מכמה שהקדיש טשרניחובסקי לשאול המלך (לצד "המלך", "על הרי גלבוע", "אנשי חיל חבל" ו"על חרבות בית-שן"), נכתבה בעקבות המסופר ב, והיא מתארת את ביקורו של שאול המלך אצל בעלת האוב בעין דור ערב הקרב הגורלי בפלשתים שבו נהרג, ושיחתו שם עם רוחו של שמואל הנביא.
בבלדה, כמו בסיפור המקראי, נמצא במרכז הסיפור הדיאלוג שבין שאול לשמואל, אך המילים ששם טשרניחובסקי בפי השניים שונות מאלה שבסיפור המקראי.
זוהי אחת הבלדות הידועות ביותר בשירה העברית.
הבלדה נכתבה ב-1893, בעת שהיה טשרניחובסקי כבן 18, והיא משיריו הראשונים.
היא התפרסמה לראשונה בעיתונו של אליעזר בן-יהודה "הצבי" (ירושלים) בי"ד בתשרי תרנ"ח (10 באוקטובר 1897), ובכ"ו בתשרי (22 באוקטובר) שבה ונדפסה בעיתונו של בן-יהודה "השקפה".
הבלדה מורכבת מ-28 בתים בני שתי שורות כל אחד.
הבלדה מתחילה בשלוש נקודות, שהן הודעה לקורא שתחילתו של סיפור זה אמורה להיות מוכרת לו ממקום אחר (ספר שמואל).
ניתן לזהות בבלדה פרקים אחדים:
בתים 2-1: הגעת שאול לעין דור.
אברהם רגלסון העיר על תיאורו של שאול בפרק זה: "העטה טשרניחובסקי את שאול המלך מחלצות מעולם זר לגמרי – שיוה לו דמות אבירית-פיאודלית.
רגילים אנו לקשור את שאול עם אתונות, וכאן, כאיזה לוֹנסֵילוֹט או אַייבֶנהוֹ רוכב המלך עין-דורה על סוס קל."
בתים 10-3: המפגש של שאול עם בעלת האוב ואווירת הכשפים האופפת אותו.
אברהם רגלסון ציין: "ובעלת האוב – מכשפה שכספּירית היא."
בתים 18-11: זכרונותיו של שאול מימי עלומיו השלווים.
זכרונות אלה נמצאים בניגוד מוחלט להווה הקודר שבו נתון שאול.
בתים 26-19: המפגש של שאול עם שמואל.
חלקו של שמואל במפגש זה קטן מחלקו של שאול, בניגוד לתיאור המקראי, המקדיש מקום רב יותר לדברי שמואל.
בתים 28-27: חזרתו של שאול למחנהו.
הבית שלפני האחרון בבלדה משקף את מילותיו של הבית הראשון, ובכך סוגר מעגל ומקנה לבלדה שלמות - מההגעה לעין דור בחשכת הליל ועד לשיבה למחנה באשמורת הבוקר.
חוקר הספרות אברהם שאנן ראה בבלדות "בעין-דור" ו"הכוזר האחרון" את פסגת יצירתו הבלדית של טשרניחובסקי, בעיקר בהתייחס להגדרתה של סוגה זו במאה ה-19. לדבריו, "שאול המלך זכה לכמה בלדות...
אולם 'בעין דור' היא המושלמת בהן".
זאת, "דוקא מפני פשטנותה, מפני אפייה העממי המובהק ומפני המוזיקליות הקלה שלה, מעין זו המצויה בשירי העלילה של זמרי-עם במזרח ובמערב, על קוויה החריפים".
חוקר הספרות יונה דוד ציין כי "שיר זה שייך לסוג הספרותי של בלדת הבלהות, הנושאת עליה את תו הגורל".
היו שמצאו פגמים שונים בבלדה.
מבקר הספרות ברוך קורצווייל, אף ששיבח את שליטתו של המשורר הצעיר בטכניקה הבלדית, טען כי "בעין דור" סובלת מחולשה מהותית:
אין גמישות ואין העמקה בתפיסת דמות הנביא.
אפילו ניתוח קל זה מעמיד אותנו על חסרון האחדות האמנותית שבבלדה זו.
הרבה סיבות לחוסר-אחדות זה, ואחת מהן – כך נדמה – אי-יכולתו של טשרניחובסקי לתפוס תפיסה עיונית את הבעיה הדתית המהדהדת בנושא הבלדה.
אמנם תופס הוא את הדברים תפיסה שירית, ספונטנית, אבל כשהוא עומד להיכנס לוויכוח על משמעותה של היהדות ההיסטורית, כשהוא מנסה לברר לעצמו את פשר המתיחות בין החוזה למלך, הוא מאכזב אותנו.
שאול אמנם נראה לעינינו, אבל שמואל נשאר מעין שריד בלבד ללא חיים.
מה עצומה ההתפתחות וההעמקה בתפיסת הבלדה מצד טשרניחובסקי כשמשווים את הרבוֹנות האמנותית שב"על הרי גלבע" עם ניסיון נעוריו להנציח את דמות שאול המלך!
נחמה ליבוביץ נהגה בהרצאותיה לשים ללעג את הבלדה, שלדעתה מאריכה בדברים דווקא במקומות שהסגנון התנ"כי נוקט את הצמצום והאיפוק הנדרשים.
בלדה זו הולחנה על ידי המלחינים יוסף טל, אלי פרויד, יצחק בן צבי ואהרון חרל"פ.
בעיית תרמיל הגב היא בעיית מיטוב קומבינטורית הנחקרת בתחום מדעי המחשב.
בבעיה זו נתונה קבוצת עצמים שלכל אחד מהם משקל ומחיר, ובנוסף נתון חסם על המשקל.
המטרה היא למצוא אוסף של העצמים הנתונים שסכום משקליהם אינו עולה על החסם הנתון, ומחירו מרבי.
הבעיה נחשבת לבעיה חשובה במדעי המחשב בגלל הערך התאורטי שלה (הבעיה היא NP-שלמה), ועקב השימושים שלה בתחומים כגון הקצאת משאבים וקריפטוגרפיה.
נתונים עצמים ולכל עצם נתונים מחירו ומשקלו .
לכל עצם נסמן ב- את מספר העצמים מהחפץ שנכניס לתרמיל.
המטרה היא למקסם את הביטוי (המחיר הכולל של העצמים בתרמיל) בכפוף לאילוץ (משקלם הכולל של החפצים אינו עולה על החסם).
הגרסה הנפוצה והפשוטה ביותר היא בעיית תרמיל הגב הבינארי: בבעיה זו לכל חפץ יש עותק אחד בלבד ולכן (כלומר, אם חפץ מסוים נכנס לתרמיל אזי יש רק אחד מסוגו בתרמיל).
בבעיית תרמיל הגב החסומה, לכל עצם יש כמות ומותר להכניס לתרמיל מספר עותקים של העצם: .
בבעיית תרמיל הגב הלא חסומה, מותר לקחת מספר עותקים בלתי מוגבל מכל עצם: .
גרסת ההכרעה של בעיית תרמיל הגב היא: בהינתן עצמים עם מחירים ומשקלים , ובהינתן מחיר כולל וחסם על המשקל W יש להכריע האם קיימת בחירה של העצמים כך ש- תחת האילוץ .
הוכחה שהבעיה ב-NP מתבצעת על ידי ההבחנה שבהינתן פתרון ניתן לוודא בזמן פולינומי האם מתקיימים התנאים ו-.
הוכחה שהבעיה היא NP-קשה מתבצעת על ידי רדוקציה מבעיית החלוקה: בהינתן מופע של בעיית החלוקה נוכל להגדיר מופע של בעיית תרמיל הגב שבו לכל מתקיים וכמו כן מתקיים .
כיוון שהבעיה היא NP-שלמה, לא ידועים אלגוריתמים פולינומיים אשר מוצאים פתרון מיטבי.