אלון14 מה עם חידת המספרים
- פותח הנושא Shiberia
- פורסם בתאריך
אתה רוצה את החידה או הפתרון ../images/Emo8.gif?
החידה היא: ל-6 שני מחלקים חוץ מעצמו או 1; 2 לחלק ל-6 שווה לשליש. ל-12 ארבעה מחלקים חוץ מעצמו או 1; 4 לחלק ל-12 גם שווה לשליש. ל-24 שישה מחלקים חוץ מעצמו או 1; 6 לחלק ל-24 זה רבע. נגדיר את השליש הזה (או הרבע) כ-יעילות של המספר. אם נבחן כמה מספרים אחרים, נגלה שהיעילות של 4 ו-8 היא רבע, זו של 10 ו-30 היא חמישית, וזו של 60 היא שישית. והחידה: הוכח שאין אף מספר חוץ מ-6 ו-12 שהיעילות שלו שווה או גדולה משליש.
החידה היא: ל-6 שני מחלקים חוץ מעצמו או 1; 2 לחלק ל-6 שווה לשליש. ל-12 ארבעה מחלקים חוץ מעצמו או 1; 4 לחלק ל-12 גם שווה לשליש. ל-24 שישה מחלקים חוץ מעצמו או 1; 6 לחלק ל-24 זה רבע. נגדיר את השליש הזה (או הרבע) כ-יעילות של המספר. אם נבחן כמה מספרים אחרים, נגלה שהיעילות של 4 ו-8 היא רבע, זו של 10 ו-30 היא חמישית, וזו של 60 היא שישית. והחידה: הוכח שאין אף מספר חוץ מ-6 ו-12 שהיעילות שלו שווה או גדולה משליש.
הסתכלתי
ההגדרה שלך ליעילות מאוד נחמדה אבל צריך להחליף את q ב-q-2 (הסבר למי שלא ראה - להלן), וכן יש להוכיח ששתי ההגדרות זהות (זו ממש לא בעיה). אגב, רעיון זה מאוד מקל על הפתרון. ועכשיו, הסבר: כל מספר טבעי X אפשר לייצג כמכפלה של ראשונים Pi בחזקת Ki. אז מספר המחלקים של x (כולל עצמו ו-1) הוא מכפלת כל (Ki + 1) נסמן ב q . כלומר, מספר המחלקים עבורנו הוא q-2 (בלי המספר ו-1), והיעילות היא q-2 / x, או y. צ"ל: y<=1/3, שוויון אם ורק אם x שווה ל-6 או 12.
ההגדרה שלך ליעילות מאוד נחמדה אבל צריך להחליף את q ב-q-2 (הסבר למי שלא ראה - להלן), וכן יש להוכיח ששתי ההגדרות זהות (זו ממש לא בעיה). אגב, רעיון זה מאוד מקל על הפתרון. ועכשיו, הסבר: כל מספר טבעי X אפשר לייצג כמכפלה של ראשונים Pi בחזקת Ki. אז מספר המחלקים של x (כולל עצמו ו-1) הוא מכפלת כל (Ki + 1) נסמן ב q . כלומר, מספר המחלקים עבורנו הוא q-2 (בלי המספר ו-1), והיעילות היא q-2 / x, או y. צ"ל: y<=1/3, שוויון אם ורק אם x שווה ל-6 או 12.
סינגפור ואני גר פה...
...בנוגע להוכחה, נבנה כל מספר בעל יותר משני גורמים ראשוניים ממחלק שלו מהצורה A*B כאשר A ו-B שונים וראשוניים. זה אפשרי אלא אם כן כל הגורמים הראשוניים של המספר (נקרא לו X) זהים, אבל במקרה כזה היעילות מוגבלת כיוון שהכפלת מספר בגורם ראשוני שלו יכולה במקרה הכי טוב להכפיל את מספר המחלקים (היא מכפילה את מספר המחלקים כולל X ו-1 ב-1.5 אם הגורם מופיע פעם אחת בלבד ובפחות אם הוא מופיע יותר מפעם, אבל ה-1.5 יכול להפוך ל-2 אם יש רק 2 מחלקים לא כולל X ו-1), אבל במקרה כזה היא גם מכפילה את המספר עצמו ב-2 לפחות, ועל כן היעילות של המספר הולכת וקטנה (כיוון שכל ההכפלות חוץ מזו שהופכת את המספר לריבוע שלם למעשה אינן מספיקות על מנת להכפיל את מספר המחלקים בהכפלה אחת). מאחר שהיעילות המקסימלית היא זו של ריבועים שלמים, ולכולם אותו מספר מחלקים (כיוון שכולם ריבועים של ראשוניים), החזקה הכי יעילה היא 4, שהיעילות שלה היא רבע. אוקיי, נעבור למספרים שכן ניתן למצוא להם מחלק מהצורה A*B. אם נבחר את A ו-B כך שיהיו שני המחלקים השונים הכי נמוכים, אז נקבל ש-A*B יעיל לפחות כמו X (הוכחה בשורה הבאה
). הוכחה: הכפלה בגורם ראשוני יכולה לכל היותר להכפיל את המספר ולהוסיף לו 2 במקרה בו הגורם המוכפל לא מופיע בהצגה (כלומר הכפלת מספר בראשוני זר), או רק להכפיל (אם הגורם כבר מופיע בהצגה, כלומר הכפלת מספר בראשוני לא זר). מאחר ש-2, אם הוא מופיע בהצגה של X, הוא הגורם הראשוני הכי קטן, הוא תמיד יופיע ב-A*B ולכן מקרה ההכפלה ועוד שתיים לעולם לא יקרה איתו. זה כן יכול לקרות לכל מספר אחר חוץ מ-3 (שהוא השני הכי קטן או הכי קטן אם הוא מופיע), אבל במקרה כזה ההכפלה ועוד שתיים מסוגלת מקסימום לשלש את מספר המחלקים (מ-2 ל-6; 1 אינו אפשרות כי ב-A*B יש תמיד 2), בעוד שהפעולה מחמשת את המספר ויותר. אם 2 כן מופיע יותר מפעם אחת אז ההכפלה בו רק תכפיל את מספר המחלקים (לכל היותר), ועל כן היעילות לא תגדל. מסקנה: אין אף מספר בעל שלושה גורמים ראשוניים או יותר מתוכם לפחות שניים שונים שהינו יותר יעיל ממכפלת שני הגורמים הראשוניים השונים הכי קטנים שלו. טענה נוספת: מאחר שלכל המספרים מהצורה A*B יש אתא ותו מספר מחלקים, היעיל ביותר מביניהם הוא המספר הכי קטן מביניהם, כאשר הוא חייב להיות יחיד עקב הפירוק היחיד (תכונה ידועה בטבעיים). מאחר שהמספר הכי קטן מהצורה A*B הוא ,ניתן להסיק שאף A*B אחר לא יכול להגיע ליעילות שלו, וממילא אף מספר שאינו מתחלק בו לא יכול (כיוון שהוא ייצר A*B אחר בעל יעילות שווה לפחות, וכן A*B יהיה פחות יעיל מ-6). עכשיו, נבחן עוד פעם את בניית X מ-A*B, כאשר ללא הגבלת הכלליות, A=2 ו-B=3. אנחנו לא יכולים להכפיל במספר שאינו מופיע בהצגה כיוון שזה יוריד את היעילות (כיוון שאנחנו מסוגלים בהכפלה יחידה במקרה הטוב ביותר להפוך את מספר המחלקים Q ל-3Q אם ורק אם Q=2 כלומר בתנאי ההתחלה ורק בהם, בעוד שהמספר מכפיל את עצמו לפחות פי 5 - הראשוני הקטן ביותר אחרי 3); אנחנו לא יכולים להכפיל ב-3 כיוון שזה רק יכפיל את מספר המחלקים (במקרה הטוב ביותר) בעוד שהמספר מכפיל את עצמו ב-3 כיוון שגם זה לא יעיל. הפעולה היחידה שנשארה הינה הכפלה ב-2, ואכן 12 יעיל בדיוק כמו 6. לרוע המזל, הכפלות נוספות ב-2 הינן פחות יעילות כיוון שכל הכפלה כזאת יוצרת רק שני צירופים נוספים: המספר החדש לחלק לשתיים (קודם זה היה המספר עצמו שלא נחשב), והמספר החדש לחלק לשלוש (קודם לא היו מספיק 2-ים בהצגה עבור זה) - וכמובן ששני החדשים אינם מספיקים כדי להכפיל את Q בפעם אחת. מסקנה: אף מספר חוץ מ-12 לא מסוגל להגיע את היעילות של 6, ואף אחד לא יכול לעבור אותה. כלומר: אף מספר לא יכול להגיע או לעבור את היעילות של 6 או 12, שהיא שליש. מש"ל (אני מקווה
).
...בנוגע להוכחה, נבנה כל מספר בעל יותר משני גורמים ראשוניים ממחלק שלו מהצורה A*B כאשר A ו-B שונים וראשוניים. זה אפשרי אלא אם כן כל הגורמים הראשוניים של המספר (נקרא לו X) זהים, אבל במקרה כזה היעילות מוגבלת כיוון שהכפלת מספר בגורם ראשוני שלו יכולה במקרה הכי טוב להכפיל את מספר המחלקים (היא מכפילה את מספר המחלקים כולל X ו-1 ב-1.5 אם הגורם מופיע פעם אחת בלבד ובפחות אם הוא מופיע יותר מפעם, אבל ה-1.5 יכול להפוך ל-2 אם יש רק 2 מחלקים לא כולל X ו-1), אבל במקרה כזה היא גם מכפילה את המספר עצמו ב-2 לפחות, ועל כן היעילות של המספר הולכת וקטנה (כיוון שכל ההכפלות חוץ מזו שהופכת את המספר לריבוע שלם למעשה אינן מספיקות על מנת להכפיל את מספר המחלקים בהכפלה אחת). מאחר שהיעילות המקסימלית היא זו של ריבועים שלמים, ולכולם אותו מספר מחלקים (כיוון שכולם ריבועים של ראשוניים), החזקה הכי יעילה היא 4, שהיעילות שלה היא רבע. אוקיי, נעבור למספרים שכן ניתן למצוא להם מחלק מהצורה A*B. אם נבחר את A ו-B כך שיהיו שני המחלקים השונים הכי נמוכים, אז נקבל ש-A*B יעיל לפחות כמו X (הוכחה בשורה הבאה
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.