חידה מתמטית

עמוד
מוצגות 7 תגובות – 1 עד 7 (מתוך 7 סה״כ)
  • מאת
    תגובות
  • #77402
    dr.null
    משתתף

    אז ככה:

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

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

    #79298
    דניאלק
    משתתף

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

    #79301
    CodeGuru
    מנהל בפורום

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

    100) וכן במאה מטבעות (של סנט בודד).
    מהו המספר המינימאלי של מטבעות בו אי-אפשר לשלם דולר?

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

    #79302
    CodeGuru
    מנהל בפורום

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

    100) וכן במאה מטבעות (של סנט בודד).
    מהו המספר המינימאלי של מטבעות בו אי-אפשר לשלם דולר?

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

    #79303
    דניאלק
    משתתף

    כותרת: פתרון לחלק הראשון.
    אפשר על ידי תוכנית, שתבדוק בכמה דרכים שונות אפשר ליצור דולר, וכמה מטבעות נדרשות בכל דרך(יש 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 הינו המספר המינימלי שאי אפשר להרכיב בו דולר.

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

    #79304
    CodeGuru
    מנהל בפורום

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

    #79306
    דניאלק
    משתתף

    כותרת: אממממ.. החלק השני הוא למתקדמים :-)
    אני כן יכול להצביע על כמה מטבעות שחייבים להיות קיימים(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
    ואוהבים להשתמש בו בכל מיני בעיות קומבינטוריות…

מוצגות 7 תגובות – 1 עד 7 (מתוך 7 סה״כ)
  • יש להתחבר למערכת על מנת להגיב.