חידה נוספת

[Crurifragium]

לא ריאלי

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

 

[Shaakedod]

יודע מה

לפי כל החרטוטים שלכם עם גאוני מחשבים אז אולי הוא גאון פי מליאררדדדד מכלכם והוא יכול להמציא תוכנה שת]רוץ את הsecure hash תוך שתי שניות וימצא מספר שהוא מנצח בוודאות ? הגיוני לא ? אם הוא גאון עילאי !!

 

[Crurifragium]

תראה

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

 

[Imai]

האמת שעד עכשיו

לו היה את הרעיון הטוב מכולם. זה שאומרים לבנות תוכנה שתעשה הכל בשבילכם וזהו, זה סתם הורס את האתגר.

 

[Crurifragium]

האמת שעד עכשיו

הרעיון שלו אולי נראה לך הכי טוב, אבל זה עדיין לא הופך אותו לטוב. שוב, תכיני מראש רק שני טקסטים: 8972153700 1 8972153710 1 אם המספר 1-5 של הסטודנט השני הוא 1, אז גם סטודנט לפסיכולוגיה בלי נסיון מתמטי יכול לראות ישר את הספרה השניה ששלח הסטודנט השני, ולשלוח אחד המספרים למעלה בהתאמה (כי מה שמשנה זה ה 10 או 00 בהתחלה, שאו שמשאירים את המספר כמו שהוא, או משנים אותו בדיוק להפכי). אז הסיכוי לנצחון של זה ששולח שני הופך מ50% ל 60%. לא צריך תוכנת מחשב, לא צריך ידע מתמטי, כל אחד יכול לעשות את זה, כולל סטודנט לפסיכולוגיה. או בקיצור, זה עדיין לא פתרון טוב. חוץ מזה לא אמרנו לבנות תוכנת מחשב, אמרנו שזה אפשרי בעזרת פונקציות מתמטיות שצריך מחשב בשביל לחשב אותן. אפשר לכתוב תוכנה. אפשר למצוא תוכנה קיימת. אם זה כן אנשים עם כשרון מתמטי מאוד מאוד רציני אפשר אפילו לחשב לבד. או אפשר למשל לפתוח דף לאתר באינטרנט שיעשה את החישוב אוטומטי. יש שלל אתרים שמקבלים טקסט (כולל מספרים) כנתון, ומחשבים לך hash. למטרת התרגיל הזה, לסטודנטים בלי ידע מתמטי, כל אחד מפונקציות הhash שתמצאי יעבדו. אם הם כן יותר מודאגים, זה גם בסדר, כי כל אחד מהאתרים האלו גם מחשב sha1 שנחשב למאוד טוב כרגע. למשל ראי http://www.devbox.info/tools/sha1-hash-calculator או http://www.fileformat.info/tool/hash.htm שמצאתי פשוט כי הם היו מהראשונים שעלו בחיפוש. האם זה פתרון אידאלי? אולי לא, כי הסטודנטים לפחות צריכים להכיר את הרעיון בשביל לעשות את החישוב. אבל זאת לא דרישה חריגה בחידות. אנחנו הרי מצפים מאסירים אמפיריים בכלא שידעו לעשות חישובי שארית בראש, וכו'. כל צורת חישוב אחרת כזאת, כמו ההצעות שעלו בינתיים, אומרת למעשה "בוא ננסה למצוא חישוב/כלל שיתן לנו תוצאה חד כיוונית שהצד השני לא יוכל להפוך מהר, אבל שתהיה חוקית ומוגדרת היטב בשביל למנוע רמאות". וזה בדיוק זה. רעיונות אחרים הם פשוט זזים מהצד של חישוב וכללים הרבה יותר מדי פשוטים, עד ליותר ויותר מורכבים שלוקחים יותר ויותר זמן. אז אני לא רואה את הבעיה בלהגיד יש שכבר יש סוג של חוקיות וחישובים שבדיוק זאת מטרתו בחיים, וזה הייעוד שלו, שבדיוק מתאים, אז למה לא ללכת עליו במקום על תחליפים שהם לא מספיק טובים? אני לא אומר שאין בהכרח גישות אחרות שלא יכולות לעבוד. יכול להיות שיש, והן יהיו פתרון מעולה, ואפילו עדיף, לחידה הזאת. אבל בינתיים אף אחד כאן עוד לא העלה כאלו.

 

