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

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

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

• שאלה

  דני מטיל מטבע `3` פעמים ורושם את התוצאות בשורה. כמה אפשרויות שונות קיימות לשורה הזאת?

  נושאים:

  קומבינטוריקה -> כלל המכפלה

• שאלה

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

  הערה: בקבוצת כדורגל תמיד יש `11` שחקנים.

  נושאים:

  קומבינטוריקה -> כלל המכפלה

• שאלה

  במרחב נתונים 30 וקטורים לא מנוונים. הוכח כי יש לפחות 2 שהזווית ביניהם היא לא גדולה מ- 45 מעלות. 
  א. טולפיגו

  נושאים:

  גאומטריה -> טריגונומטריה גאומטריה -> גאומטריה על כדור קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> גאומטריה קומבינטורית גאומטריה -> גאומטריה במישור -> חשבון זוויות גאומטריה -> ווקטורים
  מקורות:
  • תחרות הערים, תש"מ, עיקרית, אביב שאלה 4

• שאלה

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

  א. הוכיחו שהקוסם המרושע יכול לעשות את זה.

  ב. הוכיחו שקיימת עיר שניתן להגיע ממנה לכל עיר אחרת, ושקיימת עיר שאי אפשר לצאת ממנה כלל.

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

  נושאים:

  קומבינטוריקה -> תורת הגרפים קומבינטוריקה -> אינדוקציה הוכחה ודוגמה -> הוכחה בשלילה

• שאלה

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

  נושאים:

  קומבינטוריקה -> גאומטריה קומבינטורית הוכחה ודוגמה -> בניית דוגמה גאומטריה -> גאומטריה במישור -> סימטריה
  מקורות:
  • תחרות הערים, תשמ"א, אביב, גרסה עיקרית, כיתות ט-י שאלה 2 נקודות 7

• זאב וכבשים

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

  נושאים:

  קומבינטוריקה -> גאומטריה קומבינטורית קומבינטוריקה -> אינווריאנטים קומבינטוריקה -> תורת המשחקים הוכחה ודוגמה -> בניית דוגמה
  מקורות:
  • תחרות הערים, תשמ"א, אביב, גרסה עיקרית, כיתות ט-י שאלה 5 נקודות 16

• שאלה

  במדינה יש `100` ערים, ומכל עיר יוצאים `4` כבישים (כביש יכול להתחיל או להסתיים רק בעיר). כמה כבישים יש במדינה הזאת?

  נושאים:

  קומבינטוריקה -> ספירה כפולה קומבינטוריקה -> תורת הגרפים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  במדינה זרה בכל מספר טלפון יש `7` ספרות, והספרה הראשונה תמיד שונה מ-`0`. מה הכמות המקסימלית של מספרי טלפון שיכולים להיות במדינה הזאת?

  הצגת רמז

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

  אריתמטיקה קומבינטוריקה -> כלל המכפלה
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

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

  הצגת רמז

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

  אריתמטיקה קומבינטוריקה -> כלל המכפלה
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  בחברה עובדים `30` אנשים. הצעיר מביניהם הוא בן `20`, והמבוגר – בן `45`. האם נכון שבחברה הזאת בהכרח יש אנשים בני אותו גיל?

  הצגת רמז

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

  קומבינטוריקה -> עקרון שובך היונים
  מקורות:
  • אתר האינטרנט problems.ru