סדר הקפות

The6thAngel

New member
../images/Emo35.gif סדר הקפות

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

n u t

New member
../images/Emo62.gif אני חושבת...

שהצלחתי בלי בכלל להקיף... הנה |>|
 

n u t

New member
אויש, אופס...

גם לא שמתי את הקובץ וגם גיליתי שלא הצלחתי...
 

sagybp

New member
../images/Emo62.gif

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