מחפש אמת מתמטית בחידות מטבעות מזויפים

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

פאזל 1

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

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

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

שימו לב שזה עובד גם אם יש שלושה בקבוצה הבלתי שקולה, אז יכולנו להתחיל עם תשעה מטבעות. לפי ההיגיון הזה, והחל משלושה מטבעות, על כל שקילה נוספת נוכל למצוא את המטבע הקל בפי שלושה ממספר המטבעות שהיו לנו בעבר. הנוסחה שנותנת לנו את המספר המרבי של מטבעות n in w שקילות הוא אפוא n = 3^w.

פאזל 2

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

1. מצא את המטבע הרע בשלוש שקילות.

2. מהו המספר המרבי של מטבעות שעבורם תוכל למצוא את המטבע הרע בארבע שקילות? תאר כיצד תמצא את המטבע המזויף.

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

התחל בשקלול של 4 מטבעות מול 4 מטבעות.

מקרה 1: אם לא מאוזן, עבור השקילה השנייה, שים 2 כל אחד מהצד הכבד יותר משני צידי המשקל יחד עם 1 כל אחד מהצד הקל יותר.

1א: אם לא מאוזן, המטבע הגרוע הוא או 2 המטבעות שעדיין בצד הכבד או המטבע היחיד שעדיין בצד הקל.

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

1ב: אם השקילה השנייה מאוזנת, המטבע הגרוע הוא אחד מהשניים שאינם בשימוש מהצד הקל יותר של השקילה הראשונה.

שקלו אותם אחד נגד השני, הקל יותר גרוע.

מקרה 2: אם מאוזן, המטבע הרע הוא אחד מ-5 שנותרו. שקלו 3 מאלו מול כל 3 שנשקלו כבר (שידוע [כטובים]).

מקרה 2א: אם לא מאוזן, אתה יודע שהמטבע הרע הוא אחד מהשלושה האלה ואם הוא קל או כבד.

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

מקרה 2ב: אם השקילה השנייה מאוזנת, המטבע הרע הוא אחד מ-2 הנותרים.

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

טד המשיך גם והראה כי המספר המרבי של מטבעות עבור ארבע שקילות הוא 40. הנוסחה עבור פאזל זה היא: n = (3^w − 1)/2.

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

פאזל 3

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

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

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

תאר לעצמך שאתה בלש חוקר פגע וברח במדינה זעירה שלמכוניותיה יש לוחיות רישוי דו ספרתיות תוך שימוש רק בספרות 0, 1 ו-2. שלושה אנשים, A, B ו-C, צפו באירוע. שניים מהם תמיד עונים נכון על שאלה משלוש, ואחד נותן תשובות אקראיות לחלוטין. אתה לא יודע מי המשיב האקראי. אתה צריך לשאול כל אחד מהם שאלה אחת בת שלוש בחירות ואז לבחור את זה שבהחלט דובר אמת כדי לקבל מידע נוסף.

הנה איך אתה עושה את זה. שאל את A אם הספרה הראשונה היא 0, 1 או 2. נניח ש-A אומר 2. שאל את B אם הספרה השנייה היא 0, 1 או 2. נניח ש-B אומר 1. לאחר מכן בקש מ-C לבחור בין שלושת ההצהרות הללו:

• רק א' דובר אמת.
• רק ב' דובר אמת.
• שניהם דוברים אמת.

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

הנה איך לתרגם את הסיפור הזה בחזרה לפאזל שלנו. הסולמות הם A, B ו-C. ניתן לתרגם את שתי הספרות של לוחית הרישוי למטבעות באופן הבא: 01 הוא מטבע 1, 02 הוא מטבע 2, 10 הוא מטבע 3, 11 הוא מטבע 4, 12 הוא מטבע 5, 20 הוא מטבע 6, 21 הוא מטבע 7 ו-22 הוא מטבע 8. קוראים נבונים יזהו שזו מערכת המספרים הבסיסית 3 (או השלישית). שים לב גם שיש מספר אפשרי נוסף 00, שבו אתה יכול להשתמש עבור מטבע תשיעי שגם עבורו טכניקה זו תעבוד, כמו בפאזל 1.

