חידה קשה...

alone66

New member
חידה קשה...

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

slallum

New member
המף :)

8 כיוונים. שאלה ראשונה: אני חושב ש"חיפוש בינארי" הכי יעיל פה. כלומר - "האם זה אחת מ-4 הכיוונים האלה: ..?" ובהתאם לתשובה שלו לוקחים 2 מתוך הכיוונים שצריך, ואז בהתאם לתשובה שלו לקחת כיוון אחד מתוך ה-2 שצריך, ואז גילינו את התשובה. זה אומר שתוך 3 שאלות אפשר לגלות. ואם זה N כיוונים אז בתוך zzz log[2](N)] zzz שאלות. נראה לי לפחות :) שאלה שלישית: ניקח את מקרה החיפוש הבינארי - כן, ברור שצריך לשאול בהתאם למה שהוא עונה ;] בנוגע לשאלה השנייה - עדיין חושב על זה :)
 

jontra

New member
3-לא כל כך ברור

לגבי שאלה 3 בהקשר של שאלה 1. אפשר לקבוע את השאלות מראש: נמספר את הכיוונים 1-8. שאלה ראשונה: האם זה כיוונים 1,2,3 או 4? שאלה שנייה: האם זה 1,2 5 או 6? שאלה 3: האם זה 1,3,5,או 7? בסוף אפשר לעשות הצלבה בין התשובות ולמצוא את הפתרון. למשל תשובה של: כן לא כן תתן לנו שהפתרון הוא: 3.
 

ליבליך

New member
שאלה שניה

יש צורך ב-9 שאלות לפחות. במקרה של 8 שאלות, יש 256 תגובות אפשריות של הסוכן, וכל תגובה צריכה להצביע באופן חד ערכי על התשובה הנכונה מבין 8 האפשרויות. כלומר לכל אחת מ-8 האפשרויות צריכות להיות 37 תגובות של הסוכן שמצביעות עליה (אחת כשהוא תמיד אומר אמת, 8 כשהוא משקר באחת מ-8 תשובותיו, ו-28 כשהוא משקר פעמיים). זה דורש 296 תגובות אפשריות לשאלות, ואין לנו כאלה. כמובן שקשה לנסח את 9 השאלות האלה...
 

tkuihehr

New member
האם אפשר לחבר בין השאלה השניה לשלישית?

כלומר לשאול בהתאם לתשובות שלו? [בשאלה של אם הוא משקר פעמיים]
 

ליבליך

New member
לדעתי אין צורך בכך

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