PROFILPELAJAR.COM

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

מגבלות של תורת האינפורמציה

לכל שקילה יש שלוש תוצאות אפשריות, ולכן מספר התוצאות האפשריות ב-a שקילות הוא $3^{a}$ . כדי שהמטבע החריג יהיה ניתן לזיהוי, מספר האפשרויות א-פריורי אינו יכול לעלות על המספר הזה. על מנת שאפשר יהיה לזהות מטבע מזויף אחד מתוך n מטבעות, מוכרח להתקיים $3^{a}\geq n$ אם ידוע שהמטבע החריג קל (או כבד) משאר המטבעות, או $3^{a}\geq 2n$ אם אופי החריגה אינו ידוע.

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

מה אפשר לעשות בשקילה אחת

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

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

(כל בעיה שבה יש שלוש אפשרויות שייכת לאחד הסוגים האלה).

12 מטבעות בשלוש שקילות

בחידה זו נתונים 12 מטבעות, שאחד מהם מזויף - ייתכן שהוא כבד יותר וייתכן שהוא קל יותר. באמצעות שלוש שקילות בלבד במאזני כפות יש למצוא את המטבע המזויף ולקבוע האם הוא קל יותר או כבד יותר ממטבע תקין.

חידה זו הייתה פופולרית במהלך מלחמת העולם השנייה, ולראשונה הופיעה בדפוס בשנת 1945, במאמר מאת האוורד גרוסמן.^[1]

פתרון החידה

נסמן כל אחד מהמטבעות באחד מהסימונים הבאים: "?" כדי לציין שהמטבע עלום (איננו יודעים אם הוא תקין, קל או כבד), "+" כדי לציין שהוא חשוד-ככבד (כלומר הוא כבד או תקין), "-" כדי לציין שהוא חשוד-כקל (כלומר הוא קל או תקין), ו-"0" כדי לציין שהוא תקין. בתחילת התהליך כל המטבעות מקבלים את הסימון "?", משום שאיננו יודעים עליהם דבר.

שקילה ראשונה: מניחים ארבעה מטבעות על כל כף של המאזניים.

שוויון בשקילה הראשונה

אם בשקילה הראשונה הכפות מאוזנות, זו ראיה ששמונת המטבעות שנשקלו כולם תקינים (00000000) והמטבעות שלא נשקלו נותרו עלומים (????).

שקילה שנייה: משווים שלושה מטבעות תקינים כנגד שלושה מטבעות עלומים (000 כנגד ???).

אם בשקילה זו מתקבל שוויון, הרי שהמטבע המזויף הוא המטבע העלום הרביעי, וכדי לזהות האם הוא קל או כבד די להשוות אותו (בשקילה שלישית) למטבע תקין.

אם בשקילה השנייה מתקבל אי-שוויון ??? > 000, הרי שהמטבע המזויף כבד והוא אחד משלושת המטבעות העלומים שהשתתפו בשקילה זו. נסמן אותם ב+++. בשקילה שלישית שוקלים שניים מאלה זה כנגד זה. אם הכפות מאוזנות המטבע הכבד הוא השלישי, ואם אחת מהן כבדה הרי שמונח בה המטבע המזויף.

אם בשקילה השנייה מתקבל האי-שוויון ההפוך ??? < 000, הרי שהמטבע המזויף קל, וההמשך בדיוק באותו אופן.

אי-שוויון בשקילה הראשונה

אם בשקילה הראשונה הכפות אינן מאוזנות, זו ראיה שבכף אחת מונחים מטבעות ++++, ובשנייה ----; ארבעת המטבעות שלא נשקלו הם תקינים: 0000.

שקילה שנייה: מניחים בכל כף שני מטבעות חשודים ככבדים ואחד החשוד כקל (++- כנגד ++-).

אם בשקילה זו מתקבל שוויון, הרי שהמטבע המזויף הוא אחד משני החשודים-כקלים הנותרים; משווים ביניהם (בשקילה שלישית), והקל הוא המזויף.

אחרת, כף אחת כבדה יותר: ++- > ++-. המטבע המזויף הוא או אחד משני החשודים-ככבדים בכף הכבדה, או המטבע החשוד-כקל בכף הקלה (כל השאר תקינים). משווים (בשקילה שלישית) את המטבעות החשודים-ככבדים זה לזה. אם אחד מהם כבד יותר, הוא המזויף; ואם הם שווים המזויף הוא המטבע השלישי.

תרשים זרימה לפתרון החידה

חידה על שתי שקילות עם מטבעות צבעוניים

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

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