פתרונות נבחרים לשיעורי הבית

תרגיל מס' 9

1.	בשק יש 100 כדורים: 25 ירוקים, 25 צהובים, 25 אדומים ו – 25 סגולים. כמה כדורים עלינו להוציא על מנת שנהיה בטוחים שבידנו 10 כדורים בצבע זהה?
             פתרון: אם יש בידנו 36 כדורים, ייתכן כי יש 9 מכל צבע. אם יש בידנו 37 כדורים, לא ייתכן 
            שבידנו לכל היותר 9 כדורים מכל צבע. זהו מקרה פרטי של עיקרון שובך היונים המוכלל.

2.	מה מספר הדרכים להושיב 14 אנשים כך ש:
א.	8 אנשים יושבים סביב שולחן עגול והיתר סביב שולחן עגול אחר?
ב.	8 אנשים יושבים סביב שולחן עגול והיתר על ספסל?
פתרון: יש  אפשרויות לחלק 14 אנשים לשתי קבוצות – האחת של 8 אנשים והשנייה של 6 אנשים. מספר האפשרויות לסדר שמונה אנשים במעגל הוא: . מספר האפשרויות לסדר שישה אנשים במעגל הוא: . מספר האפשרויות לסדר שישה אנשים בשורה הוא: . לכן הפתרון הוא:           א. .                          ב. .

3.	מבין דיירי בית משותף המונים 10 זוגות יש לבחור ועד בן 6 דיירים. כמה ועדים שונים ניתן להרכיב אם בוועד חייבים להיות לפחות אישה אחת, לפחות גבר אחד ואסור שימצאו בני זוג.
פתרון: נבחר 6 זוגות מתוך 10 זוגות שגרים בבניין – לכך יש  אפשרויות. יש  אפשרויות לבחור בנציג אחד מכל זוג, ולכן יש  אפשרויות לבחור ועד שלא כולו נשים ולא כולו גברים. לכן הפתרון הוא: .
(הערה: מי שהציע את התשובה:  שגה, שכן "פתרון" זה סופר כל מקרה יותר מפעם אחת.)

4.	כמה מספרים טבעיים קטנים ממיליון ישנם בעלי סכום ספרות:
א.	9 
פתרון: כמספר האפשרויות לזרוק 9 כדורים זהים ל – 6 תאים, כלומר .
ב.	9 לכל היותר
פתרון: כמספר האפשרויות לזרוק 9 כדורים זהים ל – 7 תאים (התא השביעי בשביל ה"שארית"), כלומר .
ג.	45
פתרון: כמספר האפשרויות לקחת 9 כדורים מ – 6 תאים שכבר מכילים 9 כדורים כל אחד, כלומר .

6. מצא פונקציה יוצרת למספר הדרכים להרכיב סכום כסף מתוך 100 שטרות של
 20 ₪, 100 שטרות של 50 ₪ ו – 100 שטרות של 100 ₪
א.	כאשר על כל שטר מוטבע המספר הסידורי שלו.
פתרון: עבור כל שטר של 20 ₪ נכפיל בפונקציה . זאת משום שבאפשרותנו לבחור בשטר, מה שמוסיף למעריך 20, או לא לבחור בו ואז המעריך לא משתנה. אותו עיקרון נכון גם עבור שאר השטרות, ולכן הפונקציה היוצרת היא: .
ב.	כאשר אין כל אפשרות להבדיל בין השטרות בני אותו סכום.
פתרון: כיון שאין הבדל בין השטרות בני אותו סכום, חשוב רק כמה שטרות מכל סוג נבחרים. עבור השטרות של 20 ₪ נכפיל בפונקציה . הפתרון שמתקבל:

הסבר פורמלי יותר: דרך נוספת לנסח את הבעיה – כמה פתרונות יש למשוואה  עבור x1, x2 ו – x3 מספרים טבעיים הקטנים או שווים למאה. זה שקול לבעייה כמה פתרונות יש למשוואה  עבור ,   ו - , כאשר הקבוצות A1, A2 ו – A3 מוגדרות: ,  ו - . זוהי הבעיה הקרויה גם "בחירות עם הגבלות וללא חשיבות לסדר" המופיעה בעמוד 279 בספר "מבוא למתמטיקה בדידה" של פרופ' אברון. הפונקציה היוצרת המתאימה לבעיה היא המכפלה של הפונקציה שיוצרת את , הפונקציה שיוצרת את  והפונקציה שיוצרת את .

7.	מצא ביטוי סגור ל:
א.	
פתרון: נחשב תחילה את הפונקציה שיוצרת את הסידרה . לשם כך נמצא את הפונקציה שיוצרת את סידרת ההפרשים של סידרה זאת, כלומר את הסידרה . את הסידרה  יוצרת הפונקציה  (ראה עמוד 272 בספר "מבוא למתמטיקה בדידה"). את הסידרה  יוצרת הפונקציה  (כלל (8) בטבלה ד.5., עמוד 271) ואת הסידרה  יוצרת הפונקציה . לפיכך, את הסידרה  יוצרת הפונקציה 
לפי כלל (7) בטבלה ד.4. (עמוד 265), את הסידרה  יוצרת הפונקציה . לכן .

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

8.	בכמה מספרים קטנים ממיליון סכום הספרות הוא לפחות 20?
פתרון: נחשב תחילה לכמה מספרים קטנים ממיליון סכום הספרות קטן שווה 19. הפונקציה היוצרת המתאימה לבעיית מציאת מספר המספרים הקטנים ממיליון עם סכום ספרות n בדיוק היא . לכן הפונקציה היוצרת המתאימה לבעיית מציאת מספר המספרים עם סכום קטן או שווה ל – n היא  (החלוקה ב – 1-x נובעת משימוש בכלל (7) בטבלה ד.4. (עמוד 265)). המקדם של x19 הוא  שכן  (ניתן להתעלם משאר המחוברים שכן הם אינם משפיעים על המקדם של x19), וכן . לפיכך התשובה לשאלה היא .