קומבינטוריקה, תורת הגרפים

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

  • שאלה

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

  • שאלה

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

  • שאלה

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

    מקורות:

  • חידת מסילת רכבת

    צרו דיאגרמה על דף נייר גדול, כמו באיור, והכינו שלושה אסימונים המסומנים ב-A, שלושה המסומנים ב-B ושלושה המסומנים ב-C. ניתן לראות שבצומת הקווים ישנם תשעה מקומות עצירה, ומקום עצירה עשירי מחובר למעגל החיצוני כמו הזנב של האות Q. הניחו את שלושת האסימונים או הקטרים המסומנים ב-A, את שלושת המסומנים ב-B ואת שלושת המסומנים ב-C במקומות המצוינים. החידה היא להזיז את הקטרים, אחד בכל פעם, לאורך הקווים, ממקום עצירה למקום עצירה, עד שתצליחו להשיג A, B ו-C על כל מעגל, וגם A, B ו-C על כל קו ישר. עליכם לעשות זאת בכמה שפחות מהלכים. כמה מהלכים אתם צריכים? מקורות:

  • חידה לנוער

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

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

     

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

    מקורות:

  • דגל היוניון ג'ק

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

  • המעגל המנותח

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

  • החידה של מפקח הצינורות

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

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

    מקורות:

  • ביקור בעיירות

    מטייל, היוצא מעיירה מס' `1`, מעוניין לבקר בכל אחת מהעיירות פעם אחת בלבד, תוך כדי נסיעה רק בדרכים המסומנות על ידי קווים ישרים. כמה מסלולים שונים קיימים מהם הוא יכול לבחור? כמובן, עליו לסיים את מסעו בעיירה מס' `1`, ממנה הוא התחיל, ועליו להתעלם מצמתים, אלא לנסוע ישר מעיירה לעיירה. זוהי חידה קלה באופן מגוחך, אם ניגשים אליה בדרך הנכונה. מקורות:

  • חֲמִשָּׁה עָשָׂר פְּנוֹת

    הנה עוד חידת מסע מוזרה, שהפתרון שלה דורש תושייה. במקרה הזה, הנוסע מתחיל מהעיר השחורה ורוצה להגיע רחוק ככל האפשר תוך ביצוע חמש-עשרה פניות בלבד, ולעולם לא לנסוע באותה דרך פעמיים. ההנחה היא שהערים מרוחקות זו מזו במייל אחד. לדוגמה, נניח שהוא נסע ישר ל-A, אחר כך ישר ל-B, אחר כך ל-C, D, E ו-F, תגלו שהוא נסע שלושים ושבעה מיילים בחמש פניות. עכשיו, כמה רחוק הוא יכול להגיע בחמש-עשרה פניות? מקורות: