שדכניות

[עריסטו]

שדכניות

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

 

[1אברהם]

אולי

אם למשל יש רק בחור אחד בעל שיער שחור ורק 2 בלונדיניות וכולם מכירים את כולם אז ניתן לחתן את כל הבחורים עם שיער השחור ( שזה רק 1 ) אם מישהי שהוא מכיר ( אחת הבלונדיניות) אבל אי אפשר לחתן את כל הבלונדיניות עם מי שהן מכירות כי הבחור היחיד שהם מכירות תפוס על ידי אחת מהן. אז המתמתיקאי לא צודק

 

[עריסטו]

../images/Emo128.gif לא מתאים לנתוני השאלה

 

[mor48]

אם היה מדובר בפיזיקאי יתכן שהוא היה

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

 

[mor48]

ההסבר הקודם היה עילג

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

 

[ןן גיל ןן]

פיתרון דומה, מעט פורמלי יותר

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

 

[עריסטו]

../images/Emo127.gif

שימו לב שאם מספר הבחורים והבחורות אינסופי זהו משפט קנטור-ברנשטיין.