חידה

[טיקטי]

חידה

13 גנבים גנבו אוצר הם שמים אותו בתיבה הם רוצים שיהיה אפשר לפתוח את התיבה רק אים הרוב רוצה(7) לשם כך הם פונים למנעולן ומבקשים ממנו שישים כמה מנעולים שהוא רוצה (למנעול יכולים להיות כמה מפתחות שפותחים אותו אבל מפתח יכול לפתוח רק מנעול אחד) כמה מנעולים ישים המנעולן ואיך יחלק את המפתחות בין 13 האנשים?

 

[שדון קטן]

יהיו שבעה מנעולים זהים וכל אחד

מהגנבים יקבל מפתח (שיכול לפתוח כל אחד מהמנעולים)...

 

[Fingertip]

../images/Emo128.gif

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

 

[שדון קטן]

אההה... אבל אני התכוונתי:

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

 

[ילדת דווקא]

שדון יקר....

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

 

[שדון קטן]

או קיי סבבה.. מצטער..

 

[ילדת דווקא]

אין על מה ../images/Emo140.gif

 

[טיקטי]

הקפצה

 

[Belgarath]

../images/Emo62.gifאני בטח מגזים אבל ...

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

 

[טלמון סילבר]

לא העתקתי ממך ../images/Emo13.gif

 

[טלמון סילבר]

../images/Emo62.gif פתרון תיאורטי

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

 

[טיקטי]

יפה מאד לשניכם