נתונים 10 שקים. בכל אחד מהם נמצאים המון מטבעות. כל המטבעות שוקלים 1 גרם, מלבד שק אחד שהמטבעות בו מזויפים ושוקלים 2 גרם. ברשותך מאזניים דיגיטליים שנותנים משקל מספרי. מהו המספר הקטן ביותר של שקילות שדרוש כדי למצוא את השק המזויף?
| פתרון
|
| ניקח מטבע אחד מהשק הראשון, שניים מהשק השני, שלושה מהשלישי וכן הלאה. אם כל השקים היו אמיתיים היה אמור להיות סכום של 55 (ראו מספר משולשי) ההפרש בין המשקל שיצא לבין 55 הוא השק המזויף (כי כל מטבע שהוצא ממנו מוסיף 1 גרם לסכום הכולל). לפיכך המספר המבוקש הוא 1.
|
|
אותה חידה, אלא שהפעם כל שק יכול להיות מזויף או אמיתי. כמה שקילות דרושות הפעם?
| פתרון
|
הפעם נוציא מטבע אחד מהשק הראשון, שניים מהשני, ארבעה מהשלישי ובאופן כללי  מהשק ה-nי. אילו כל השקים היו אמיתיים, הסכום היה 1023. נסתכל על ההפרש בין המספר שיצא לבין 1023 ונרשום אותו בבסיס בינארי. איפה שהספרה היא 1, סימן שהשק הוא מזויף. לפיכך התשובה היא שוב 1.
|
|