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