2 שאלות אמריקאיות - תורת הקבוצות ותורת הגרפים

[nir9696]

2 שאלות אמריקאיות - תורת הקבוצות ותורת הגרפים

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

שבת שלום ותודה לעונים!

 

[אורי769]

תשובות

1. התשובה היא אכן א0. הבעיה במה שכתבת היא שהחיתוך של Ai-ים לא יכול להיות סופי. נסה לחשוב למה.
2. כאן לא צריך לדעת כלום על זיווג מושלם פרט להדגרה שלו. זאת בכלל לא שאלה על גרפים, אלא בעית מניה. ראשית, נסה להבין למה בגרף דו-צדדי מלא על n קודקודים כל צד יש n! זווגים מושלמים. אח"כ הוסף את האילוץ של הסרת צלע בודדת וחשוב איך זה משפיע על הספירה.

 

[nir9696]

תשובות

1. אני מתקשה לחשוב על טיעון שישכנע אותי שאין חיתוך סופי.
2. אם הייתי צריך לבחור תשובה הייתי בוחר ב-6!-5!, אבל אני לא מבין כ"כ את השיקול הקומבינטורי. אם זו הייתה שאלה פתוחה, הייתי בכלל חושב שהדרך למנות את הזיווגים הוא ע"י צירופים של מספר קודקודים מעל 2. למה אני טועה??

אני מצרף עוד שאלה דומה הקשורה למניית זיווגים מושלמים, שעל אף שהתשובות נתונות, הגעתי ע"י שיקולים של צירופים ל-90 (תשובה שאינה נתונה)... אשמח להבין איפה אני טועה:

 

[אורי769]

עוד תשובות

אכן q 6!-5! q זה התשובה הנכונה. נניח שנסמן את קודקודי כל צד ב-a1,a2,...a6 ו-b1,b2...b6. מספר הזיווגים המושלמים בגרף הדו-צדדי המלא הוא 6! כי זה פשוט לשאול איך לסדר את ה-bi-ים ביחס ל-ai-ים. עכשיו נניח שאנו מסירים את הצלע a6-b6. מה מספר הזווגים המושלמים כעת? אז התשובה היא שצריך לחסר את המקרים ה"רעים", כלומר את אלו שבהם a6-b6 היא חלק מהזיווג שבחרנו. תשכנע את עצמך למה יש בדיוק 5! כאלה.

לגבי השאלה שצירפת - 90 זו לא התשובה הנכונה, אבל אם אני מנחש את דרך המחשבה שלך אז אתה בכיוון הנכון. בא אני אתן לך עיצה כללית בנושא בעיות מניה. בכל פעם שאתה מציע פתרון, שאל את עצמך שתי שאלות:
1. האם ספרתי את כל המקרים?
2. האם ספרתי כל מקרה פעם אחת בדיוק?
בשאלה זו, הפתרון שלך של 90 נופל במבחן השני. כלומר, אתה סופר מקרים יותר מפעם אחת. נסה להבין למה ואיך לתקן.

 

[nir9696]

עוד תשובות

קודם כל תודה! אני חושב שהבנתי. התשובה יצאה לי 15. בדקתי מה מספר האפשרויות לבחור קשת (זיווג בין שני קודקודים) מהגרף המלא - 15 אפשרויות. לאחר מכן אני "מוריד" את שני הקודקודים שזיווגתי ואת כל הקשתות השכנות להם ונשאר עם K4. עכשיו יש לי 6 אפשרויות לבחור זיווג נוסף. משבחרתי אותו, אני שוב מוריד את שני הקודקודים שזיווגתי ואת הקשתות הסמוכות להם, ונשאר עם K2, אשר כבר מזווג את שני הקודקודים הנותרים. סה"כ עפ"י עקרון הכפל: 15X6 = 90. עכשיו עלי לגרוע מסך האפשרויות את מס' הפעמים שיוצא לי אותו זיווג מושלם אך בסדר שונה - 3!. לכן התשובה הסופית היא 90/6 = 15. אני צודק?

 

[אורי769]

אחלה