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