- This topic has 3 תגובות, 3 משתתפים, and was last updated לפני 20 שנים, חודש 1 by
.
-
תגובות
-
החידה המקורית מדברת על המטבעות האמריקנים:
סנט, 5 סנט, 10 סנט, 25 סנט, חצי דולר, ודולר.
אפשר לשלם דולר במטבע בודד, שני מטבעות, שלושה (איך?), ארבעה, …
מהו המספר הראשון בו אי אפשר לשלם דולר?החידוד לשאלה המקורית: אם היו מוסיפים מטבע של שני סנט, איך היתה משתנה התשובה לשאלה המקורית?
גרסה אחרונה להפעם: מצא חמישה מטבעות כך שאפשר יהיה לשלם שקל על ידי מטבע אחד, שנים, שלושה, עד 14 אבל לא עם 15.
שנה טובה וחג שמח!
כותרת: פתרון
בקצרה:
לסעיף א´: 21
סעיף ב´: 45
סעיף ג´: 5, 20, 25, 50, 100.הוכחה:
ההוכחה מבוססת על אינדוקציה, שבסיסה הוא שניתן לשלם במטבע אחד של דולר.
כעת אנו מניחים שניתן לשלם ע"י N מטבעות, ואנו מעוניינים לשלם ע"י N+1 מטבעות. ע"י החלפת K מטבעות מהקבוצה של N מטבעות, ב-K+1 מטבעות בעלי סכום זהה, ניתן ליצור קבוצה של N+1 מטבעות, בעלת סכום זהה לקבוצה בת N המטבעות.
נשתמש באחד מהמעברים הבאים בכל שלב:
1. החלפת מטבע של דולר בשני מטבעות של 50 סנט.
100=50X2
2. החלפת מטבע של 50 סנט בשני מטבעות של 25 סנט.
50=25X2
3. החלפת מטבע של 10 בשני מטבעות של 5.
10=5X2
4. החלפת מטבע של 25 ומטבע של 5 בשלושה מטבעות של 10.
25+5=10X3
5. החלפת שלושה מטבעות של 25 במטבע של 50, שני מטבעות של 10, ומטבע של 5.
25X3=50+10X2+5ע"י שימוש באחד מהמעברים בכל שלב, ניתן להפוך כמעט כל קבוצה של Nמטבעות לקבוצה בת N+1 מטבעות. המצב היחידי שבו אי אפשר להמשיך הוא כאשר כל המטבעות הם של 5 סנט (20 מטבעות כאלה). ברור כי אי אפשר לפתור זאת ע"י 21 מטבעות (המטבע הקטן ביותר אינו מספיק קטן לכך), ולכן 21 הוא מספר המטבעות הראשון שבו אי אפשר לשלם דולר.
למען ההבהרה- דוגמא למעברים הראשונים:
1. (100)
2. (50X2) מעבר מספר 1.
3. (25X2,50) מעבר מס´ 2.
4. (25X4) מעבר מס´ 2.
5. (5,10X2,25,50) מעבר מס´ 5.
6. (5,10X2,25X3) מעבר מס´ 2.וכן הלאה.
החידוד:
נוסיף את המעברים הבאים:
6. החלפת שישה מטבעות של 5 בחמישה מטבעות של 2 ובשני מטבעות של 10.
7. החלפת שני מטבעות של 25 וחמישה מטבעות של 2 בארבעה מטבעות של 10 וארבעה מטבעות של 5. (זהו מעבר מיוחד הנוצר עבור N=27, כאשר יש עשרים וחמישה מטבעות של 2 ושני מטבעות של 25).כעת, המצב היחידי בו לא ניתן יהיה להפעיל את אחד המעברים הוא כאשר יש פחות משישה מטבעות של 5, וכל השאר מטבעות של 2.
(אין מצב בו יש מטבע יחיד של 25 והשאר 2, כי אז הסכום אי זוגי).
כלומר אנו "ניתקע" רק ב-N=44, כאשר יש ארבעים מטבעות של 2, וארבעה מטבעות של 5.
שימוש בשיטה הזו מוכיח כי ניתן לפתור עד N=44. כדי להוכיח כי אי אפשר לפתור עבור N=45 נשים לב כי מספר המטבעות של 2 תמיד מתחלק ב-5 (אחרת השארית של הסכום, מחלוקה ב-5, תהיה שונה מ-0).
עבור 40 מטבעות של 2, המקסימום שניתן להגיע אליו הוא 44.
45 מטבעות של 2, לעומת זאת, אינם מגיעים לסכום המיוחל של דולר.לכן- לא ניתן לפתור זאת ע"י 45 מטבעות, ו-45 הוא התשובה לחידוד.
ולסעיף האחרון- בקבוצה אין חוכמות מיוחדות, היא תוצאה של ניסוי קבוצות מיוחדות עד לתוצאה הרצויה.
הקבוצה היא:
5, 20, 25, 50, 1 דולר.
נשתמש במעברים 1 ו-2 מסעיף א´ ולהם נוסיף את המעברים הבאים:3. החלפת מטבע של 25 במטבע של 20 ומטבע של 5.
4. החלפת 3 מטבעות של 20 בשני מטבעות של 25 ושני מטבעות של 5.כעת, המצב היחיד בו אין לנו אפשרות להפעיל את אחד המעברים הוא כאשר יש פחות מ-3 פעמים 20, והשאר הם מטבעות של 5.
המקרה הראשון בו נתקע הוא של N=14, כאשר יש 12 מטבעות של 5, ו-2 מטבעות של 20. כלומר, ניתן לשלם בכל אחד מהמקרים של N=1 עד N=14.כדי להוכיח כי לא ניתן לפתור עבור N=15, נשים לב כי שימוש ביותר משני מטבעות מסוג גדול מ-20, יביא אותנו למצב בו אנו משתמשים לכל היותר ב-14 מטבעות.
(אם בוחרים לדוגמא פעמיים 20, הסכום הוא כבר 40, וניתן להשלים אותו ל-100 תוך שימוש ב-12 מטבעות לכל היותר).
לכן, עלינו לבדוק רק את המצבים הבאים:
1.מטבע אחד של 20 והשאר 5.
2.מטבע אחד של 25 והשאר 5.
3.מטבע אחד של 50 והשאר 5.
4.כל המטבעות הם של 5.
בכל אחד מהמקרים, מספר המטבעות שבהם משתמשים שונה מ-15, ולכן אי אפשר לשלם דולר תוך שימוש ב-15 מטבעות מהקבוצה הנ"ל.כותרת: תיקון
סליחה על הטעות, אבל תוך שימוש באותה שיטה, ניתן להגיע לפתרון גם לשאלה המקורית:
הפתרונות המעודכנים:
77
101סעיף א´:
נגדיר עוד שתי החלפות:
1. החלפת 7 מטבעות 5 ב-3 מטבעות 10 ו-5 מטבעות 1.
5X7=10X3+1X5
2. החלפת 2 מטבעות 25 ו-5 מטבעות 1 ב-3 מטבעות 10 ו-5 מטבעות 5.
25X2+1X5=10X3+5X5המקרים היחידים בהם "נתקעים" הם כאשר יש:
-פחות מ-7 מטבעות 5 והשאר 1.
-מטבע של 25 והשאר 1.
-הכל 1.במילים אחרות- כאשר יש 76 מטבעות, 75 של 1 ואחד של 25, או 70 של 1 ו-6 של 5.
כדי להראות שזהו המקסימום, נשים לב כי המטבעות של 1 באים ב"קפיצות" של 5 (שוב, השארית של הסכום בחלוקה ב-5 חייבת להיות 0). ובכל המקרים בהם יש 70 או 75 מטבעות של סנט יחיד, אין אפשרות להשלים ל-77.
סעיף ב´:
ההחלפות:
1. החלפת מטבע של שני סנט בשני מטבעות של סנט יחיד.
2. החלפת מטבע של 5 סנט ומטבע של סנט בשלושה מטבעות של שני סנט.
3. החלפת מטבע של 25 וחמישה מטבעות של 1 בשני מטבעות של 10 וחמישה מטבעות של 2.כעת, אין מצב בו נתקעים, עד שכל 100 המטבעות הם מסוג של סנט יחיד. ברור גם כי לא ניתן לפתור זאת ע"י 101 מטבעות.
הטעות הזאת אולי הבהירה את כוחה של השיטה, שנראית אולי מסורבלת, אבל בשינויים קטנים יכולה לפתור שאלות דומות מהסוג הזה בקלות.
- יש להתחבר למערכת על מנת להגיב.