חלוקת כדורים שונים לתאים (שונים)

togi12341

New member
חלוקת כדורים שונים לתאים (שונים)

שלום,

מצורפת שאלה + פתרון שכתבתי.

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

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

תודה לעונים
 

אורי769

New member
נו טוף...

אז שניכם טועים ):

שאלה: נניח לא היה האילוץ - בכמה אופנים ניתן לחלק 25 כדורים זהים ל-40 תאים שונים?
 

אורי769

New member
תיקון קל

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

תמיד אני נופלת על הניסוח.

אם אין חשיבות לסדר , את יתר הכדורים אפשר לסדר ע"י
62!\32!23! (62 זה המונה...) ?
 

togi12341

New member
חלוקת כדורים שונים לתאים שונים ללא הגבלה

בלי האילוץ, יש לנו יותר תאים מאשר כדורים ככה שבטוח יהיו תאים ריקים.

נראה לי שצריך קודם לבחור את התאים:
zz C(40,25) zz

עכשיו כשבחרנו את התאים אנחנו רוצים לסדר את הכדורים השונים (25) בתאים שבחרנו:
אם למשל שמנו כדור אחד בתא 1 אז נשארו לנו עוד 24 כדורים לחלק
אם שמנו שני כדורים בתא 1 אז נשארו לנו עוד 23 כדורים לחלק
..
נראה לי שזה צריך להיות !25

סה"כ:
zz C(40,25) * 25! zz
 

togi12341

New member
אולי שימוש בשובך יונים ע"י בחירה של 24 תאים

אפשר אולי לבחור 24 תאים מתוך 40 ואז לחלק את 25 הכדורים ל 24 התאים שבחרנו ומשובך יונים נקבל שיש לפחות תא אחד עם יותר מכדור אחד.
(צירפתי קובץ)
 

togi12341

New member
תיקון קטן לחלוקת כדורים שונים ללא הגבלה

כתבתי
zz C(40,25) * 25! zz

אבל חשבתי על זה שנשאר לי לחלק 25 כדורים ל25 תאים ללא הגבלה ולכן זה צריך להיות: 25^25 כי בכל תא יש 25 אפשרויות.

אז התשובה הסופית שלי היא:
zz C(40,25) * 25^25 zz
 
זה כבר נראה לי סתם להסתבך וגם שגוי

אנחנו לא מחוייבים למלא 25 תאים
אנחנו רק מחוייבים שאחד מתוך ה-40 יכיל 2 כדורים לפחות
אחרי זה מסדרים 23 כדורים איך שרוצים ל40 תאים
כלומר:
יתכנו חזרות בבחירת התא ולפי מה שאני מבינה מזה שהכדורים שונים אז יש חשיבות לסדר שלהם בתוך התא ?
 

togi12341

New member
נראה לי שאין חשיבות לסדר בתוך התא

כי אם נגיד יש לי 3 תאים
ו 2 כדורים: א, ב (צבעים שונים)

אז אם אני שם בתא 1 את: א,ב
זה אותו דבר כמו שאני אשים: ב,א
 
אני כבר מבולבלת :) רשום כדורים שונים

אם בתא א' אני אשים את כדור מספר 1
זה לא כמו שאני אשים בו את כדור מספר 2
כלומר , בשני המקרים יש בתא א' כדור אחד , אבל אלו שני מקרים שונים.

ככה השאלה הייתה מנוסחת בספר?
 

togi12341

New member
כן, העתקתי אותה.

בזה את צודקת אל שני מקרים שונים אם בתא א' יש את כדור מס' 1
או כדור מס' 2.

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

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

jehenam

New member
הצעה לפתרון

פתרון:
כל האפשרויות להכניס 25 כדורים שונים לתוך 40 תאים שונים פחות האפשרויות להכניס 25 כדורים שונים ל-40 תאים שונים כאשר בכל תא יש כדור אחד לכל היותר.

להכניס 25 כדורים שונים ל-40 תאים שונים כאשר בכל תא יש כדור אחד לכל היותר: לבחור 25 תאים מתוך ה-40 ואז להכניס את הכדור הראשון לאחד מ-25 התאים, את הכדור השני לאחד מ-24 התאים הנותרים וכך הלאה.


40^25 – c(40 25)*25!
 

אורי769

New member
את התשובה הנכונה טרם הצעתם :)

חברים, אני מציע שתקחו צעד אחד אחורה ותנסו לענות על השאלה הפשוטה הבאה:

יש 25 כדורים שונים (שיסומנו באותיות הא"ב האנגלי A,...,Y) בכמה אפשרויות ניתן לסדר אותם ב-40 תאים שונים (שימוספרו 1,...,40).

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

זאת שאלה בסיסית שאם לא תדעו לענות עליה ותבינו את הפתרון אי אפשר להתקדם.
 

togi12341

New member
25^40 (ללא האילוץ) + הסבר

אז החלטתי באמת להתחיל למנות ב"אופן ידני".
3 תאים, שני כדורים: א,ב
נתחיל:

_ _ א,ב
_ ב א
ב _ א

_ א,ב _
ב א _
_ א ב

א,ב _ _
א ב _
א _ ב

סה"כ: 9 אפשרויות שזה בעצם: 2^3 , כלומר לכל אות יש 3 אפשרויות לתא.

מה שאומר שלחלק 25 כדורים שונים ל-40 תאים זה: 25^40


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

אז:
zz C(25,2) * C(40,1) * 40^23 zz

הסבר: אנחנו בוחרים 2 כדורים, בוחרים תא אחד מתוך ה-40 ששם נשים אותם.
את השאר נחלק רגיל: 23 כדורים שונים ל40 תאים.
 

אורי769

New member
יפה

הנוסחא שלך למקרה הכללי נכונה. גם ההסבר נכון.

לגבי הפתרון שלך לבעיה עם האילוץ - בא נבדוק האם לא ספרת מקרים פעמיים.

נניח שני הכדורים שבחרנו הם A,B ונניח שבחרנו לשלוח אותם לתא 1. כל שאר הכדורים הולכים לאן שרוצים. אז לדוגמא, אפשר לשלוח את כל שאר הכדורים לתא 1. עכשיו כל הכדורים מצטופפים להם בתא 1. ומה אם נבחר של C,D ונשלח אותם לתא 1 ואז נחליט שכל שאר הכדורים גם הולכים לתא 1? מה פה קורה פה? את המקרה הזה שכל הכדורים הולכים לתא 1 אתה סופר לא פעם אחת וגם לא פעמיים. אתה ספרת אותו משהו כמו 25C2 פעמים!

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

אז מה עושים?
 

togi12341

New member
משתמשים בשיטת המשלים

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

הגעתי למסקנה הזאת לאחר שלקחתי דוגמא יותר רצינית:
ניקח דוגמא:
חלוקת 3 כדורים שונים ל4 תאים ללא אילוץ: 4^3
נחלק 3 כדורים שונים ל 4 תאים כאשר יש בלפחות תא אחד יותר מכדור אחד (קיים תא אחד שיש בו לפחות שני כדורים):
מקרה 1 כאשר א,ב ביחד:
_ _ _ א,ב,ג
_ _ ג א,ב
_ ג _ א,ב
ג _ _ א,ב

_ _ א,ב,ג _
_ _ א,ב ג
_ ג א,ב _
ג _ א,ב _

_ א,ב,ג _ _
_ א,ב _ ג
_ א,ב ג _
ג א,ב _ _

א,ב,ג _ _ _
א,ב _ _ ג
א,ב _ ג _
א,ב ג _ _

עד כאן: 16 מקרים

מקרה 2 כאשר א,ג ביחד:
_ _ _ א,ב,ג (נספר פעם נוספת)
_ _ ב א,ג
_ ב_ א,ג
ב _ _ א,ג
....

_ _ א,ב,ג _ (נספר פעם נוספת)
_ _ א,ג ב
_ ב א,ג _
ב _ א,ג _


_ א,ב,ג _ _ (נספר פעם נוספת)
ב א,ג _ _
_ א,ג ב _
_ א,ג _ ב


א,ב,ג _ _ _ (נספר פעם נוספת)
א,ג ב _ _
א,ג _ ב _
א,ג _ _ ב


יש כאן 16 מקרים - 4 מקרים שספרנו בראשון לכן סה"כ: 12

מקרה 3 כאשר ב,ג ביחד:
_ _ _ ב,ג
_ _ ב,ג _
_ ב,ג _ _
ב,ג _ _ _

כמו בקודם: 12 מקרים


סך הכל: 24+ 16= 40

=====================

ניסיתי למצוא דרך להגיע ל 40 בצורה ישירה ללא הצלחה.
לכן באמת צריך כמו ש jehenam עשה - שיטת המשלים.
מקרה כללי: 3^4 (סידור 3 כדורים שונים ב 4 תאים שונים, בכל תא יש 3 אפשרויות)
המשלים: לכל היותר כדור אחד בתא והנוסחה היא: zz C(4,3)*3! zz

סה"כ:
zz 4^3 - C(4,3)*3! = 40 zz



לכן התשובה לבעיה המקורית שפרסמתי היא :
zz 40^25 – C(40 25)*25! zz



אגב, אם למישהו יש דרך נוספת לחשב את זה אני אשמח לשמוע.
 
למעלה