קומבינטוריקה
קומבינטוריקה היא אמנות הספירה. היא עוסקת בבחירות, סידורים וצירופים של אובייקטים. שאלות כוללות קביעת מספר הדרכים לביצוע משימות, סידור פריטים (תמורות), או בחירת תת-קבוצות (צירופים), תוך שימוש לעיתים קרובות בעקרונות כמו עקרון המכפלה ועקרון הסכום.
עקרון שובך היונים ספירה כפולה מקדמים בינומיים ומשולש פסקל כלל המכפלה תורת הגרפים התאמות אינדוקציה תורת המשחקים גאומטריה קומבינטורית אינווריאנטים בדיקת מקרים תהליכים טבלאות מספריות צביעות-
שאלה
בתרגיל חשבון הבא ספרות שונות הוחלפו על ידי אותיות שונות, וספרות זהות – על די אותיות זהות. שחזרו את התרגיל:
`BAOxxBAxxB=2002`
נושאים:אריתמטיקה אלגברה -> משוואות אלגברה -> אי שוויונים לוגיקה -> הגיון תורת המספרים -> מספרים ראשוניים -> פרוק לגורמים ראשוניים קומבינטוריקה -> בדיקת מקרים -> תהליכים חידות ורבוסים -> שחזרו את התרגיל -
שאלה
נתונים `50` מספרים טבעיים שונים בין `1` ל-`100`. ידוע כי אין בינם שני מספרים שסכומם שווה ל-`100`. האם נכון שאחד מהמספרים האלה חייב להיות ריבוע שלם?
נושאים:תורת המספרים -> מספרים ראשוניים אריתמטיקה קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> התאמות לוגיקה -> הגיון הוכחה ודוגמה -> בניית דוגמה תורת הקבוצות קומבינטוריקה -> בדיקת מקרים -> תהליכים הוכחה ודוגמה -> הוכחה בשלילה -
שאלה
ברשותו של שלומי לוח שחמט וקובייה שגודל הפאה שלה הוא כמו גודל של משבצת הלוח. שלומי רוצה לצבוע את פאות הקובייה בשחור ולבן, ואז לגלגל את הקובייה על פני הלוח כך שכל פעם הפאה שנוגעת בלוח תהיה באותו הצבע כמו המשבצת בה היא נוגעת. הקובייה אמורה לעבור בכל משבצת בלוח בדיוק פעם אחת. האם שלומי יוכל לעשות זאת? נמקו או הביאו דוגמה.
נושאים:קומבינטוריקה -> גאומטריה קומבינטורית קומבינטוריקה -> תורת הגרפים לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה קומבינטוריקה -> צביעות -> צביעת שחמט -
שאלה
מידי ערב יובל מסיים עבודה בזמן אקראי ומגיע לתחנת אוטובוס. בתחנה הזאת עוצרים שני אוטובוסים: מספר `7`, שנוסע לבית של יובל, ומספר `13`, שנוסע לבית של ידידו שלומי. יובל עולה על האוטובוס הראשון שמגיע וכתלות בכך נוסע לשלומי או הביתה.
כעבור זמן מה יובל שם לב כי אחרי עבודה הוא נוסע לשלומי בערך פי שניים יותר מאשר הוא נוסע הביתה. הוא הסיק מזה שהאוטובוס מספר `13` מגיע בתדירות פי שניים גבוהה יותר מאוטובוס מספר `7`.
האם יובל בהכרח צודק?
נושאים:הוכחה ודוגמה -> בניית דוגמה קומבינטוריקה -> בדיקת מקרים -> תהליכים תורת ההסתברות לוגיקה -> הגיון -> פרדוקסים -
האם לכל הסוסים יש אותו צבע?
שלומי טוען כי הוא הוכיח באמצעות אינדוקציה שבכל עדר כל הסוסים באותו צבע:
אם יש סוס אחד, אז הוא בצבע של עצמו - כך הראנו כי בסיס אינדוקציה מתקיים.
בשביל מעבר אינדוקציה, נמספר את הסוסים מ-`1` עד `n`. לפי הנחת אינדוקציה, הסוסים שמספרם מ-`1` עד `n-1`, כולם באותו צבע. באופן דומה, הסוסים שמספרם מ-`2` עד `n`, גם הם כולם באותו צבע. ובגלל שהצבעים של הסוסים מ-`2` עד `n-1` הינם קבועים ולא יכולים להשתנות בהתאם לאיך ששייכנו אותם לקבוצה זו או אחרת, אז גם הסוסים ה-`1` וה-`n` חייבים להיות באותו הצבע.
האם שלומי ביצע טעות במהלך ההוכחה שלו? אם כן, מצאו את הטעות.
-
באובב
בתרגיל הבא ספרות זהות הוחלפו באותיות זהות, וספרות שונות הוחלפו באותיות שונות. שחזרו את התרגיל.
`BAOxxBAxxB = 2002`
נושאים:אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה לוגיקה -> הגיון תורת המספרים -> מספרים ראשוניים -> פרוק לגורמים ראשוניים קומבינטוריקה -> בדיקת מקרים -> תהליכים חידות ורבוסים -> שחזרו את התרגיל -
שאלה
מכשף זימן אליו `20` אבירים, שמתוכם `10` אלפים ו-`10` גמדים. המכשף רוצה לבחור מתוכם צוות שיבצע משימה סודית. על הצוות הזה להכיל כמויות שוות של אלפים וגמדים.
כמה יש אפשרויות לצוות כזה? (שימו לב הוא לא יכול לבחור צוות ריק)
-
שאלה
בארץ מסוימת יש יותר מ-101 ערים. הבירה מקושרת בקווי טיסה עם 100 ערים וכל עיר פרט מהבירה מקושר בקווי טיסה בדיוק עם 10 ערים. נתון שמכל עיר ניתן להגיע לכל עיר אחרת (אולי לא בקו ישיר). הוכח כי ניתן לסגור חצי קווי טיסה שמובילים לבירה כך שהאפשרות להגיע מכל עיר לכל עיר תשמר.
מקורות: -
משולשים במשושה
כמה משולשים יש בתמונה? יש לספור את כל המשולשים שנוצרים על ידי הקווים
מקורות: -
חתול לסבתא
לסבתא חנה יש מספר חתולים. יום אחד הגיעו אליה שלושה נכדים שלה, אבי, בני וגילי, וניסו לנחש כמה חתולים יש לה.
אבי אמר: "לסבתא יש לפחות 7 חתולים",
בני אמר: "אבל פחות מ-10, לדעתי",
ואז גילי אמרה: "לסבתא חנה יש או 9, או 10, או 11 חתולים".
"כולכם צדקתם!" ענתה הסבתא
אז כמה חתולים יש לה?
מקורות: