חידה מראיון עבודה ...

[Cadillac]

חידה מראיון עבודה ...

תמיד תפסתי מעצמי בקטע של חידות ... אבל לא הצלחתי יותר מדי לגשת לחידה הזאת. אשמח לקבל עזרה : נתונים 2 מספרים רציונליים ויש למצוא מספר רציונלי ביינהם המקיים סכום מונה ומכנה מינימאלי. ולהוכיח כי הוא המינימאלי. המספרים היו : 485/601 והמספר השני היה 439/544 לי זה כבר לא יעזור, אבל החידה נורא מעניינת אותי.

 

[AnarchistPhilosopher]

רגע, שאבין את החידה כמו שצריך:

אם נתון לנו :

a/b c/d​

צריך להוכיח שקיים מספר רציונלי שהמונה שלו שווה לסכום המונים של האחרים והמכנה שלו שווה למכנים של האחרים, כלומר:

(a+b)/(c+d)​

נכון?

 

[טלמון סילבר]

לא כך.

נתונים שני מספרים רציונליים, בצורת שברים בלתי מצטמצמים: a/b,c/d a/b < c/d וצריך למצוא כזה מספר רציונלי, המיוצג כשבר בלתי מצטמצם p/q המקיים a/b < p/q < c/d ושהסכום p+q יהיה מינימלי. סתם למצוא מספר רציונלי בין שני נתונים זו לא בעיה:

r = [(a/b) + (c/d)]/2 = (ad + cb)/bd​

אם אינני טועה, יש משפט כזה, שלפיו התשובה לשאלה הנ"ל היא:

r = (a + c)/(b + d)​

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

לעבודה של מתרגל בתורת המספרים?

 

[עריסטו]

אין משפט כמו שכתבת

למשל, אם השברים הם 1/3 ו - 3/4, הנוסחה שלך נותנת 4/7, אבל הפתרון הוא 1/2. נראה לי שמה שכתבת נכון אם השברים המקוריים מקיימים

|ad-bc|=1​

כמו בשאלה כאן.

 

[Cadillac]

אבל למה זה נכון ?

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

 

[עריסטו]

זה בגלל האופן בו ניתן לבנות את כל

המספרים הרציונליים באמצעות עץ Stern-Brocot http://www.cut-the-knot.org/blue/Stern.shtml

 

[Cadillac]

עבודה כאלגוריתמאי ...

 

[טלמון סילבר]

ונשארת השאלה,

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