חידה מתמטית

[dr.null]

אז ככה:

אתם קופאים שצריכים להחזיר עודף ללקוח בסך של 25 שקלים
אתם צריכים להחזיר לו את העודף ב-10 מטבעות, אבל בעולם שאתם נמצאים קיימים רק שלושה סוגים של מטבעות: 1,3,5

ציינו 10 מטבעות שערכם 1,3,5 ושסכומם שווה 25

[דניאלק]

כותרת: חחחחחחחח, אהבתי
אבל חידה פשוטה למדי…
אתה הרי מחבר סכום זוגי של מספרים אי זוגיים, והתוצאה תמיד תצא זוגית – החידה בלתי אפשרית.

[CodeGuru]

כותרת: ועוד חידה קשורה
בארצות הברית קיימים שישה סוגים של מטבעות: 1,5,10,25,50,100.
ולכן אפשר לשלם דולר בכמה צורות שונות:
1) מטבע בודד של דולר,
2) שני מטבעות של חצי דולר,
3) אפשר אפילו לשלם דולר בשלושה מטבעות (איך?),
…
100) וכן במאה מטבעות (של סנט בודד).
מהו המספר המינימאלי של מטבעות בו אי-אפשר לשלם דולר?

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

[CodeGuru]

כותרת: ועוד חידה קשורה
בארצות הברית קיימים שישה סוגים של מטבעות: 1,5,10,25,50,100.
ולכן אפשר לשלם דולר בכמה צורות שונות:
1) מטבע בודד של דולר,
2) שני מטבעות של חצי דולר,
3) אפשר אפילו לשלם דולר בשלושה מטבעות (איך?),
…
100) וכן במאה מטבעות (של סנט בודד).
מהו המספר המינימאלי של מטבעות בו אי-אפשר לשלם דולר?

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

[דניאלק]

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

1. 100
2. 50 + 50
3. 50 + 25 + 25
4. 25 + 25 + 25 + 25
5. 50 + 25 + 10 + 10 + 5
6. 50 + 10 + 10 + 10 + 10 + 10
על ידי החלפה של מטבע 10 ב2 מטבעות של 5, נגדיל את מספר המטבעות כל פעם ב1, ובשיטה זו נגיע עד 10…
10. 10 פעמים 10.
שוב פעם, על ידי החלפת מטבעות של 10 ב2 של 5, אפשר להגיע עד 20.
20. 20 מטבעות של 5.
מכאן, נחליף מטבע של 5 ב5 מטבעות של 1, מה שיוסיף לנו 4 מטבעות לסכום. כדי לפצות על כך(אנחנו צריכים להוסיף רק מטבע 1), נמיר מטבעות של 5 למטבעות של 10(6 מטבעות 5 בשביל להגיע ל+1, 4 בשביל +2, 2 בשביל +3, ולא נמיר מטבעות של 5, אם צריך להוסיף 4).
נמשיך בפעולה זו, עד שנגיע ל76:
70 מטבעות של 1, ו6 מטבעות של 5.
עתה, אם ננסה להמיר מטבע של 5 לאחדות, לא יהיו לנו מספיק מטבעות 5 כדי להגיע לתוספת של מטבע אחד בלבד(ניתן להמיר רק 2 זוגות מטבעות של 5, ולכן נגיע ל+2, אבל לא ל+1).

כלומר – 77 הינו המספר המינימלי שאי אפשר להרכיב בו דולר.

מקווה שהייתי מספיק ברור…

[CodeGuru]

כותרת: כל הכבוד, ומה עם החלק השני?

[דניאלק]

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

אני כן יכול להצביע על עובדה מעניינת אחרת בכל נושא המטבעות, אם נפתח סוגרים בביטוי הבא:
(1 + x + x^2 + x^3 + x^4 + x^5 …)(1 + x^5 + x^10 + x^15 + x^20 + x^25 …)(1 + x^10 + x^20 + x^30 + x^40 + x^50 …)(1 + (1 + x^25 + x^50 + x^75…)(1 + x^50 + x^100…)

אז המקדם של
x^100
למעשה אומר בכמה דרכים שונות אפשר להרכיב דולר מהמטבעות הנ"ל.
המקדם של
x ^ 55
למעשה אומר בכמה דרכים שונות אפשר להרכיב 55 סנט מהמטבעות הנ"ל.
(מישהו מבין למה?)

בכל מקרה, כל התחום הזה נקרא
Generating functions
ואוהבים להשתמש בו בכל מיני בעיות קומבינטוריות…

[מאת]

תגובות