חידה מספר 12


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

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


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


כמה שבילים לאון סימן?

התשובה הנכונה היא:
5

מצורף ההסבר של רז מנור ניסן מרופין, שהצליח להסביר באופן פשוט את התנאי לקיום של מסלול אוילר בגרף (מסלול שעובר בעם אחת על כל קשת):


במסלול שעובר בכל השבילים יוצאים מתחנה (מתקן/דוכן) ואחר כך מכל תחנה שנכנסים אליה גם יוצאים ממנה חוץ מהתחנה האחרונה שממנה לא יוצאים.

בגלל שעוברים בכל השבילים אז עוברים בכל השבילים שמתחברים לכל אחת מהתחנות ולכן חוץ מתחנת ההתחלה ותחנת הסיום מס' השבילים שמתחבר לכל תחנה חייב להיות זוגי.

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

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

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