קומבינטוריקה

[Click6]

קומבינטוריקה

נתונים 3 כדורים אדומים ו-4 כדורים צהובים. כמה אפשרויות יש לפזר את הכדורים בין 3 תאים, כאשר בכל תא חייב להיות לפחות כדור אחד?

מאוד מאוד יעזור פתרון מלא.

תודה מראש!

 

[אורי769]

צריך הבהרות

האם התאים הם זהים או שונים?

 

[Click6]

הבהרות

התאים זהים
3 כדורים זהים אדומים
4 כדורים זהים צהובים

 

[אורי769]

קשה לי להאמין

בעיות של חלוקת כדורים זהים לתאים זהים היא בעיה קשה גם בלי אילוצים. איכשהו נראה לי שמדובר בשאלה בנושא כדורים בתאים - כלומר כדורים זהים ותאים שונים.

האם אתה מכיר את נוסחאת כדורים בתאים? בכמה אפשרויות ניתן לפזר n כדורים ל-k תאים? התשובה q (n+k-1 choose k-1) q. יש לזה הסבר שאני מניח שראית. כעת מדובר בשתי קבוצות כדורים. אילו לא היה אילוץ, אז הפתרון היה פשוט לכפול את מספר האפשרויות לפזר את האדומים במספר האפשרויות פזר את הכחולים. משאיר לך לחשוב מה עושים עם האילוץ.

 

[Click6]

סליחה, אני מתקן שוב

ממש סליחה שאני כל פעם משנה
זאת ההבהרה הסופית
התאים -לא- זהים
3 הכדורים האדומים זהים, 4 הכדורים הצהובים זהים

 

[אורי769]

יפה

אז כבר רשמתי לך הדרכה איך פותרים

 

[Click6]

זה:

אז הפתרון היה פשוט לכפול את מספר האפשרויות לפזר את האדומים במספר האפשרויות פזר את הכחולים.

?

 

[Click6]

אם כך,

לפי מה שכתבת התשובה צריכה להיות
6 על 2
כפול
5 על 2
סה"כ 15*10 = 150

האם זה אכן נכון?

 

[אורי769]

לא בדיוק

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

האם למדת עקרון ההכלה והדחה?

 

[Click6]

יעזור מאוד שתראה את הדרך

 

[אורי769]

השאלה אם תבין

לא ציינת אם למדת את עקרון ההכלה והדחה. זה נתון חשוב.

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

בכמה אפשרויות ניתן לבחור את התא הריק?
בהנתן שבחרנו את התא הריק - בכמה אפשרויות ניתן לפזר את הכדורים לשני התאים הנותרים?
תכפיל את התשובות ותקבל מה צריך לחסר מהסך הכולל


רגע... רגע... רגע....

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

 

[Click6]

מכיר את העקרון

לא שולט בו כ"כ טוב, לכן מאוד יעזור אם תראה את הפתרון

 

[אורי769]

למעשה כבר רשמתי את הפתרון

נסמן

M - מספר האפשרויות לפזר את הכדורים ל-3 תאים בלי הגבלה
X1 - מספר האפשרויות לבחור תא ריק שיהיה ריק
Y1 - מספר האפשרויות לפזר את הכדורים לשני התאים הנותרים
X2 - מספר האפשרויות לבחור שני תאים ריקים.
Y2 - מספר האפשרויות לפזר את הכדורים בתא הנותר.

הפתרון הוא
M - X1*Y1 + X2*Y2

אתה כבר חישבת את M ונותר לך לחשב את ארבעת הערכים האחרים. אני משוכנע שאתה תעמוד במשימה. השאלה היותר חשובה היא אם אתה מבין את הפתרון.

 

[Click6]

תקן אותי אם אני טועה

M = 150
X1 = 3
Y1 = כמו הדרך שהגענו ל-150 רק שהפעם יש 2 תאים ולא 3
כלומר:
5 על 1
כפול
6 על 1
5 * 6 = 30
---------------------------------------------
X2 = 3
כי תאים 1,3 ריקים או 1,2 ריקים או 2,3 ריקים

Y2 = 1

סה"כ
qq 150 - 30*3 + 3 qq
= 63

 

[Click6]

ב Y1

צריך להיות
4 על 1
כפול
5 על 1
5 * 4 = 20
ובסוף
qq 150 - 20*3 + 3 qq
93 =

 

[אורי769]

זה הפתרון

 

[Click6]

תודה!

 

[עולל]

בהנחה שהתאים שונים זה מזה:

לכל כדור יש 3 אופציות לאיזה תא להישלח.
לכן מספר האפשרויות לחלק 3 אדומים ו 4 צהובים לשלושה תאים ללא מגבלות היא
z 3^7 z

נרצה להחסיר מכך את האפשרויות שבהן קיים תא כלשהו שאין בו כדורים כלל.

כמה אפשרויות לחלוקת הכדורים יש שבהן קיים לפחות תא אחד ריק?
(עקרון ההכלה וההדחה..)

 

[אורי769]

אתה מניח שהכדורים שונים

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

 

[Click6]

בדיוק, הבנת את הכוונה