נושא חוזר בפרק הכמותי · השער לרמות הקושי הגבוהות
GMAT Combinatorics - פרמוטציות וצירופים
קומבינטוריקה היא הנושא שבו רבים נכשלים - לא מחוסר ידע בנוסחאות, אלא מחוסר תפיסה איזו נוסחה להחיל. השאלה הקריטית היא תמיד אותה שאלה: "האם הסדר חשוב?". עם תשובה ברורה לזה - רוב השאלות נפתרות במהירות.
למה Combinatorics חשובה ב-GMAT
במבחן ה-GMAT Focus Edition מופיעות 1-2 שאלות קומבינטוריקה בסימולציה, וברוב המקרים הן יושבות ברמת קושי 650-750. הן גם בסיס לחישובי הסתברות, ולכן מי ששולט בקומבינטוריקה זוכה גם בנקודות הסתברות.
הסיבה לחשיבותן: נושא זה בודק תפיסה מבנית של בעיות ספירה. תלמיד שקורא "בחר 3 מ-10" וקופץ מיד ל-C(10,3) בלי לבדוק אם הסדר חשוב - נופל לכל מלכודת בדרך.
- בסיס ל-Probability - חצי משאלות ההסתברות פותרים באמצעות צירופים במונה ובמכנה.
- נושא קל-להוראה - קשה-לטעות - הנוסחאות פשוטות, אבל הבחירה ביניהן דורשת מודלים מנטליים חדים.
- נוטה לשאלות "מילים" - תרגום הסיפור למבנה ספירתי הוא עיקר הפתרון.
תובנה אסטרטגית: בכל שאלה - לפני שאתה כותב נוסחה, ענה בקול: "הסדר משנה? כן/לא". אם כן - פרמוטציה. אם לא - צירוף. השאלה הזו תחסוך חלק ניכר מהטעויות.
הנוסחאות שאתה חייב לדעת בעל פה
1. פרמוטציה - סדר חשוב
P(n,k) = n! / (n−k)!
מספר הסידורים של k פריטים מתוך n. דוגמה: שלושה מקומות מובחנים, 10 מתמודדים → 10·9·8 = 720.
2. צירוף - סדר לא חשוב
C(n,k) = n! / [k!·(n−k)!]
מספר הקבוצות של k מתוך n. דוגמה: ועדה של 3 מ-10 = C(10,3) = 120.
3. עצרת
n! = n · (n−1) · ... · 1
סידור של n פריטים מובחנים בשורה. 5! = 120. 7! = 5040. 0! = 1 (לפי הגדרה).
4. סידור מעגלי
(n − 1)!
בסידור עגול אין "ראש" - לכן מקבעים פריט אחד ומסדרים את השאר. דוגמה: 6 אנשים סביב שולחן עגול = 5! = 120.
5. פריטים זהים
n! / (p! · q! · ...)
אם יש n פריטים אבל p מהם זהים ו-q מהם זהים - חלק בעצרת של כל קבוצת זהים. דוגמה: סידור אותיות BANANA = 6! / (3!·2!) = 60.
6. בחירה ממספר קבוצות
Total = #A × #B × #C × ...
אם בוחרים אחד מ-A, אחד מ-B, וכן הלאה - מכפילים. שונה מצירוף או פרמוטציה בתוך אותה קבוצה.
טיפ זיכרון: פרמוטציה ≥ צירוף תמיד. אם קיבלת בצירוף תוצאה גדולה מהפרמוטציה המקבילה - יש שגיאה. C(n,k) = P(n,k)/k!.
3 דוגמאות פתורות - מהקל אל הקשה
דוגמה 1 · קלה · צירוף בסיסי
A hackathon organizer needs to choose a team of 3 developers from a pool of 8 backend engineers. How many different teams are possible?
פתרון:
- שאלת מפתח: האם הסדר משנה? לא - צוות זה צוות, לא משנה מי "ראשון".
- צירוף: C(8,3) = 8! / (3!·5!) = (8·7·6) / (3·2·1) = 336 / 6 = 56.
תשובה: 56 צוותים אפשריים. שים לב לקיצור: בחישוב C(n,k), בטל את (n−k)! מהמונה והמכנה, ונשארת רק k·(k−1)·... במכנה.
דוגמה 2 · בינונית · בחירה מקבוצות + מגבלה
A sushi chef offers 4 types of fish, 3 types of vegetables, and 2 types of sauces. A custom roll uses exactly 1 of each. How many distinct rolls can be created? If a customer insists on tuna fish, how many remain?
פתרון:
- חלק א': מכפלת בחירות עצמאיות. 4 × 3 × 2 = 24 גלילים אפשריים.
- חלק ב': אם הדג חייב להיות טונה - נשארה רק אפשרות אחת לדג. 1 × 3 × 2 = 6 גלילים.
תשובה: 24 גלילים בסך הכול; 6 עם טונה. כלל בחירה מקבוצות: כל קבוצה תורמת פעם אחת במכפלה. בכל פעם שמופיעה מגבלה ("חייב להיות X"), הגודל של אותה קבוצה יורד ל-1 (או למספר הפריטים שעונים על המגבלה).
דוגמה 3 · קשה · עקרון הכפל לפי מיקומים + מגבלה
A new vehicle registration code consists of 5 characters: 2 letters (chosen from A, B, C with repetition allowed) followed by 3 digits (chosen from 0-9 with no repetition). How many distinct codes are possible if the first letter cannot be A?
פתרון:
- אות 1: מותר רק B או C → 2 אפשרויות.
- אות 2: כל אחת מ-A, B, C → 3 אפשרויות.
- ספרה 1: 10 אפשרויות (0-9). ספרה 2: 9 (ללא חזרה). ספרה 3: 8.
- סך הכול: 2 × 3 × 10 × 9 × 8 = 4320 קודים.
תשובה: 4,320 קודים. תובנת מפתח: בשאלות "license plate"-style, חשוב על כל מיקום כקבוצה עצמאית, וזכור את המגבלות (חזרה מותרת? מוגבל?). הסדר חשוב כאן כי המיקום קובע את משמעות התו.
5 מלכודות נפוצות שיוצרות 70% מהטעויות
- פרמוטציה במקום צירוף. "בחר 5 שופטים מתוך 20 לוועדת אתיקה" - אין כאן סדר, השופטים סתם חברים בוועדה. תשובה: C(20,5) = 15,504. אם תכפיל ב-5! לקבל פרמוטציה, תקבל 1.86 מיליון - מספר עצום וטעות מובהקת.
- ספירת אותה תצורה פעמיים. "בכמה דרכים אפשר לבחור 2 צוותים של 5 מתוך 10 שחקנים?" - תלמידים כותבים C(10,5) × C(5,5) = 252. שגוי! החלפת "צוות A" ו"צוות B" יוצרת ספירה כפולה אם הצוותים אינם מסומנים. חלק ב-2 → 126.
- שכחת המגבלה "חייב לכלול X". "צוות של 4 מתוך 12, כאשר מנהיג הצוות נבחר מראש" - בעצם בוחרים 3 נוספים מתוך 11 (כי אחד כבר נקבע). תשובה: C(11,3) = 165, לא C(12,4) = 495.
- סידור מעגלי במקום סידור בשורה. 8 אנשים סביב שולחן עגול: 7! = 5040, לא 8!. הסיבה: סיבוב של כל הסידור יוצר את אותה תצורה בעין צופה חיצוני. בסידור על ספסל ארוך - כן 8!.
- טעויות "בדיוק k" מול "לפחות k". "כמה דרכים לבחור צוות של 5 הכולל לפחות 2 נשים מתוך 6 נשים ו-8 גברים?" - חייב לסכום: בדיוק 2N3M + בדיוק 3N2M + 4N1M + 5N0M. או להשתמש במשלים: סך הכול − (0 נשים) − (1 אישה). שתי הדרכים אפשריות, אבל חישוב ישיר של C(6,2)·C(8,3) לבדו מספק רק "בדיוק 2".
טבלת ההחלטה - איזו נוסחה לבחור
| תרחיש | נוסחה | דוגמה GMAT אופיינית |
|---|---|---|
| סידור k מתוך n - הסדר חשוב | P(n,k) = n!/(n−k)! | 3 מקומות מובחנים מתוך 10 רצים |
| בחירת k מתוך n - סדר לא חשוב | C(n,k) = n!/[k!(n−k)!] | ועדה של 5 מתוך 12 |
| סידור של n פריטים בשורה | n! | סידור 6 ספרים על מדף |
| סידור מעגלי | (n−1)! | 6 אנשים סביב שולחן עגול |
| פריטים זהים | n!/(p!·q!·...) | סידור אותיות במילה |
| בחירה מקבוצות שונות (אחד מכל) | #A × #B × #C | חולצה, מכנסיים, נעליים |
| חזרה מותרת (סידור עם חזרה) | nk | קוד PIN של 4 ספרות |
| "לפחות אחד מ-X" | סך − (אף אחד) | ועדה עם לפחות אישה אחת |
| בחירה משתי קבוצות בו-זמנית | C(a,k₁)·C(b,k₂) | 2 גברים ו-3 נשים מצוות מעורב |
| "שני פריטים חייבים להיות יחד" | קבץ אותם → טפל כיחידה אחת | זוג חברים בשורה |
תובנת זהב: סידור מעגלי = שורה חלקי n. סידור עם זהים = שורה חלקי כפילויות. סידור עם חזרה = לא עצרת. אם תכיר את שלושת ההבדלים מהשורה הסטנדרטית, תפתור 90% מהווריאציות.
תרגיל 2-דקות - חימום מנטלי
- בכמה דרכים אפשר לסדר 5 ספרים שונים על מדף?
- ועדה של 3 מתוך 7 - כמה אפשרויות?
- סידור 4 אנשים סביב שולחן עגול - כמה תצורות?
- בכמה דרכים אפשר לסדר את האותיות של המילה LEVEL?
- מסעדה מציעה 5 מנות ראשונות ו-4 מנות עיקריות. כמה ארוחות (ראשון+עיקרי) שונות?
לחץ לתשובות
תשובות: (1) 5! = 120. (2) C(7,3) = 35. (3) (4−1)! = 6. (4) LEVEL - 5 אותיות, L×2, E×2 → 5!/(2!·2!) = 120/4 = 30. (5) 5 × 4 = 20.
צעד הבא - תרגול תחת לחץ זמן
הנוסחאות בידך. הסימולציה החינמית של mivchan.co.il מציעה בנק שאלות קומבינטוריקה בקצב 1:50 לשאלה - כולל וריאציות סידור מעגלי, פריטים זהים, ומגבלות "חייב לכלול".
תרגול Combinatorics התחל סימולציית Quant
לא יודעים מאיפה להתחיל? בנו תוכנית לימוד אישית (4-16 שבועות)
מדריכים קשורים
הבהרה: mivchan.co.il אינו מסונף ל-GMAC (Graduate Management Admission Council), הגוף המנהל את מבחן ה-GMAT. כל השאלות והדוגמאות באתר נכתבו במקור על ידי הצוות שלנו ואינן נגזרות מ-Official Guide, Manhattan Prep, Magoosh, או כל מקור צד ג'.