[Imai]

ועדיין

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

 

[Shaakedod]

אני מסכים איתך !

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

 

[Javali]

אפשרי

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

 

[Shaakedod]

תוספת קטנה -פתרון משופץ אם תרצו

הרעיון שלי היה דוגמא של שיטה מסוימת אתה יכול להפוך אותו למספר עם 25 ספרות וכל אחד יזרוק מספר מ1 עד 5 רק שבמקום חיבור המספרים (1-5) אתה כופל אותם ובנוסף המספרים הגדולים בעלי 25 הספרות נכפלים זה בזה והופכים את המספר לדוגמא קטנה: 12345 2 11111 2 עכשיו המספר החדש שנוצר הוא 137165295 ומיקום הספרה הוא 4 (2*2) עכשיו הופכים את המספר שקיבלנו 592561731 מיקום הספרה הרביעית היא 1 ולכן הפרד מנצח.... אני די בספק אם אתה יכול לחשב דבר כזה תוך 5 שניות ... "בלי לבנות תוכנה" 25 ספרות אוקיי ? כפל של 2 מספרים בעלי 25 ספרות ואחר כך להפוך ולמצוא את מיקום הספרה אם אתה אומר שזה לא טוב ... אז כנראה שאתה יכול לעשות חישבוים כאלה תוך 5 שניות....

 

[Javali]

secure hash

מה שאתה מנסה עכשיו לעשות (אפילו אם אתה לא מודע לזה) זה למצא פונקצית hash מתאימה. secure hash היא פונקצית הצפנה. הנסיון מלמד שכאשר אנשים שאינם מומחים בתחום מנסים להמציא פונקצית הצפנה הם עושים את זה רע מאוד. מתגובותיך נראה שהבנתך בתחום של תורת ההצפנה נמוכה מאוד, אם בכלל קיימת. הפתרונות שאתה מציג תואמים את רמת ההבנה הנשקפת. הפתרון שלך רע משלוש סיבות - ראשית, אפילו בהנחה ששני המשתתפים בוחרים מספרים אקראים, לא הוכחת שההסתברות לקבל מספר זוגי זהה לזו של לקבל מספר אי זוגי, ולכן המשחק אינו בהכרח הוגן. שנית, אתה מניח שהדרך היחידה לחשב את הפונקציה היא הדרך שלך - לכפול מספרים בני 25 ספרות - אבל אתה שוכח שיש אפשרויות אחרות. בפרט מה שמעניין אותנו זה רק ספרה אחת בתוצאה של הכפל. קירובים יכולים לתת לנו הסתברות גבוהה מ-50% לנחש מה הספרה הזו תהיה ולנצל את זה למטרותינו. שלישית - אם השחקן שמנצח במקרה והתוצאה זוגית נותן את המספרים הבאים: 1 7449078417776885386820000 הוא זוכה.

 

[jaXon]

חידה נהדרת

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

 

[Imai]

ככל הנראה אתה לא טועה,

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

 

[כלמנ]

אפשר לסכם? (פתרון אלגנטי בפנים)

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

 

[Imai]

אני הייתי בוחרת בתנ"ך ../images/Emo13.gif

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

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

 

[Crurifragium]

רעיון מעניין, יש לי כמה הערות

