תוכנית פסגה · גרפים מכוונים ובעיית המנעול
תרגיל 3: המנעול - כמה קודים וכמה לחיצות לפחות?
בדיקת מנעול ניסיוני
למנעול שמונה כפתורים: 1-8. קוד הוא בן שתי ספרות, ומותר שהן יהיו זהות. רק הקודים ברשימה שלמטה תקפים.
אין כפתור אישור: אחרי כל לחיצה, החל מהלחיצה השנייה, המכשיר בודק את שתי הספרות האחרונות. למשל, הרצף 146 בודק את 14 ואז את 46.
צוות הבדיקה רוצה להקליד רצף שיבדוק את כל הקודים התקפים בכמה שפחות לחיצות. מתחילים מזיכרון ריק. במצב הבדיקה המכשיר ממשיך לקלוט לחיצות גם לאחר זיהוי קוד, בלי איפוס בין בדיקות.
אפשר ללחוץ על כל כפתור בכל שלב. קוד שאינו ברשימה אינו מוסיף קוד תקף לבדיקה, אבל הלחיצה נספרת והספרה האחרונה נשארת בזיכרון.
- 35
- 71
- 22
- 64
- 58
- 17
- 33
- 46
- 82
- 11
- 53
- 77
- 28
- 61
- 44
- 85
- 14
- 32
- 67
- 55
- 41
- 88
- 76
- 23
- 47
- 52
- 16
- 83
- 66
- 25
- 74
- 38
- 72
חסם תחתון הוא מספר שמתחתיו אין אפשרות להצליח.
הוכחה שאי אפשר בפחות לחיצות עדיין אינה מוכיחה שאפשר להצליח בדיוק במספר הזה. כדי לקבוע את המינימום נצטרך גם לבנות רצף שמשיג את החסם, או להסביר מדוע אינו ניתן להשגה.