בעיות שקילה

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

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

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

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

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

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

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

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

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

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

חוקרים רבים, כגון מרטלי וגנון במאמרם "הפרד ומשוך כדי למצוא זיוף" מכתב העת College Mathematics Journal  משנת 97', נעזרים בתוכניות מחשב כדי למצוא את המספר הגדול ביותר של מטבעות שאפשר לשקול ב-n שקילות על מאזני כפות. אם משתמשים באלגוריתם הפשוט שהצגנו בתחילת הכתבה, מספר המטבעות הוא 3^n-1. אם משתמשים באלגוריתם השני, מספר המטבעות יהיה: 3ⁿ-3)/2).

בעיות במשקל רגיל

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

הפתרון הוא פשוט: ניקח מטבע אחד מהערימה הראשונה, שני מטבעות מהערימה השניה, שלושה מטבעות מהערימה השלישית וכך הלאה, עד עשרה מטבעות מהערימה העשירית. את כל המטבעות האלה נשקול ביחד, ולפי המשקל שהתקבל נדע איזו ערימה היתה המזויפת. (איך?)

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

במבט ראשון נראה שאפשר להשתמש בשש המשקולות 1 ק"ג, 2 ק"ג, 4 ק"ג, 8 ק"ג, 16 ק"ג ו-32 ק"ג כדי לשקול כל חפץ שמשקלו נע בין 1 ק"ג ל-40 ק"ג. לדוגמה, אם נניח שק של תפוחי אדמה שמשקלו 11 ק"ג על כף אחת של המאזניים, נוכל לאזן אותו בעזרת המשקולות של 1 ק"ג, 2 ק"ג ו-8 ק"ג שנשים על הכף השנייה של המאזניים.

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

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

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

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

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

יוסי ומיכל אלרן
מכון דוידסון לחינוך מדעי
מכון ויצמן למדע

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