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

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

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

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

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

טוב, הדבר הראשון שעושים הוא לשכוח לרגע את מר כהן ולנסות להבין איך סיטואציית לחיצות הידיים בכלל הגיונית. אילו תשובות אנשים בכלל יכולים לתת לשאלה “כמה ידיים לחצת”? מספר שהוא בין 0 ל-8. למה רק 8? כי אדם לא לוחץ ידיים לא לעצמו ולא לבן זוגו. כעת, מכיוון שיש 9 תשובות, אז התשובות הן בהכרח \( 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 אנשים. מבין הלא שרופים יש לנו את \( 2,3,4,5,6 \), שהם רק חמישה; לכן שוב, נלחצה ידה של גברת כהן.

אני מניח שהעיקרון ברור כעת; למרות זאת, העסק יכול להיות מבלבל למדי ומי שהתבלבל, יכול לנקוט בטריק העתיק ביותר בפתרון חידות ולהסתכל על מקרה פשוט יותר. האם אנחנו מצפים שהחידה תשתנה מהותית אם במקום שיבואו לבקר ארבעה זוגות, יבוא לבקר רק זוג אחד? אולי היא תשתנה, אבל על פניו זה לא סביר כל כך. אז בואו קודם כל נפתור את המקרה הזה. כאן יש לנו את האנשים \( 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 נותר רק להיות בן הזוג של גברת כהן - כלומר, הוא מר כהן המדובר. והנה כך הפתרון נובע מאליו.

ומה קורה אם באים \( n \) זוגות? ראינו כי כאשר \( n=1 \) אז התשובה היא “1”; וראינו כי כאשר \( n=4 \), אז התשובה היא “4”. אני מותיר לכם את המלאכה המורכבת של ניחוש והוכחת התשובה עבור המקרה הכללי…