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

א. הוכיחו שהקוסם המרושע יכול לעשות את זה.

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

ג. הוכיחו שקיימת דרך שעוברת בכל הערים ויש רק אחת כזו.

דרגת קושי (1 קל מאד - 10 קשה מאד): 6

נושאים:
קומבינטוריקה -> תורת הגרפים קומבינטוריקה -> אינדוקציה

עדיין אין תגובות

נדרש אימות

יש להכנס לאתר על מנת להגיב.

כניסה