שלום לכם,

תודה על פתרון החידה הקודמת!  אכן היו אלה ספרות רומיות. עזרתם לי מאוד, והאיטלקים היו מרוצים.

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

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

לגמדים יש לילה אחד לחשוב איך יוכלו לצאת מהצרה בצורה הטובה ביותר. התוכלו לעזור ולומר מהו מספר הגמדים הגבוה ביותר של גמדים שאפשר להציל מתוך המאה, ואיך הם יעשו את זה?

בתקווה שהשלווה והשמחה יחזרו לעיירה,

סקובידו

(תודה לאמונה ארד על החידה!)

                                                     תמונה: Shutterstock

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

30 תגובות

  • בני צור

    תשובה לחידה 43

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

  • עטרה

    רק גמד אחד בסכנה

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

  • רמי

    פתרון פשוט

    יהיו n גמדים עם m צבעי כובעים. נסמן את הכובעים במספרים מ 0 ועד (m-1) .
    גמד אחרון בטור (גמד Dn) יחשב את סכום ערכי הצבעים של הכובעים של הגמדים מגמד (n-1) ועד גמד 1, ויחשב את מודולו m של התוצאה. הוא ידווח על המספר שקיבל.
    כל גמד אחר (Di) יחשב את סכום ערכי הכובעים של כל הגמדים למעט של עצמו ושל הגמד Dn. כעת יחשב מודולו m של התוצאה, יפחית מהערך ש Dn דיווח עליו את המספר שקיבל ועל התוצאה שוב יבצע מודולו m. המספר שקיבל הוא צבע הכובע שלו!!

  • עטרה

  • רמי

    ולך התודה

    פיתחת יפה מאוד את חידת הגמדים.
    איתגרת אותנו כהלכה.

  • עטרה

    חידה מעניינת - רק 2 גמדים בסכנה, עבור כל ערך של C

    הגמדים מצאו שיטה, שבה לכל היותר 2 גמדים נמצאים בסכנה, בלי תלות במספר הצבעים של הכובעים. מהי השיטה של הגמדים?

  • רמי

    שאלות להבהרה

    1) האם גם בשאלה זו מדובר על 100 גמדים, או לכל מספר סופי של גמדים?
    2) האם מותר לגמד האחרון להכריז על צבע לא קיים? למשל אם יש 30 צבעים, הוא מדווח על 42 למשל.
    3) במקרה של 100 גמדים, האם השיטה אמורה להתאים גם למצב של 99 או 100 צבעים?

  • עטרה

    תשובות

    1) כן. השיטה מתאימה לכל מספר טבעי של גמדים, ולכל מספר טבעי של צבעים.
    2) לא. (אם היה מותר אז הפתרון היה מאוד פשוט.)
    3) כן. אין תלות בין מספר הגמדים ומספר הצבעים.

  • עטרה

    חידת 27 צבעים

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

  • עטרה

    חידת 10 צבעים

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

  • עטרה

    בעצם רק 3 גמדים בסכנה

    הגמדים מצאו שיטה, שבה רק 3 גמדים נמצאים בסכנה, וכל השאר לא נפגעים.

  • רמי

    פתרון ל 10 כובעים תוך סיכון 3 גמדים בלבד

    3 הגמדים האחרונים מחשבים זוגיות של כובעי הגמדים מגמד 1 עד וכולל גמד 97.
    גמד 100 (אחרון) ידווח על זוגיות מספר הכובעים בצבעים 1,0 ו-2 ע"י דיווח מספר בין 0 ל 7 , כשביט 0 במספר עבור צבע 1, ביט 1 לצבע 1 וביט 2 לצבע 2. [לדוגמא דיווח 6 מסמן לגמדים כי מספר הכובעים מצבע 1 ו-2 הוא אי זוגי, ומספר הכובעים מצבע 0 הוא זוגי]
    גמד 99 (לפני האחרון) ידווח על זוגיות מספר הכובעים בצבעים 4,3 ו-5 ע"י דיווח מספר בין 0 ל 7 כנ"ל.
    גמד 98 ידווח על זוגיות מספר הכובעים בצבעים 7,6 ו-8 ע"י דיווח מספר בין 0 ל 7 כנ"ל.
    זוגיות מספר הכובעים מצבע 9 יוסק מהנ"ל.
    גמד Di יחשב את זוגיות מספר הכובעים לצבעיהם של הגמדים שלפניו תוך התחשבות בנתוני 3 הגמדים הראשונים ודיווחי כל הגמדים האחרים שעמדו מאחוריו.

  • עטרה

    רעיון מצוין!

    רעיון יפה. לא חשבתי על הכיוון הזה.
    אני מצאתי שיטה אחרת, שמתאימה גם לחידה שלמעלה (27 צבעים).

  • עדי

    תשובה

    אם הגמד האחרון (זה שרואה את כל הכובעים ) רואה מספר זוגי של כובעים שחורים הוא אומר שחור ואם אי זוגי אז הוא אומר לבן. יש לו סיכוי של 50%. לפי התשובה הזאת כל אחד מהגמדים ינחש נכון :למשל אם הוא אמר שחור והגמד שבא אחריו יראה 38 כובעים שחורים הכובע שלו לבן (אם הוא היה שחור אז האחרון היה רואה מספר אי זוגי של כובעים)

  • רמי

    גמד 97

    על פי דוגמתך שגמד אחרון אמר שחור על מספר זוגי של כובעים,
    אם נסמן גמד אחרון ב 100, והגמד שלפניו ב 99,
    אז אם גמד 97 סופר 36 כובעים שחורים, האם כובעו לבן? או אולי שחור?
    יכול להיות מצב בו גמדים 99 ו98 כובעיהם שחורים, ואז גמד 97 כובעו לבן,
    ומצב אחר בו גמד 99 כובעו לבן וגמד 98 כובעו שחור, ואז גמד 97 כובעו שחור.
    לפי דעתי כל גמד צריך להתחשב, מעבר לספירת הכובעים שלפניו, גם במה שאמרו הגמדים שעמדו אחריו.

  • עדי

  • עדי

    נכון

    כל גמד מחבר את מספר הכובעים השחורים שלפניו למספר הפעמים שאמרו שחור (חוץ מהפעם של גמד 100) אם התוצאה מתאימה לצבע(תוצאה זוגית - שחור, אי זוגית - לבן) אז צבעו לבן, אם היא לא אז צבעו שחור.

  • רמי

    חידת כובעים ב 3 צבעים

    בדומה לחידה המקורית גם כאן יש 100 גמדים במצוקה, כי הענק הגיח והודיע על יום הדין שיגיע בעוד 3 ימים.
    כך כתוב בספרים העתיקים על יום הדין :
    1) הגמדים יועמדו בטור אחד אחרי השני. הגמד האחרון יראה את ראשי כל הגמדים שלפניו, הגמד הראשון לא יראה אף ראש של גמד.
    2) הענק יסיר את כובעו האדום של כל גמד, ויחבוש במקומו כובע בצבע אקראי מאחד הצבעים הבאים : ירוק, שחור או לבן.
    שום גמד לא יוכל לראות את הכובע שעל ראשו.
    3) בסיום תהליך החבישה, יתבקש כל גמד (מהגמד האחרון שרואה את כול השאר, ועד הראשון שאין לפניו אף גמד) לנחש את צבע הכובע שעל ראשו. כל גמד שינחש לא נכון יוצא מהשורה וייענש כהוגן לפני כל הגמדים, ואילו גמד שיצליח לומר את הצבע הנכון יקבל חנינה.
    הגמדים שומעים את ניחושי חבריהם.

    לגמדים יש 3 לילות לחשוב איך יוכלו לצאת מהצרה בצורה הטובה ביותר. התוכלו לעזור ולומר מהו המספר הגבוה ביותר של גמדים שאפשר למנוע את הענשתם מתוך המאה, ואיך הם יעשו את זה?

  • עטרה

    פתרון אופטימלי - רק גמד אחד בסכנה

    הגמדים קובעים ביניהם מראש התאמה כלשהי בין קבוצת הצבעים {ירוק, שחור, לבן} ובין קבוצת המספרים {0, 1, 2}. נניח שהם קובעים את ההתאמה הבאה: ירוק=0, שחור=1, לבן=2.
    הגמד DL הוא הגמד האחרון בטור. הגמד DL יתעלם מהכובעים הירוקים, שמתאימים למספר 0. הגמד DL יספור את הכובעים השחורים ואת הכובעים הלבנים של כל הגמדים, מלבד הכובע של עצמו שהוא אינו יודע מה הצבע שלו. הגמד DL יפחית ממספר הכובעים השחורים את מספר הכובעים הלבנים, יחלק את ההפרש ב 3, ויבדוק מה השארית. (אם השארית היא מספר שלילי, אז מגדירים 2=1-, 2=1-.) נקרא לשארית הזאת RL. הגמד DL יכריז את הצבע המתאים לשארית שהתקבלה. כל אחד מהגמדים יבדוק מה המספר המתאים למה שהכריז הגמד DL, וכך הוא ידע מהו המספר RL.
    יהא Di גמד כלשהו, שאינו הגמד DL. הגמד Di יספור את מספר הכובעים השחורים ואת מספר הכובעים הלבנים של כל הגמדים, מלבד הכובע של עצמו והכובע של הגמד DL. (אם הגמד Di רואה רק את הגמדים שלפניו ולא את אלו שאחריו, אז הוא יספור כמה כובעים שחורים הוא רואה לפניו, וכמה פעמים הגמדים שאחריו (מלבד הגמד DL) אמרו "שחור", ויחבר את המספרים, ובאותו אופן עבור הכובעים הלבנים.) הגמד Di יפחית ממספר הכובעים השחורים את מספר הכובעים הלבנים, יחלק את ההפרש ב 3, ויבדוק מה השארית. נקרא לשארית הזאת Ri. הגמד Di יחשב את RL-Ri) mod 3). הצבע המתאים לשארית שהתקבלה הוא הצבע של הכובע של הגמד Di.

  • רמי

    מדהים!!

    רעיון מעולה. פתרון יפהפה.

    בפתרון שלי סיכנתי שני גמדים:
    גמד אחרון (100) דיווח על שארית מספר הגמדים עם כובעים ירוקים מהגמד 98 ועד 1, בחלוקה ב 3.
    גמד 99 דיווח על שארית מספר הגמדים עם כובעים שחורים מגמד 98 ועד 1, בחלוקה ב 3.

  • טל ברק

    פתרון

    הגמד הראשון בשורה יגיד את הצבע של הגמד מאחוריו ואז יש חמישים אחוז שהוא צודק.
    בעוד הגמד שאחריו יגיד את הצבע שהגמד הראשון אמר, ואם מאחוריו יש גמד עם כובע באותו צבע לדוגמה לבן יגיד-הכובע בצבע לבן וזה שאחריו יבין שהכובע שלו לבן.
    ואילו מאחוריו גמד עם כובע בצבע אחר-שחור יגיד הכובע בצבע לבן ולא שחור וכך יבין הגמד מאחוריו שצבע הכובע שלו שחור וכן הלאה.
    לכן ניתן להציל בין 99-100

  • מומחה מצוות מכון דוידסוןפזיה

    לא בטוח שהענק ירשה

    לא בטוח שהענק ירשה לגמדים לומר יותר מאשר "שחור" או "לבן". בדרך שהציעו רמי ושי ניתן להציל בין 99 ל-100 (כפי שהצלחת אתה), בלי לומר מילים נוספות.

  • משי

    פתרון לחידה

    כל הגמדים ישבו והחליטו על גמד אחד שיגיד לכל שאר הגמדים את צבע הכובע שעל ראשיהם לפי היידים שלו מספר זוגי (2,4) יסמן כובע לבן מספר אי זוגי (1,3,5) יסמל כובע שחור ולבסוף ימונה עוד גמד שיסמן בידיו לגמד האחרון (בדיוק על אותו עיקרון שעשה אותו גמד לשאר הגמדים)
    וככה יחזור השלום לעיירה וכול הגמדים ישראו בריאים ושלמים:)

  • מומחה מצוות מכון דוידסוןפזיה

    הצלת את כולם!

    בעצם הרעיון של החידה שמותר לגמדים לומר רק שחור או לבן ולא להשתמש בסימנים נוספים, אבל אם הם יצליחו להתחכם (לסמן בידיים בלי שהענק יראה) ולהציל את כולם אשמח מאד :)

  • רמי

    פתרון דומה

    כל גמד סופר את כל הכובעים השחורים שהוא רואה לפניו , מוסיף את מספר הגמדים שאמרו לפניו "כובע שחור" , אם המספר זוגי, ידווח "כובע לבן", אחרת ידווח "כובע שחור".
    הגמד הראשון עלול להפגע בהסתברות של 50%. הוא מקריב את עצמו להצלת כל יתר הגמדים.
    שאר 99 הגמדים ינצלו בוודאות.

  • מומחה מצוות מכון דוידסוןפזיה

  • שי

    אפשרות לפתרון

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

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

  • מומחה מצוות מכון דוידסוןפזיה

  • רמי

    אני רק שאלה

    אם הגמדים יעמדו בטור, כיצד כולם יראו את כולם? אולי הם בשורה ומותר להם לסובב את הראש?
    אולי הכוונה שכל גמד רואה את כל הגמדים שלפניו ולא את כל הגמדים?
    האם יש סדר בו הגמדים צריכים לתת תשובה?
    אם הם בטור, האם הגמד האחרון או הראשון מתחיל?
    אחרת, האם הם יכולים לבחור את הסדר? האם הענק בוחר באקראי?
    האם כולם צריכים לתת תשובה סימולטנית?

  • מומחה מצוות מכון דוידסוןפזיה

    אני רק תשובה :)

    ובכן, יש כמה אפשרויות: 1. מותר להם לסובב את הראש כדי שיוכלו לראות את *כל השאר*. הם לא יודעים מראש מה יהיה הסדר בו יועמדו. התשובה לא ניתנת סימולטנית, אלא אחד אחרי השני. 2. לצורך הפיתרון אפשר להסתפק גם בזה: הגמדים עומדים בטור כך שכל גמד יכול לראות רק את *אלו שלפניו*, אבל לשמוע גם את אלו שמאחוריו, הענק מתחיל לשאול את הגמד האחרון בטור (המסודר לפי הסדר שיבחר הענק) ומתקדם הלאה לפי הסדר מהאחרון עד לראשון.