קומבינטוריקה, ספירה כפולה

ספירה כפולה היא טכניקת הוכחה קומבינטורית שבה כמות נספרת בשתי דרכים שונות. השוואת שני הביטויים המתקבלים יכולה להוביל להוכחת זהויות או אי-שוויונים. שאלות דורשות זיהוי קבוצה שניתן לספור בכמה דרכים.

• שאלה

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

  נושאים:

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

• שאלה

  האם תוכלו למלא טבלה בגודל `5xx5` על ידי מספרים ממשיים כך שסכום בכל שורה יהיה חיובי, וסכום בכל עמודה יהיה שלילי?

  הצגת רמז

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

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

• שאלה

  האם תוכלו למלא טבלה בגודל `5xx5` על ידי

  א. מספרים שלמים,

  ב. מספרים ממשיים,

   כך שהסכום בכל שורה יהיה זוגי, והסכום בכל עמודה יהיה אי זוגי?

  הצגת רמז

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

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

• שאלה

  האם תוכלו למצוא `35` מספרים שלמים שהממוצע שלהם שווה ל-`6.35`?

  הצגת רמז

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

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

• שאלה

  בשתי כיתות בעלות כמויות זהות של תלמידים התקיים בוחן. אחרי בדיקת הבוחן, המורה טען שכמות של ציוני `0 ` הייתה ב-`13` גדולה יותר מכמות של כל הציונים האחרים ביחד. האם יש מצב שהוא טעה?

  הצגת רמז

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

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

• המשימה המתוחכמת

  לחנה יש סלסלה בה `13` תפוחים. חנה רוצה לדעת את המשקל הכולל של כל התפוחים האלה. לרחל יש משקל דיגיטלי, והיא מוכנה לעזור לחנה, אבל רק בתנאים הבאים: בכל שקילה חנה יכולה לשקול בדיוק `2` תפוחים, והמספר של השקילות לא יכול לעבור את `8`.

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

  נושאים:

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

• שאלה

  פרש שח יצא מהמשבצת `a1` והגיע למשבצת `h8`. האם יתכן שבדרך הוא ביקר בכל משבצות הלוח בדיוק פעם אחת?

  הצגת רמז

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

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

• שאלה

  נתון לוח בגודל `M times N`, ובכל משבצות הלוח כתובים מספרים ממשיים. ידוע כי הסכומים בכל שורה ובכל עמודה של הלוח שווים ל-`1`.

  הוכיחו כי `M = N`.

  נושאים:

  קומבינטוריקה -> ספירה כפולה לוגיקה -> הגיון אלגברה -> אי שוויונים -> ממוצעים

• שאלה

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

  נושאים:

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

• שאלה

  הארץ הקסומה מורכבת מ-`25` מחוזות. האם יתכן שכל מחוז גובל במספר אי זוגי של מחוזות אחרים?

  נושאים:

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