תלמידונת >> שיתוף תכנים אקדמים >> מתמטיקה בדידה

ive added a link there is a jpg file with the question

הוסיפי תגובה

http://www.f2h.co.il/38488021
the link for the trinom.jpg

הוסיפי תגובה

כמה תתי קבוצות בגודל K יש לקבוצה {N,....1,2} כך שכל אחת מהן מכילה את 1 או את 2?

הוסיפי תגובה

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

אז איך בכל זאת פותרים את הבעיה הזאת? מפרידים לשלושה סוגים של קבוצות בגודל K:
1. קבוצות המכילות רק את 1.
2. קבוצות המכילות רק את 2.
3. קבוצות המכילות גם את 1 וגם את 2.

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

1. צריך לבחור K איברים מתוך הקבוצה $\{1,2,...,n\}$ וביניהם את האיבר 1, אך לא את האיבר 2. זה שקול לבחירת K-1 איברים מהקבוצה $\{3,4,...,n\}$ (כי את 1 כבר בחרנו, ואת 2 אסור לבחור). גודל הקבוצה הוא n-2. לכן מספר האפשרויות השונות הוא ${n-2}\choose{k-1}$ .

2. באופן דומה.

3. שקול לבחירת K-2 איברים מהקבוצה $\{3,4,...,n\}$ , כלומר: ${n-2}\choose{k}$ .

סך הכל קיבלנו (בהנחה שלא טעיתי, כמובן):
$2\cdot{{n-2}\choose{k-1}}+{{n-2}\choose{k}}$

הוסיפי תגובה

רשת חברתית לשיתוף תכנים אקדמים

מתמטיקה בדידה
פורום

תגובות

רשת חברתית לשיתוף תכנים אקדמים

מתמטיקה בדידה פורום

תגובות

מתמטיקה בדידה
פורום