בבלוגריתמוס 6 הצבתי חידה שקרמתית: הבובילים והגוגלים הם מסוגים מנוגדים: דוברי אמת או דוברי שקר. עשרה אנשים שנפגשו הצהירו "שאר התשעה הם גוגלים!" מה האפשרויות?
נניח שהגוגלים הם שקרנים. במקרה כזה לא יכולים להיות שני דוברי אמת בין העשרה, כי אז כל אחד מהם היה כולל את רעו בשקרנים. גם לא ייתכן שכולם שקרנים, כי אז כולם אומרים משפטי אמת. לכן, אם הגוגלים שקרנים – אזי ישנו דובר אמת אחד ויחיד!
אם הגוגלים הם דוברי אמת, ואכן יש בין העשרה דובר אמת אחד, הרי שגם כל השאר דוברי אמת כפי שהוא מעיד עליהם. לכן, אם יש דובר שקר יחיד – כולם שקרנים שאומרים על השאר שהם דוברי אמת, ולכן התשובה היא, "או שכולם שקרנים או שכולם דוברי אמת או שיש בדיוק דובר אמת יחיד".
לחלקכם הפתרון נשמע אולי מאכזב, כי הוא כולל אפשרויות רבות, אך לבעיות רבות יש פתרונות מרובים ולעתים זה בדיוק סוד קסמן. גם למשוואות ממעלה שנייה יכולים להיות פתרון יחיד, שני פתרונות, או פתרונות שאינם במספרים ממשיים אלא במספרים מרוכבים. כל פתרון "מרובה" מצמצם בדרך כלל מאוד את מספר האפשרויות שהיו לנו לפני שהצגנו את פרטי הבעיה.
במקרה שלנו, כשרק נפגשו יכלו העשרה להתחלק ל-1,024 מִיוּנים שונים, כי כל אחד היה יכול להשתייך לכל אחד משני השבטים. כלומר היו 210 אפשרויות! הפתרון לעיל מותיר אותנו עם 12 מיונים אפשריים בלבד – קצת יותר מאחוז!
לעתים הפתרון המרובה הוא זמני, כי נוסף לו מידע שמצמצם את האפשרויות או משנה אותן. לדוגמה, נניח שהדובר השלישי הוסיף בסוף המשפט את המילה "מלבדי". מה היה קורה לפתרונות?
נדון בזאת בבלוגריתמוס הבא.
בהצלחה,
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
