תוכנית פסגה · גרפים מכוונים ובעיית המנעול
תרגיל 6: הרחבה: יותר כפתורים
מגדילים את המנעול לעשרה כפתורים, הספרות 0-9. הקוד נשאר בן שתי ספרות. גם 0 יכול להופיע בתחילת קוד.
הקבוצה הראשונה היא {0, 1, 4, 6, 7}; הקבוצה השנייה היא {2, 3, 5, 8, 9}.
כל זוג ספרות מאותה קבוצה הוא קוד תקף, כולל ספרות זהות. הקוד 72 הוא הקוד התקף היחיד שמחבר בין הקבוצות.
תחילה חושבים - בלי לפתוח את המנעול
- כמה קודים תקפים יש במנעול החדש? חשבו בלי לרשום את כולם.
- כמה לחיצות נחוצות לפחות? הסבירו את החסם.
- כיצד משתנה הגרף? מהן דרגות הכניסה והיציאה, והיכן חייב להתחיל ולהסתיים מסלול אוילר?
- האם אפשר להשיג את החסם? נמקו באמצעות הגרף, ואז מצאו רצף ובדקו אותו.
אחרי החישוב - פתיחת המנעול
שינוי הגרסה מתחיל ניסיון חדש.
כשכבר לא כדאי לספור אחד־אחד
בכל גרסה יש שתי קבוצות זרות, בכל אחת אותו מספר כפתורים. כל זוג סימנים מאותה קבוצה תקף, ויש קוד תקף אחד נוסף מהקבוצה הראשונה לשנייה, ללא קוד בכיוון ההפוך.
| כפתורים בכל קבוצה | סך הכפתורים | מספר הקודים התקפים | מינימום לחיצות - ונימוק |
|---|---|---|---|
| 5 | 10 | ? | ? |
| 10 | 20 | ? | ? |
| m | 2m | ? | ? |
נסחו כלל לכל מספר חיובי m של כפתורים בכל קבוצה. הסבירו מדוע אי אפשר בפחות לחיצות ומדוע אפשר להשיג את החסם, בלי לרשום את כל הקודים או את רצף הלחיצות.
במנעולים הגדולים כל כפתור נושא סימן שונה - אפשר להשתמש גם באותיות. קוד נשאר באורך שני סימנים בלבד.