עבור השקילה הראשונה, אתה מחלק את המטבעות בספרה הראשונה שלהם (בסיס 3), כך ששלוש הקבוצות שלך יהיו מטבעות [1, 2], [3, 4, 5] ו- [6, 7, 8]. שקלו [3, 4, 5] כנגד [6, 7, 8] בסולם A. אם A עובד היטב, תהיה לך קבוצת הספרות הראשונה הנכונה כמו בפאזל 1. באופן דומה, עבור השקילה השנייה בסולם B הקבוצות שלך יהיו אלה עם אותה ספרה שנייה: [1, 4, 7], [2, 5, 8] ו-[3, 6]. אם B עובד טוב, תהיה לך הספרה השנייה הנכונה. עבור השקילה השלישית, בסולם C, אתה שוקל את הקבוצה ש-A זיהה מול הקבוצה ש-B עשתה. בעקבות הדוגמה שלנו, עבור 21, הקבוצות יהיו [6, 7, 8] ו-[1, 4, 7]. לא ניתן לשים מטבע 7 משני הצדדים בו-זמנית, אז אנו משאירים אותו בחוץ ומשקולים [6, 8] ו-[1, 4] זה מול זה. שימו לב שאם A ו-B שניהם אמינים, אז 7 היא למעשה התשובה הנכונה, ולא משנה איזה צד יוצא קל יותר ב-C. אם במקרה השקילה ב-C מאוזנת, אז כל שלושת המאזניים מסכימים, ו יש לך את התשובה שלך (מטבע 7) בשלוש שקילות בלבד. אם A אמין ו-B לא, המטבע המצית נמצא ב-[6, 8], שסולם C יאשר, ואם B אמין ו-A לא, המטבע המצית נמצא ב-[1, 4], איזה סולם C גם יאשר.

אז בשלוש שקילות זיהינו את המטבע הקל או צמצמנו אותו לקבוצה של שניים, וזיהינו גם סולם עובד. השקילה הרביעית בסולם A או בסקאלה B (על פי סולם C הסכים איתו) תעשה את השאר.

הפתרון הזה נראה לי יפה להפליא!

ניתן להכליל שיטה זו כדי למצוא את המטבע הקל בין 3^2x מטבעות ב-3x + 1 שקילות עם סט מאזני האיזון הנתון. לפיכך, אתה צריך שבע שקילות עבור 81 מטבעות. למספרים גדולים יותר של מטבעות (>~1,000), פתרון חזק עוד יותר קיים.

פאזל 4

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

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

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

שנית, אם תקבל תוצאה מאוזנת (נניח המטבע המיוחד A מאזן מטבע B), תוכל לשלב את המטבעות המאוזנים ולשקלל אותם מול שני מטבעות נוספים, C ו-D. אם הם לא מאוזנים, יש לך את התשובה; אחרת, הכפלת כעת את מספר המטבעות הדומים, מה שעשוי לעזור לך לקבל תשובה לא מאוזנת בשקילה הבאה. אתה יכול גם לבצע תהליך זה הפוך עם מספרי מטבעות שהם בחזקת שתיים (4, 8 וכו') אם יש לך תוצאה ראשונית לא מאוזנת כפי שניתן לראות בפתרון הבא.

להלן כל הנוהל שיכול לזהות את סוג המטבע המיוחד א' בכל המקרים בשלוש שקילות. (B, C ו-D הם שלושה מטבעות המונחים באותו צד של A בשקילה 1 (W1); X ו-Y הם שני המטבעות שאינם בשימוש ב-W1.)

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

באשר להכללה, אשאיר לכם לראות אם אותה שיטה עובדת למציאת סוג מטבע מיוחד בין 32 מטבעות, מתוכם 16 כבדים ו-16 קלים.

פאזל 5

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

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

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

שלושה מטבעות: רק מטבע קל אחד. נדרשת שקילה אחת לכל פאזל 1.

ארבעה מטבעות: רק מטבע קל אחד. נדרשת שקילה אחת נוספת, אז w = 2.

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

אם נשקול אחד נגד אחד, אז אנחנו יכולים לקבל:

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

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

זה מוכח עבור:

שישה מטבעות: אחד עד שניים מטבעות קלים; w = 4.

שבעה מטבעות: אחד עד שלושה מטבעות קלים; w = 5.

שמונה מטבעות: אחד עד שלושה מטבעות קלים; w = 6. לפתרון זה מבנה פשוט:

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

מצטערים, הרצף שלנו של 0, 0, 1, 2, 3, 4, 5, 6 בהחלט לא מספיק מעניין כדי להגיש את אנציקלופדיה מקוונת של רצפים שלמים!

As יונאס טוגרסן קיילסטדלי ציין, נראה שהפתרון הוא w = n − 2 עבור מספרים קטנים, אך לא הוכחנו שזה לא ישתנה עבור מספרים גדולים יותר. בכמה n, שימוש במספר שקילות מטבע עשוי להתחיל להצליח יותר, או יותר שקילות מאשר n - ייתכן שיידרשו 2. אנחנו יכולים פשוט להכליל את הפתרון לשמונה מטבעות לכל החזקות של 2, נתינה n − 2 כגבול עליון למספר השקילות עבור כל החזקות של 2.

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

תודה לכל מי שהשתתף. פרס Insights לחודש זה מוענק במשותף לטד וריינר aus dem Spring. מזל טוב!

נתראה בפעם הבאה לחדשים תובנה.