שירשור החידות הגדול

moco · שליחה 12/09/2007 1:39

אין לי מושג למה הוא התכוון, ייתכן מאוד שלמקרה א' בלבד - זה יותר אלגנטי שזה יוצא 1.
אבל הוא כתב משהו שכולל גם את ב'.

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

שליחה 12/09/2007 8:49

osherov,

התשובה שלך היא מלאה ו-100% נכונה.

AviBiton · שליחה 12/09/2007 9:55

amirbd
התשובה שלך נכונה מאוד.

moco
אני מבין מה כתבת, וכוונתי (למרות ששכחתי לציין זאת) היא שאין כפילויות.

לכן אני מעביר את השרביט ל- amirbd

amirbd · שליחה 12/09/2007 10:21

O.K., מה החוקים עכשיו - יש לנו שני ענפים חיים (אחד של osherov ואחד שלי). האם נריץ שני חידות במקביל (אני מוכן לותר אם מעדיפים שתהיה רק חידה אחת במקביל).

שליחה 12/09/2007 10:26

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

אם אין לנו חידה מכם אז הכל פתוח.

amirbd · שליחה 12/09/2007 11:48

O.K. קבלו חידה חמודה (מי שמכיר שיתן לאחרים צ'אנס לפתור).

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

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

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

Shed · שליחה 12/09/2007 13:56

התשובה לחיפושיות היא דקה.

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

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

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

osherov · שליחה 12/09/2007 14:57

חידה יפה, תשובה יפה !
(amirbd רק צריך לאשר את הפיתרון)

השישרוש פתאום התעורר

amirbd · שליחה 12/09/2007 15:20

פתרון נכון !!! נכון שזו חידה חמודה

.

השרביט עובר ל-Shed בברכת חג שמח לכל חברי הפורום.

שליחה 12/09/2007 16:01

חידה מעולה ופיתרון מעולה!

Shed · שליחה 12/09/2007 16:16

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

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

moco · שליחה 12/09/2007 17:05

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

טוב, נתחיל לשבור את הראש.

moco · שליחה 12/09/2007 17:40

הנה פתרון שהציע בני (אני משפצר קצת את הנוסח שלו). איני בטוח שזה נכון כי לא משתמשים כלל בעובדה שלקוד 10 ספרות.
נקרא לקוד X ונתיחס אליו כמספר.
נבחר עוד שני מספרים (לא משנה מה) שנקרא להם Y ו Z.
עכשיו נרכיב משוואות לינאריות שכל שלוש מהן בלתי תלויות.
למשל
[left]
X + Y + Z = A
X + 2Y + Z = B
X + 2Y + 2Z = C
X + 3Y + 2Z = D
[/left]
וכך הלאה 10 משוואות סה"כ, כאשר A,B,C ... הם מספרים , לא משתנים.
כל שלושה קצינים יפתרו מערכת של 3 משוואות ויקבלו את X.

amirbd · שליחה 12/09/2007 17:45

Shed,

האם הקצינים הם גם מתמטיקאים לעת מצוא ?

להלן פתרון "מתמטי" שאני מקווה שהוא נכון.

נסמן את הקוד הסודי ב-s.

נבחר באקראי פולינום מדרגה שלישית (נשמר בסוד)
p(x)= a+b*x+c*x^2

נותנים לקצין ה-i את הערך של הפולינום p ב-i, כלומר את
a+b*i+c*i^2, בנוסף אומרים לכל קצין את ההפרש בין a לבין הקוד הסודי

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

פתרון זה ניתן להכללה לכל מספר קצינים (דרגת הפולינום).

הערה - גם אם הפתרון הזה נכון אני מקווה שיש פתרון פשוט יותר...

Shed · שליחה 12/09/2007 18:01

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

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

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

moco · שליחה 12/09/2007 20:07

Shed כתב:הקצינים הם לא מתימטיקאים דגולים .
...

אבל כבר לא דורשים קצת אלגברה בסיסית בשביל לקבל קצונה? ועוד לחברה בצוללת גרעינית? איזה פחד
אה שכחתי, זה קצינים בצוללת גרעינים

שאלה: יש שימוש לנתון שזה מספר עם 10 ספרות (כמספר הקצינים) ?

Shed · שליחה 12/09/2007 22:50

כשאני הייתי קצין האלגברה שלי לא היתה משהו... (מצד שני, אני לא הייתי בצוללת גרעינים)

ה-10 ספרות הוא לא נתון מחייב.

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

amirbd · שליחה 13/09/2007 1:46

Shed,

אני לא מבין מה רע בפתרון שלי - (חוץ מזה שהוא מתמטי) אני נעלב בשם עדי שמיר (אחד ממפתחי צופן ה-RSA), שלפני שנים רבות פרסם מאמר בו תיאר טכניקה זו להסתרת אינפורמציה בצורה מושלמת (לא היו במאמר קצינים או גרעינים למיטב זכרוני, והוא יותר מתמטי, אך גם שם היה שימוש בפולינומים). ספציפית, אין לזוג קצינים או לקצין בודד שום אינפורמציה חלקית שתעזור להם לנחש את הקוד (בהנחה שהפולינום הוא מעל שדה מתאים שמכיל את s) - במובן התיאורתי של המילה יש להם zero knowledge לגבי הפולינום (כי יש להם רק שתי שורשים שלא מספיקים למציאת הפולינום).

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

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

נבחר מישור (דו מימדי) בחדר זה כך שהוא חותך את קיר הקודים בדיוק במיקום הסוד האמיתי.

עבור כל קצין נבחר נקודה אקראית על המישור הסודי (x,y,z) וזה יהיה החלק שלו (נ"צ תלת מרחבי בחדר).

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

פתרון זה לא דורש מתמטיקה, אך לא ניתן להכליל אותו ליותר מימדים...

moco · שליחה 13/09/2007 2:57

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

Shed · שליחה 13/09/2007 6:15

יש לנו פיצוח כפול!

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

על מנת לעבור ל-N קצינים, עוברים לעבוד ב-N מימדים במקום שלושה).

בגל מקרה - שני הפתרונות מספקים.