[אמיתי]

כותרת: פתרון
בקצרה:
לסעיף א´: 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 מטבעות מהקבוצה הנ"ל.

[מאת]

תגובות