חידת שקילה

מאזני כפות פשוטים המשמשים לשקילת חפצים בהשוואה לחפצים אחרים

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

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

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

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

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

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

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

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

12 מטבעות

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

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

פתרון החידה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

לקריאה נוספת

• T. H. O'Beirne, Puzzles and Paradoxes: Fascinating Excursions in Recreational Mathematics, Dover, 1984, pp. 20-32

קישורים חיצוניים

• דוד שי, מאזני כפות ומטבעות מזויפים

• Richard K. Guy and Richard J. Nowakowski, Coin-Weighing Problems, The American Mathematical Monthly Vol. 102, No. 2 (Feb. 1995), pp. 164-167

הערות שוליים

ערך זה הוא יתום, כלומר אין ערכים במכלול שמקשרים אליו. אתם מוזמנים לתרום למכלול ולקשר אליו מכמה מהערכים שמכילים את המונח "חידת שקילה".

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] חידת שקילה25200354