50 פתקים ו50 קופסאות

[Ori]

גברת נחמדת חדה לי את החידה הזאת אתמול אחרי שהמוח שלי כבר נמס.
הוכיחה לי שתי דברים,
שלא משנה כמה אתה חכם, אתה טיפש
שאם פתרת כל היום מתמטיקה מתקדמים 2 אז המוח שלך יוצא לשביתה

עכשיו לחידה (עם שינוי קל כי אני יודע שיהיה לכם קצת קשה)

משחק ל-2 שותפים:
בחדר נמצאות חמישים קופסאות ממוספרות מ-1 עד 50.
1. ממספרים חמישים פתקים מ-1 עד 50 ומכניסים אותם לקופסאות בצורה אקראית כך שיש פתק 1 בכל קופסא.
2. מכניסים את אחד השותפים לחדר ומבקשים ממנו לפתוח את כל הקופסאות ולראות את כל הפתקים, לאחר שראה את כל הפתקים מותר לו להחליף בין 2 פתקים, ואסור לו לדבר עם שותפו לאחר מכן.
3. מכניסים את השותף השני לחדר ונותנים לו מספר אקראי בין 1 ל 50, על השותף השני למצוא את הפתק עם המספר האקראי בלכל היותר-25 נסיונות (כלומר לפתוח לכל היותר 25 קופסאות).

מה צריכים השותפים לעשות כדי לנצח במשחק תמיד?

בלי לחפש תשובות באינטרנט ובלי לרמות זה חידה קצת קשה אבל הפתרון פשוט בהצלחה

[ShinTen]

טעות שלי.

[YaKiRaMa]

לא ברור איזה פתק אקראי הוא צריך למצוא, נאמר שכל הפתקים מוכנסים בצורה אקראית..האם התכוונת שהשני צריך למצוא איזה 2 פתקים הבחור הראשון החליף?

[Tiger]

השותף הראשון צריך להשים את הפתק בקוספא ההאי זוגית.
השותף השני צריך לפתוח רק הקופסאות האי זוגיות.

[Ori]

דבר ראשון שימו בספויילרים
דבר שני יניב אתה לא צודק

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

עוד משהו השותף הראשון לא יודע איזה מספר יבקשו מהשותף שלו לחפש

[InSane]

ספוילר:

שישאיר את הקופסא פתוחה וזהו

[ישראל]

דבר ראשון שימו בספויילרים
דבר שני יניב אתה לא צודק

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

עוד משהו השותף הראשון לא יודע איזה מספר יבקשו מהשותף שלו לחפש

לשותף הראשון מותר לפתוח את הקופסאות? מותר לו גם שלא להחליף?

[theidan]

אני מכיר את החידה אז אני לא יהרוס.
התשובה היא מתמטית נטו, ובלי התחכמויות כאלו ואחרות.
אני אתן רמז דיי רציני, הוא יהיה בספויילר.

ספוילר:

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

[ישראל]

בהנחה שהשותף הראשון יכול לפתוח את הקופסאות, נראה לי שזה הפתרון:

ספוילר:

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

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

[Flash]

גם אם תסביר לי את הפתרון אני לא יבין אותו חבל לנסות!

[Ori]

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

[Flash]

נשמע מופרך תוכיח!

[Ori]

קח דוגמא של 10 עד 5 ניסיונות