nenkuro - They do not have anything except for the command!

החידה שאני מכיר דומה, אבל קשה יותר:

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

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

1.  לך מטר צפונה.

2.  אם עברת על פני מצנח - עבור לפקודה 3; אם לא - עבור לפקודה 1.

3.  לך מטר דרומה.

4.  אם עברת על פני מצנח - עבור לפקודה 1; אם לא - עבור לפקודה 3.

חזקות של 2 לא באות בחשבון כאן - אי-אפשר לומר לרובוט "לך מרחק כפול ממה שהלכת קודם".  אפשר לדייק בחידה ולתת את רשימת הפקודות האפשריות באופן מפורט:

א. לך מטר צפונה.

ב. לך מטר דרומה.

ג. הישאר במקום.

ד. עבור לפקודה מספר  N.

ה. אם עברת על-פני מצנח - בצע פעולה X (א/ב/ג/ד); אם לא - בצע פעולה Y.

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

בהצלחה!

יואב

לשאלה היפוטתית מותר להציע תשובה היפוטתית. לא צריך אפילו סדרת פקודות.

פקודה אחת!

"הקש על המסילה והתקדם לכוון בו הנקישות מתחזקות". גם רעיון, הא?

צטט: הכינוי קיים 2008-04-23 03:23:44

לשאלה היפוטתית מותר להציע תשובה היפוטתית. לא צריך אפילו סדרת פקודות.

פקודה אחת!

"הקש על המסילה והתקדם לכוון בו הנקישות מתחזקות". גם רעיון, הא?

יכולה להיות התאבכות הורסת לגלים בתוך הברזל שתקטע את התקשורת.

צטט: nenkuro 2008-04-22 21:33:14

you people are not thinking about the simplest solution. the speed of sound in iron (from which the rail is made) is 7000 meters per second. the first paratrooper simply bangs the rail every one in a while. the other has the instructions to reply with a bang when he hears a bang. the first paratrooper can note the time interval it takes the reply to come. then he starts moving in a certain direction. if the time interval gets longer and longer - he is going in the wrong direction! if it is shorter and shorter, he is going in the right direction!

Both should do the same thing.

They can be stationed in a much longer distance than the sounds of the bangs... 

אם הייתי צריך לשלוח שני אנשים למשימה הזו ורוצה להבטיח הצלחה - ללא ספק הייתי בוחר בפתרון הראשון / שני שהוצע

פתרון הנקישות יש אלמטים סוביקטיביים וסיכונים ולכן לא מובטחת השלמת המשימה (ככל שמדובר בבני אדם ולא בגירסת הרובוטים) :

1. החלטה האם הנקישה נחלשה או התחזקה

2. האם המקיש מצליח להקפיד על אחידות הנקישות

3. ההחלטה מי מהשנים ממשיך להקיש ומי הולך לאורך המסילה

וכו'

צטט: עופר @ 2008-04-23 12:05:42

אם הייתי צריך לשלוח שני אנשים למשימה הזו ורוצה להבטיח הצלחה - ללא ספק הייתי בוחר בפתרון הראשון / שני שהוצע

פתרון הנקישות יש אלמטים סוביקטיביים וסיכונים ולכן לא מובטחת השלמת המשימה (ככל שמדובר בבני אדם ולא בגירסת הרובוטים) :

1. החלטה האם הנקישה נחלשה או התחזקה

2. האם המקיש מצליח להקפיד על אחידות הנקישות

3. ההחלטה מי מהשנים ממשיך להקיש ומי הולך לאורך המסילה

וכו'

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

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

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

הצנחן הראשון הולך קדימה

השני מסתובב והולך אחורה

בהנחה כמובן ששניהם צונחים עם כיוון הטיסה 

צטט: סבתא'לה 2008-04-29 18:20:25

הצנחן הראשון הולך קדימה

השני מסתובב והולך אחורה

בהנחה כמובן ששניהם צונחים עם כיוון הטיסה

צודקת.

ככה זה פשוט מדי, אנחנו אוהבים להסתבך. ;-)

אם הם צונחים מגובה רב וכל הזמן מסתובבים?

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

 (זהירות - spoiler בסוף...)

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

  הגרסה שאני מכיר היא כדלהלן (בסוף יש פיתרון):

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

א. לך מטר צפונה.

ב. לך מטר דרומה.

ג. הישאר במקום.

ד. עבור לפקודה מספר  N.

ה. אם יש מצנח במרחק של מטר או פחות - בצע פעולה X (א/ב/ג/ד); אם לא - בצע פעולה Y.

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

 ============================================================

  פיתרון (!)

---------------

  תכנית לדוגמה שעובדת היא:

1. לך מטר צפונה.

2. לך מטר צפונה.

3. אם יש מצנח במרחק של מטר או פחות - עבור לפקודה מספר 5 ; אם לא - הישאר במקום.

4. עבור לפקודה מספר 2.

5. לך מטר צפונה.

6. עבור לפקודה מספר 5.

  אם הרובוטים צנחו במרחק של קילומטר זה מזה, אחרי כשעתיים וחצי (9000 שניות) הם ייפגשו, כשלושה קילומטר צפונית למצנח הצפוני.

יואב,

הסגנון הזה של החידה נאמר כבר למעלה.

אני חושש שהפתרון שלך לא עובד... 

נדמה לי שהפיתרון דווקא בסדר - בשנייה הראשונה שני הרובוטים יילכו מטר צפונה, ואח"כ הם יילכו עוד 999 מטר צפונה בקצב של מטר ב-3 שניות (כי על כל ביצוע של הפקודות 2, 3 ו-4 הם מתקדמים מטר אחד).  המרחק בינהם נשאר קבוע, כלומר 1000 מטר.  אז הרובוט הדרומי יותר יגיע למצנח של הרובוט הצפוני, ומאותו רגע הוא יתחיל להתקדם בקצב של מטר ב-2 שניות (על כל ביצוע של פקודות 5 ו-6 הוא מתקדם מטר אחד).  הרובוט הצפוני ממשיך להתקדם בקצב של מטר ב-3 שניות, לכן כל 6 שניות המרחק ביניהם מתקצר במטר אחד (כי 1=3-2).  יוצא שאחרי 6000 שניות המרחק יהיה 0, כלומר הם ייפגשו.  בסה"כ הזמן שעבר הוא 1+3x999+6000=8998 שניות, או קצת פחות משעתיים וחצי (והמרחק שהרובוט הצפוני עובר בינתיים הוא 1000+2000=3000 מטר).  אולי אני טועה, אבל אני לא רואה איפה  :)