משהו נחמד

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

משהו נחמד

את החידה הזו הכרתי כאשר למדתי דיסקרטית. והנה היא לפניכם: יהי n מספר טבעי, שהספרה הימנית שלו (בבסיס 10) היא 1 או 3 או 7 או 9. הוכח שקיימת כפולה של n, שכל הספרות שלה הן 1 : כגון 11, או 11111 וכד´. ניתן להכליל את הטענה הזו לדבר הבא: יהי n כמו בחלק א. תהי s מחרוזת סופית כלשהי של ספרות עשרוניות (למשל: s = 221366) אז יש ל- n כפולה, שהכתיב העשרוני שלה הוא רק חזרות על s כגון: s או sss או sssssss וכד´. דוגמא: s = 112 , n = 13 אכן: 13 * 8624 = 112112 בהצלחה.

 

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

הקפצה + רמז

יש משפט נחמד שעוזר בפתרון החידה: יהיו a,b,c טבעיים חיוביים. נניח ש- a מתחלק ב- b, ו- a מתחלק ב- c אם b,c זרים זה לזה אז גם a/b מתחלק ב- c.

 

[פייד-ראותא]

מה הכוונה ב:"זרים זה לזה"?

ואגב כל מספר טבעי הוא חיובי...

פייד!

 

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

תשובה

זרים זה לזה = המחלק המשותף החיובי הגדול ביותר שלהם הוא 1. למשל 13 ו-12 שכן המחלקים החיוביים של 13 הם 1 והוא עצמו והמחלקים של 12 הם 4,3,2,6,1,12, ולכן רק 1 מחלק את 2 המספרים הנ"ל, וממילא הוא הגדול ביותר... כל מספר הוא חיובי בתנאי שמגדירים את המספרים הטיבעיים ללא 0 [ויש שמגדירים עם 0], וזאת הסיבה שרשמתי זאת [בשביל שהמשפט יהיה בסדר לשני ההגדרות].

 

[פייד-ראותא]

הבנתי,תודה!

 

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

התיאשתם?

רוצים עוד רמז?

 

[בן100]

דיר חזירים - הוכחה מלאה.

מכיר את המשפט הידוע על דיר החזירים? המשפט אומר שאם 100 חזירים נכנסים לדיר שבו יש 99 תאים אז 2 חזירים ילכו מכות. הוכחה מלאה: יהי n המספר המספר הטבעי הנתון ויהי t המספר שבו הכפולה של n אמורה להסתיים. ואוכיח לך (כאן ועכשיו) שקיים m כך ש mn מסתיים ב-t. ניקח מספר מינימלי y כך ש 10 בחזקת y גדול מ-t ונסמן אותו ב-X (x = 10^y > t > 10^(y-1 ונוכיח כי קיים k כך שn^k מסתיים ב00001..... נסתכל על המספרים n^1.....n^x אף אחד מהם אינו מתחלק ב-X, (כי X הוא מספר זוגי). נחלק את כל x+1 המספרים ב-x ונסתכל על השארית: ישנם לפחות 2 מספרים בעלי אותה השארית (כלל דיר החזירים) נניח כי המספרים הם n^i ו- n^j בלי הגבלת הכלליות i>j נקבל מכאן כי (n^(i-j) - n^j ) מתחלק ב 00000..... מכאן (n^(i-j מתחלק ב 00001..... לכן ((t*(n^(i-j נותן את המספר המבוקש מ ש " ל ! נ.ב. : קיבלתי 100 בבדידה.