מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/תמורות/סידור איברים שונים בשורה/תרגילים

דוגמאות לפתרון בעיות

דוגמה 1

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

1. ללא הגבלות.
2. המילה חייבת להתחיל באות א'.
3. אסור למילה להתחיל באות א'.
4. כל אותיות האהו"י מופיעות בחציה הראשון של המילה, או שכולן מופיעות בחציה השני של המילה.
5. כל אותיות האהו"י חייבות להיות סמוכות זו לזו במילה.
6. אחרי אות אהו"י לא תבוא אות אהו"י אחרת.

פתרון

1. מכיוון שאין לנו הגבלות ולא צריך שהמילים תהיינה בעלות משמעות, יש לנו סידור בשורה של 6 אותיות שונות זו מזו, ולכן הפתרון הוא $\ 6!=720$.
2. אם המילה חייבת להתחיל באות א' נשים את האות במקום הראשון ונבדוק כמה סידורים אפשריים לשאר המקומות. מכיוון שכל סידור תקין, הבעיה זהה לבעיה של סידור 5 אותיות בשורה - נסדר בשורה את כל האותיות פרט לא' ואז נוסיף את א' בתחילת השורה. לכן הפתרון הוא $\ 5!=120$.
3. בצורה ישירה ניתן לפתור את התרגיל כך: למקום הראשון ניתן לבחור רק אחת מתוך 5 אותיות (כי א' פסולה) ולכן יש לנו 5 אפשרויות. כדי לסדר את שאר המקומות אנחנו צריכים לסדר בשורה את 5 האותיות שנותרו ללא מגבלות על הסידור, ולכן יש $\ 5!=120$ אפשרויות לעשות זאת. על פי עקרון הכפל נקבל כי בסה"כ יש לנו $\ 5\cdot 5!=600$ אפשרויות.
   נציג כעת פתרון עקיף: נסתמך על כך שידוע הפתרון לסעיפים הקודמים: אם יש 720 אפשרויות סידור באופן כללי, ובדיוק 120 מתוכן הן פסולות כי בהן (ורק בהן) המילה מתחילה בא', מספר האפשרויות שנותר הוא $\ 720-120=600$. כדאי מאוד לזכור שיטת פתרון זו שכן לעתים קל יותר לחשב את מספר האפשרויות של המקרה המנוגד לזה שאנחנו צריכים למצוא, ולחסר מספר אפשרויות זה ממספר האפשרויות הכולל ללא מגבלות.
4. יש לנו רק שלוש אותיות אהו"י: האותיות א', ה', ו', ולכן רק בהן עוסק התרגיל. אנחנו מבדילים בין שני ניסויים: זה שבו כל אותיות אהו"י הן בחצי הראשון וזה שבו כולן בחצי השני. על פי עקרון החיבור מספר האפשרויות הכולל הוא סכום האפשרויות בשני המקרים, ומכיוון ששני המקרים סימטריים מספיק למצוא את מספר האפשרויות במקרה אחד ולכפול ב-2.
   אם כל אותיות אהו"י הן בחצי הראשון נסדר אותן בסדר כלשהו, ואת שאר האותיות נסדר בחצי השני בסדר כלשהו. מספר הסידורים של החצי הראשון לא משפיע על מספר הסידורים של החצי השני, ולכן על פי עקרון הכפל מספר הסידורים הכולל הוא מספר הסידורים של החצי הראשון כפול מספר הסידורים של החצי השני. סידור של כל אחד מהחצאים הוא סידור של שלוש אותיות בשורה ולכן יש $\ 3!=6$ אפשרויות לסידור כל חצי. לכן בסך הכל יש $\ 6\cdot 6=36$ סידורים, ומכיוון שצריך לכפול תוצאה זו ב-2 נקבל שהתשובה הסופית היא $\ 2\cdot 36=72$.
5. אם כל אותיות האהו"י סמוכות זו לזו, נביט עליהן כעל אות בודדת, כאילו "הדבקנו" אותן זו לזו. כעת הבעיה היא סידור של ארבע אותיות: האותיות ב', ג', ד' והאות הנוספת, ה"מודבקת". יש לנו $\ 4!=24$ סידורים אפשריים כאלו.
   כעת נבדוק בכמה צורות שונות ניתן לבצע את ה"הדבקה". כל הדבקה תלויה בסידור הפנימי של שלוש אותיות האהו"י שלנו, ולכן יש $\ 3!=6$ אפשרויות שונות. לכן על פי עקרון הכפל הפתרון הוא $\ 6\cdot 24=144$.
6. בשל המגבלה שלנו יש לסדר את האותיות לסירוגין: אות אהו"י ואחריה אות שאינה אהו"י, וחוזר חלילה. נפרק את הבעיה שלנו לשני ניסויים שונים: באחד המילה מתחילה באות אהו"י ובשני היא מתחילה באות שאינה אהו"י. כמקודם, בגלל הסימטריה בין המקרים והעובדה שבהכרח אחד משניהם מתקיים מספיק למצוא את מספר האפשרויות לאחד מהם ולכפול ב-2.
   נניח שהמילה מתחילה באות אהו"י. נסדר קודם כל את אותיות האהו"י בשורה. לשם כך יש לנו $\ 3!=6$ אפשרויות. אחר כך נסדר את האותיות שאינן אהו"י בשורה, גם כן $\ 3!=6$ אפשרויות. כעת נבנה את המילה שלנו כך: נשים את אות האהו"י שבמקום הראשון ברשימה שלה, ואחריה את האות שאינה אהו"י שבמקום הראשון ברשימה שלה. אחר כך נשים את אות האהו"י שבמקום השני ברשימה שלה, וכן הלאה. נקבל מילה שבה מופיעות לסירוגין אותיות אהו"י וכאלו שאינן אהו"י.
   מכיוון שהשלב של בניית המילה משתי הרשימות מניב תוצאה אחת בלבד, מספר הפתרונות הכולל, על פי עקרון הכפל, הוא מכפלת האפשרויות ליצירת כל אחת מהרשימות הקצרות, כלומר $\ 6\cdot 6=36$. ואת התוצאה הזו כמובן נכפול ב2, ולכן התשובה תהיה 72.

דוגמה 2

נתונות הספרות 0,1,2,3,4,5. מצא כמה מספרים ניתן ליצור תוך שימוש בכולן:

1. ללא מגבלות.
2. מספרים שמתחלקים ב-5.
3. מספרים זוגיים שגדולים מ-300,000.

פתרון

1. למרות שאין מגבלות מיוחדות על המספרים, מספר ש-0 הוא הספרה השמאלית ביותר בו איננו חוקי, ולכן למקום השמאלי ביותר יש לנו בחירה של אחת מתוך 5 ספרות, ועבור שאר 5 המקומות אנחנו משתמשים בנוסחה הרגילה לסידור בשורה. נקבל $\ 5\cdot 5!=5\cdot 120=600$ מספרים אפשריים.
2. המגבלה של הסעיף הקודם נשארת, וכעת אנחנו חייבים לוודא שהמספר שאנו יוצרים יתחלק ב-5. ידוע כי מספר מתחלק ב-5 אך ורק כאשר הספרה הימנית ביותר בו היא 0 או 5. לכן נפריד בין שני המקרים הללו.
   אם בחרנו את 0 בתור הספרה הימנית ביותר, עבור שאר המקומות אנחנו יכולים לבחור מספרים בצורה חופשית ולכן זהו סידור רגיל בשורה ויש $\ 5!=120$ אפשרויות. לעומת זאת, אם בחרנו את 5 בתור הספרה הימנית ביותר צריך לוודא ש-0 לא תהיה הספרה השמאלית ביותר ולכן נפעל בצורה דומה לזו של סעיף א': נבחר אחת מארבע הספרות הנותרות (אלו שאינן 0 או 5) ונשים אותה במקום השמאלי ביותר, ואת יתר הספרות נסדר בשורה. נקבל $\ 4\cdot 4!=4\cdot 24=96$ אפשרויות.
   כעת נשתמש בעקרון החיבור (כי מספר יכול שספרתו הימנית ביותר תהיה 0 או 5, אך לא שניהם יחד) ונקבל בסך הכל $\ 120+96=216$ אפשרויות.
3. כדי שהמספר שלנו יהיה גדול מ-300,000 עלינו לבחור בתור הספרה השמאלית ביותר אחת משלוש הספרות 3,4,5. כדי שהמספר יהיה זוגי עלינו לבחור בתור הספרה הימנית ביותר אחת מהספרות 0,2,4. נפריד בין המקרים על פי הספרה השמאלית ביותר.
   אם הספרה השמאלית ביותר היא 3, יש לנו 3 אפשרויות לבחירת הספרה הימנית ביותר, ואחר כך נסדר את 4 הספרות הנותרות בשורה. נקבל $\ 3\cdot 4!=3\cdot 24=72$ אפשרויות. כאשר נבחר בתור הספרה השמאלית ביותר את 5 נקבל את אותה תוצאה בדיוק, מאותם שיקולים.
   לעומת זאת, אם נבחר את 4 בתור הספרה השמאלית ביותר לא ניתן לבחור אותו גם בתור הספרה הימנית ביותר, ולכן אנחנו חייבים לבחור אותה מתוך 2 ספרות (0,2) ולכן מספר האפשרויות הפעם יהיה $\ 2\cdot 4!=48$.
   כעת נשתמש בעקרון החיבור ונקבל שבסך הכל יש $\ 72+72+48=192$ מספרים שונים.

תיקון להערה - 300000 אינה אפשרות שכן מוגדר כי צריך להשתמש בכל הספרות , לכן אין צורך להפחית 1 מהסכום הכולל