דרכים באפגניסטאן

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

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

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

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

לאחר איסוף ממושך של מודיעין, הגיעו האמריקנים לשלושת המסקנות הבאות:
(0) מערכת הדרכים המקורית היא מחוברת (כלומר כל עיר מחוברת לכל עיר אחרת);
(1) אף הפצצה של עיר בודדת לא תנתק את ערי אפגניסטאן;
(2) כל הפצצה של שתי ערים שאינן מחוברות בדרך ישירה,
תנתק את ערי אפגניסטאן.

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

שיתוף החידה בפייסבוק
דרגת קושי: קשה
תחום החידה: מתמטיקה
סוג הפתרון: חשיבה שיטתית
קניון loox

חיפוש

חיפוש מתקדם

הצטרף לרשימת התפוצה שלנו