1. הכי חשוב, במקרה זה א' אמור קודם לבחור אות, ואח"כ למצוא מקום בספר שהאות מופיעה בו. הספר הוא רק האמצעי לאפשר לב' לוודא שזאת האות האמיתית. כי אם א' לא בוחר אות מראש, אלא פותח את הספר ובוחר משם, אז בחירת האות היא לא אקראית, אלא מאוד תלויה בהתפלגות של אותיות בשפה. מה שנותן לב' אפשרות טובה לנחש מראש איזו אות תבחר. 2. צריך ספר שיש לשניהם. לא יעזור לב' ללכת למחרת לספריה לבדוק, כי זה כבר מאוחר מדי וה"ניסוי" עבר. למרות שזאת כמובן בעיה, כי אם מסכמים מראש על ספר ספציפי אז מגבלת הזמן לבחירה של ב' הופכת להרבה יותר קריטית. אם יש אוסף גדול של ספרים שיש לשניהם, ושא' יכול לבחור מתוכם איזה ספר שהוא רוצה, זה מקל על הבעיה. 3. אם תתן לאנשים לבחור באקראי אות כלשהי, אז (בדיוק כמו עם אותו דבר במספרים) ההתפלגות של הבחירות לא הולכת להיות אחידה. יש אותיות שהרבה יותר סביר שיבחרו בהן מאחרות. ואם במקרה הספציפי הזה אנחנו דנים בסטודנטים לפסיכולוגיה, אז יש אפילו סיכוי שהם קראו מאמרים בנושא. מצד שני, בניגוד למספרים, אני לא בטוח לגמרי שנעשו מחקרים מספיק מסודרים, ומספיק הרבה, בנושא, אז יכול להיות שזה עוד בסדר. 4. בשום ניסוי שנתקלתי בו באוניברסיטה לא הציעו לחלק למשתתפים וויסקי. אני חושב שהייתי באוניברסיטה הלא נכונה. 4.5 הצעת ייעול אולטימטיבית - נותנים לכל אחד משני המשתתפים לשתות 6-7 כוסיות וויסקי, ואז לבחור מספר או אות. אני חושב שהסיכוי לרמאות, חישובים מהירים, וכו', ירדו דרסטית.

 

[Imai]

../images/Emo2.gif אף פעם לא הציעו לך וויסקי בניסוי?

איפה בדיוק למדת, בטכניון?

 

[Crurifragium]

לא, אף פעם ../images/Emo7.gif

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

-- אגב, סיפור שנתקלתי בו ממש לא מזמן, שגם קשור לנושא חידות, וגם קשור לנושא שנדון פה על מה ועד כמה אנשים יכולים לחשב במהירות בראש: יש חידות מהסוג של... מרחק בין A ל B הוא 1000 ק"מ. רכבת יוצאת מ A ל B במהירות 20 קמ"ש. רכבת נוספת יוצאת מB ל A במהירות 30 קמ"ש. בין הרכבות עף זבוב, במהירות של 100 קמ"ש, שעף מרכבת לרכבת, וכל פעם שהוא מגיע לרכבת אז הוא מסתובב ועף לעבר הרכבת השניה. מה המרחק שהזבוב יעוף עד שהרכבות יפגשו? ויש שתי דרכים עקרוניות לפתור את זה. הראשונה, שהיא מה שבד"כ אנשים חושבים עליה מיד, היא הארוכה והקשה יותר. יש סדרה אינסופית של סכום מרחקים שהזבוב עובר. אפשר למצוא את הנוסחא, ולחשב אותה. לא טריוויאלי, אבל עם מספיק ידע מתמטי אנשים בד"כ יכולים לפתור את זה גם עם נייר ועפרון, ולפחות כמה וכמה דקות. השיטה השניה היא להבין שאפשר בקלות להוציא מהחידה את הזמן שלוקח לרכבות להפגש (המהירות שלהן אחת אל השניה ידועה, והמרחק ביניהן ידוע), ואז עם הזמן הזה והמהירות של הזבוב ברור מה המרחק שהוא יעוף. את זה בערך כל אחד יכול לעשות בראש, מי שמחשב מהר אז אפילו בכמה שניות, אבל רק אחרי שחושבים על הרעיון. יש סיפור של פול הלמוס (מתמטיקאי), שפעם סיפר את החידה הזאת לוואן ניומן (מתמטיקאי, מאוד מאוד ידוע). וואן ניומן מיד נתן לו את התשובה. אז פול אמר לו שזה מוזר, כי בד"כ אנשים דווקא מתחילים לסכום את הסדרה האינסופית. וואן ניומן ענה לו "למה אתה מתכוון, מוזר? ככה אני עשיתי את זה!" עכשיו, ברור שג'ון וואן ניומן הוא מקרה חריג, אבל זה בפרוש משהו שכולם כאן היו מרגישים מאוד בנוח להגיד שדווקא אף אחד לא יכול לעשות בראש תוך 2-3 שניות, לא?

 

[Imai]

וואן ניומן חריג אולי במספרים

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

 

[Crurifragium]

../images/Emo122.gif

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

 

[Imai]

הוא בטח היה

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