עוד חידה מגניבה...

[Fingertip]

עוד חידה מגניבה...

תודות לאורי פנקס מפורום "מבני נתונים ומבוא לאלגוריתמים" שהביא את השאלה החמודה הזה. יש לי שני פתרונות, אחד חביב וקצר, אחד ארוך ומסובך, אבל אולי אתם תמצאו פתרון יותר פשוט! והחידה: מספר יקרא "מספר יפה" אם הוא מורכב מקבוצה של 1-ים (1 אחד ומעלה) ולאחריהם קבוצה של 0-ים (0 אחד ומעלה). לדוגמה: 111000 הוא מספר יפה, 10 הוא המספר היפה הקטן ביותר, 1101101 אינו מספר יפה. (הייצוג הוא בבסיס עשרוני, לא להתחכם עם בסיסים בינארים...) הוכיחו שלכל מספר טבעי n שלא יהיה, קיים מספר שלם k כך ש-n*k הוא מספר יפה. בהצלחה! אהד.

 

[aaa123]

פתרון

נפרק את המספר לגורמים ראשונים אנו יכולים להכפיל את 2 בחזקת משהו כפול 5 בחזקת משהו כדי לקבל 10 בחזקת משהו ונשאר לנו להכפיל את מכפלת יתר הגורמים כדי לקבל מספר שמורכב רק מאחדים. נסמן בM את מכפלת יתר הגורמים. נסתכל בשאריות של החזקות של 10 בM. השארית הראשונה היא אחד ומכיון שאף שארית איננה 0 השאריות יוצרות סדרה מחזורית. הסכום של השאריות של M מחזורים חייב להתחלק בM ,וזה אומר שהסכום של החזקות הרלבנטיות של 10 שנותנים שאריות אלו גם מתחלק בM. במלים אחרות אפשר לקבל כפולה של M שמורכבת רק מ1ים.

 

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

פתרון דומה (מבוסס על אותו רעיון):

גם כן אפשר לשים בצד את הגורמים 2 ו-5, אבל בעיקרון לא חשוב. 1 חלקי 9N הוא מספר רציונלי, לכן, כידוע, ניתן להציגו כשבר עשרוני אינסופי מחזורי (אם לא היינו שמים בצד את 2 ו-5, המחזור יכול להיות גם 0 או 9, לא חשוב). מציגים את השבר העשרוני האינסופי המחזורי כסכום סדרה הנדסית אינסופית ומקבלים שבר, שהמכנה שלו הוא בדיוק "מספר יפה", רק במקום רצף הספרה 1 יש בו רצף של הספרה 9. נשאר לנו לבצע הכפלה מוצלבת ולצמצם ב-9.

 

[Fingertip]

פתרון יפה...

 

[Fingertip]

אבל בעצם...

מה קורה כאשר המחזור אינו מתחיל מהנקודה? למשל, 1/72 הוא 0.01388888888888888888888888888888 ואז אתה חייב להציג את זה כסכום סדרה ועוד 0.013... אהד.

 

[איגור קרסיק]

פתרון פשוט

הבעיה תפטר אם מכפילים מספיק פעמים ב-10.... תחשוב על זה...

 

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

לסכום הסדרה ועוד 0.013 יש אותו

המכנה המשותף כמו לסכום הסדרה בלבד, אולי כמה אפסים יותר...

 

[Fingertip]

מה פתאום אותו מכנה?

לסכום הסדרה יש מכנה 9, ואילו ל-0.013 יש מכנה 1000! אהד.

 

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

כתבתי "אולי כמה אפסים יותר". תמיד!

הכוונה למכנה המשותף הסופי. כאן: 9000.

 

[איגור קרסיק]

פתרון נוסף

נסתכל ב-n+1 המספרים:

1,11,111,...,1...1​

כאשר במספר האחרון יש n+1 ספרות. לכל אחד מהמספרים נמצא את השארית בחלוקה ב-n כך יתקבלו n+1 שאריות. ומשום שקיימות n שאריות שונות בחלוקה ב-n. בהכרח קיימים 2 מספרים שונים בעלי אותה שארית. לפיכך n יתחלק בהפרש של 2 המספרים. אך ההפרש הוא מספר יפה...

 

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

נהדר!!!

 

[איגור קרסיק]

אהד....

איכפת לך לרשום את ההוכחות שאתה מצאת...

 

[Fingertip]

יש לי שני פתרונות...

אחד מאוד מאוד ארוך - זה הפתרון שהגעתי אליו בעצמי. הוא מאוד ארוך, כמו כל הפתרונות שלי. אחד דומה טיפה לפתרון של איגור, רק במקום לחשב את את השארית של 1111..1 מחשבים את השארית של

10^i mod (9n)​

מקבלים שתי שאריות שוות, מחסרים, מקבלים שארית 0, ואז n*k הוא למעשה

(10^p - 10^q)/9​

שזהו למעשה מספר יפה. זה פתרון ש-Woom הראתה לי. (אתם לא מכירים אותה...) אהד.

 

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

הרבה פתרונות מסתובבים סביב אותו

רעיון, וכאמוּר הפתרון של איגור זוכה בתחרות ללא עוררין! ברשותכם סיפור מעשיה מימים רחוקים. לפני שנים רבות התחריתי עם חבר לעבודה מי משנינו יכתוב תכנית קצרה שמחשבת משהו, אינני זוכר מה, והתכנית של מי תהיה יותר מהירה. נדברנו על איזשהו מקדם, כי הוא כתב ב-PL1 ואני באסמבלר. מכיוון שהשתמשנו באלגוריתמים שונים לחלוטין, תרגמתי את התכנית שלו לאסמבלר, ובשביל להיות לגמרי פיר, ניסיתי לשפר את תכנית האסמבלר לפי האלגוריתם שלו, כמה שאפשר. מי שמכיר את הסיפור הזה: כאן אפשר לקצר, כאן לעקוף, כאן לשכלל, כדי שהתכנית תהיה כמה שיותר מהירה. בקיצור, בסוף יצא......העתק מדוייק של התכנית שלי!