חידת לחיצות ידיים

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

לארוחת ערב אצל גברת כהן ובעלה מגיעים ארבעה זוגות אורחים. בכניסה יש המולה רבה ומוחלפות לחיצות יד. לא כולם לוחצים אחד לשני את היד, ובוודאי שאף אחד לא לוחץ לא לעצמו ולא לבן/בת זוגו. אחרי שכולם יושבים לשולחן גברת כהן שואלת את הנוכחים כמה פעמים הם לחצו ידיים ומקבלת מהם 9 תשובות שונות. השאלה: כמה ידיים לחץ מר כהן?

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

לבינתיים, הנה שעשועים בחסות SMBC:


טוב, הדבר הראשון שעושים הוא לשכוח לרגע את מר כהן ולנסות להבין איך סיטואציית לחיצות הידיים בכלל הגיונית. אילו תשובות אנשים בכלל יכולים לתת לשאלה "כמה ידיים לחצת"? מספר שהוא בין 0 ל-8. למה רק 8? כי אדם לא לוחץ ידיים לא לעצמו ולא לבן זוגו. כעת, מכיוון שיש 9 תשובות, אז התשובות הן בהכרח $latex 0,1,2,3,4,5,6,7,8$. אוקיי, נסמן את האנשים על פי המספרים הללו.

כעת אפשר לנסות ולהתחיל לצייר דיאגרמות שמתארות את לחיצות הידיים. אם נתחיל מ-1 נגלה שיש לנו המון חופש פעולה וזה מבלבל ואנחנו לא רוצים את זה – ההפך, אנחנו רוצים כמה שפחות חופש פעולה – לראות מה מתחייב מהנתונים. אז בואו נתחיל מ-8. נניח שהוא לחץ ידיים לכל האנשים מ-0 ועד 7, אז… היי, רגע, איך הוא יכל ללחוץ יד למר 0 אם מר 0 בכלל לא לחץ ידיים? מסקנה, מר 8 היה חייב ללחוץ את ידי האדם היחיד שלא אמר כלום – גברת כהן. בנוסף לכך, הוא לחץ את ידי כל יתר האנשים.

בואו נעבור כעת למר 7. מר 7 לחץ את היד של מר 8; למי עוד הוא יכול ללחוץ ידיים? לא למר 0, אבל גם לא למר 1, שהרי מר 1 כבר לחץ את היד של מר 8 ו"נשרף"! ומר 7 חייב ללחוץ את הידיים של עוד 6 אנשים. מבין הלא שרופים יש לנו את $latex 2,3,4,5,6$, שהם רק חמישה; לכן שוב, נלחצה ידה של גברת כהן.

אני מניח שהעיקרון ברור כעת; למרות זאת, העסק יכול להיות מבלבל למדי ומי שהתבלבל, יכול לנקוט בטריק העתיק ביותר בפתרון חידות ולהסתכל על מקרה פשוט יותר. האם אנחנו מצפים שהחידה תשתנה מהותית אם במקום שיבואו לבקר ארבעה זוגות, יבוא לבקר רק זוג אחד? אולי היא תשתנה, אבל על פניו זה לא סביר כל כך. אז בואו קודם כל נפתור את המקרה הזה. כאן יש לנו את האנשים $latex 0,1,2$ ואת גברת כהן; וברור שמר 2 לחץ את ידו של מר 1, ואת ידה של גברת כהן. אז לצייר את "דיאגרמת לחיצות הידיים" במקרה הזה, זה קל, ואפשר כבר לחשוב הלאה – איך המידע הזה עוזר לנו לדעת כמה ידיים לחץ מר כהן?

ובכן, אנחנו יודעים שמר 2 לחץ ידיים לגברת כהן, אז הוא לא מר כהן; יותר מזה, הוא לחץ יד עם מר 1, אז הוא גם לא בן זוגו של מר 1 (כן, תראו איך אנחנו מסתבכים עם השימוש החופשי שלנו במגדר…), ולכן מר 2 הוא בהכרח בן הזוג של מר 0. לכן נשאר רק מר 1, וזהו מר כהן.

זה כבר נותן לנו רעיון איך לפתור את המקרה המסובך יותר (אני מקווה). מר 8 לחץ ידיים לגברת כהן, אז הוא לא מר כהן, והאדם היחיד שהוא לא לחץ את ידו הוא מר 0, אז הם בני זוג, ומרגע זה שניהם "נשרפו" מבחינתנו. עברנו למר 7 – הוא לחץ ידיים לכל מי שנשאר פרט למר 1, ולכן שניהם בני זוג. ומר 6? לחץ לכל מי שנשאר פרט למר 2. ומר 5? לחץ לכל מי שנשאר פרט למר 3. ומר 4? או, הנה, עלינו על מר כהן. מר 4 לחץ ידיים לכל המרים שלפניו – מר 8, מר 7, מר 6 ומר 5. בנוסף, ארבעת אלו הם בני הזוג של מר 0, מר 1, מר 2 ומר 3; לכן למר 4 נותר רק להיות בן הזוג של גברת כהן – כלומר, הוא מר כהן המדובר. והנה כך הפתרון נובע מאליו.

ומה קורה אם באים $latex n$ זוגות? ראינו כי כאשר $latex n=1$ אז התשובה היא "1"; וראינו כי כאשר $latex n=4$, אז התשובה היא "4". אני מותיר לכם את המלאכה המורכבת של ניחוש והוכחת התשובה עבור המקרה הכללי…

19 תגובות בנושא “חידת לחיצות ידיים”

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

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

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

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

  4. ובכן, אמרתי בתחילת הפוסט:

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

    גם אופן הפתרון אלגנטי לטעמי.

  5. אני מכיר את החידה הזו בניסוח למבוגרים בלבד

    לעוזי: אכן x וn-x הם תמיד זוג, וזה מספיק להוכיח

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

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

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

    אני חושב שהניסוח שלי יותר פשוט אבל אולי זה רק כי הוא שלי.

  9. בלי קשר לפוסט –

    1) היכן ניתן להציע הצעות אודות נושאים מתמטיים לכתיבה? (כלומר נניח ויש לי נושא שאני רוצה שתכתוב עליו , היכן אני אמור לשלוח את הבקשה?)

    2) לגדי – מה הכינוי שלך בפורום?

    תודה 🙂

  10. פתרתי קצת אחרת מהדרך שהצעת:
    בהתחלה אכן שידכתי את מר/גברת 0 עם גברת/מר שמונה, ומתוך כך את 1 עם 7, את 2 עם 6 וכן הלאה. ציירתי תרשים עם קווים בין כל מי שלחץ למי שנלחץ, וחיפשתי מה יהיה המספר היחיד שיופיע פעמיים, שהוא גברת כהן (הרי יש 10 לוחצים, ורק 9 תשובות אפשריות, שניתנו על ידי כל מי שאיננו גברת כהן, ולכן בהכרח תשובתה שלה תהיה זהה לאחד הלוחצים). המספר היחיד שהופיע פעמיים הוא 4, ובן זוגו הוא ה-4 השני – מר כהן.

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *