בבלוגריתמוס 1 הצבתי בפניכם בעיה: למצוא מספר הבנוי מעשר הספרות 9-0 ומתחלק בכל אחת מהספרות 9-2, ורמזתי לאסטרטגיה פשוטה יחסית שאפשר לנקוט בה נוכח המספרים העצומים.
ראשית, מאחר שסכום המספרים הוא 45 – כל מספר שתכתבו יתחלק ב-3 וב-9.
שנית, מאחר שהמספר צרייך להתחלק ב-2 וב-5 – הספרה האחרונה חייבת להיות 0, וכיוון שהמספר חייב להתחלק בכל חזקות המספרים הראשוניים המופיעים בעשירייה – כל פתרון חייב להתחלק במכפלה 5*7*8*9, כלומר 4,520
לצערנו, יש מספרים רבים כאלה: !9, כלומר יותר מ-400 אלף מספרים שיהיה עלינו לבדוק בין 1,234,567,890 לבין 9,876,543,210 כדי לגלות מי ביניהם מתחלק ב-4,520. גם אם נביא בחשבון את כלל החלוקה ל-8, שקובע שהמספר הבנוי משלוש הספרות האחרונות חייב להתחלק ב-8, עדיין נישאר עם כ-100 אלף בדיקות! ואפשר לראות שהבעיה הקשה היא החלוקה ל-7.
לכן נפנה לשיטה אחרת, שהדגמתי אותה בשאלה: מצאו מספר הבנוי מהספרות 1, 3, 4 ו-5 ומתחלק ב-7. ישנם !4 (=24) מספרים הבנויים מארבע ספרות שונות ואפשר להתחיל לבדוק כל אחד, אבל קל לראות שניתן להרכיב שני זוגות מספרים – 14, 35, שכל זוג בהם מתחלק ב-7, למשל: 1,435=35+(14*100) ולכן מתחלק ב-7, ובאופן דומה גם 3,514.
ניישם את השיטה הזאת לפתרון בעיית עשר הספרות: נחפש חלוקה שלהן לשלוש שלישיות (מלבד המספר 7) כשכל שלישיה היא מספר תלת-ספרתי המתחלק ב-7. בנוסף, השלישייה המסיימת צריכה, כפי שהראינו, להתחלק ב-7, 8 ו-10, כלומר היא חייבת להתחלק ב-280, ולכן יכולה להיות 280, 560 או 840.
עבור הסיומת 280 – נוכל לקבל את השלשות 154,693, שכל אחת מתחלקת ב-7, ונוכל להרכיב מהן שישה פתרונות באופן הבא: יש שתי 2 אפשרויות לבחור את השלשה הראשונה והשנייה וכן שלוש אפשרויות לשבץ את ה-7 – בראש המספר, בין השלשה הראשונה לשנייה או בין השנייה לשלישית. לדוגמה: 6,037,154,280.
בצורה דומה נתאים לשלשה האחרונה 840 את שתי השלשות 196 ו-532 ונקבל שישה פתרונות נוספים, לדוגמה: 7,196,532,840
שימו לב: לא תמיד אפשר לפתור בשיטה הזו. דוגמה פשוטה: אי אפשר להרכיב מהספרות 0,0,1,1 מספר המתחלק ב-7. המספרים החלקיים שאפשר להרכיב מהספרות הם 10, 11, 100, 101 ו-110, ואף אחד מהם לא מתחלק ב-7 – ואף על פי כן 1,001 מתחלק ב-7. לכן ייתכנו תמיד פתרונות נוספים על אלה שמצאנו בשיטה הזו.
השיטה טובה כניסיון חסכוני למצוא לפחות פתרון אחד או חלק מהפתרונות. כתרגיל, נסו למצוא את המספר המכיל את מרב הספרות מתוך העשר ומתחלק ב-13, ואותו דבר לגבי 17. עוד על כך, בבלוג הבא.
בהצלחה,
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
