שאלות ותשובות - מקבץ מס' 8

מזמן לא עשיתי מקבץ “שאלות ותשובות” - לשמחתי נהיה קשה לעשות מקבצים כאלו כי לשאלות רבות שמביאות אנשים לבלוג כבר יש תשובה. למרות זאת, הגיע הזמן למקבץ חדש:

1. "נוסחה לחישוב משיק לישר בנקודה" - ובכן, על פי הגדרת המשיק שנתתי פה פעם, המשיק לישר בנקודה כלשהי הוא הישר עצמו...
2. "קריאת מחשבות" - בקשו מידיד לבחור מספר בן 3 ספרות השונות זו מזו. בקשו ממנו להפוך את סדר הספרות ולחסר את המספר הקטן מהגדול. בקשו ממנו להפוך את סדר הספרות של התוצאה, ולחבר את התוצאה עם ההיפוך הזה. כעת בקשו ממנו לחשוב חזק חזק על המספר שהוא קיבל, קראו את מחשבותיו ואמרו לו שהוא חושב על 1089.
3. "דוגמאות להוכחות פורמליות ומקובלות" - הוכחה לקיום אינסוף ראשוניים: נניח כי יש רק מספר סופי של ראשוניים, \( p_{1},p_{2},\dots,p_{n} \). נתבונן במספר \( p_{1}\cdot p_{2}\cdots p_{n}+1 \). בחלוקה בכל אחד מה-\( p_{i} \)-ים נקבל שארית 1, כך שהוא אינו מתחלק באף ראשוני מהרשימה; ומצד שני, כל מספר מתחלק על ידי ראשוני (באינדוקציה: או שהוא עצמו ראשוני, או שאחד מגורמיו מתחלק על ידי ראשוני). מסקנה: קיים ראשוני שאינו ברשימה שלנו. זוהי הוכחה פורמלית ומקובלת.
4. "משפטים לאנשים לא מכובדים" - משפט ארו, הקובע כי שיטת הבחירה היחידה שהיא "הוגנת" (על פי הגדרה ספציפית מסויימת) היא לתת לדיקטטור להחליט, עשוי בהחלט להיות משפט מתאים לאנשים לא מכובדים.
5. "תרומת האיסלם בתחום המתמטיקה בעבר" - האיסלאם מפורסם בהקשר זה בשל היות מדינות האיסלאם המדינות הבולטות ביותר שבהן היה עיסוק מתמטי בימי הביניים, בעוד שבאירופה הוא נזנח כמעט לחלוטין. התרומות המפורסמות ביותר הן בתחום האלגברה (המילה עצמה מגיעה משם ספר של אל-חוואריזמי), שאז עוד הייתה בעיקרה העיסוק בפתרון משוואות. גם את שיטת הכתיב העשרונית, היעילה פי כמה משיטת ייצוג הספרות הרומית, חייב המערב לאיסלאם (הוא עצמו ככל הנראה ייבא אותה מהודו).
6. "מבני נתונים איך מוכיחים שגרף קשיר" - כמובן, זה תלוי בתנאי השאלה עצמה, אבל הנה אפיון נחמד של קשירות שעשוי לסייע בשאלות שלא ברור איך לגשת אליהן: גרף הוא קשיר אם ורק אם בכל חלוקה של קבוצת צמתיו לשתי קבוצות זרות ולא ריקות ("חתך" של הגרף), קיימת קשת מצומת באחת הקבוצות לצומת בקבוצה השניה (ברור שזהו תנאי הכרחי, ולא קשה להראות שהוא גם מספיק).
7. "תוכנה שבודקת אילו מספרים ראשונים" לצורך השעשוע שבדבר ולמרות שזה לא בדיוק מה שביקשו כאן, הנה תוכנית בהסקל שמבצעת סינון ראשוניים על פי הכברה של ארטוסתנס ומחזירה את הראשוני ה-10,001:

   sieve (p:xs) = p : sieve(filter (\n -> n `mod` p /= 0) xs)
   primes = sieve [2..]
   result = last (take 10001 primes)

8. "אם מספר מרוכב הוא שורש המשוואה אז גם הצמוד שלו הוא פתרון" - נכון עבור משוואות פולינומיות במקדמים ממשיים (אך לא באופן כללי יותר). הסיבה לכך היא שאם \( p\left(z\right) \) הוא פולינום במקדמים ממשיים כך ש-\( p\left(z\right)=0 \) אז \( \overline{p\left(z\right)}=\overline{0}=0 \) כי הצמוד של 0 הוא 0, אבל \( \overline{p\left(z\right)}=p\left(\overline{z}\right) \) כי כאשר מצמידים את מקדמי \( p \) הם לא משתנים (כי הם ממשיים).
9. "היפוך של כל שפה רגולרית הוא רגולרי" - כמובן. לוקחים את האוטומט של השפה, והופכים את כיווני כל החיצים. כל מצב התחלתי הופכים למצב מקבל, וכל מצב מקבל - למצב התחלתי. מקבלים אוטומט אי דטרמיניסטי, אבל הוא שקול לאוטומט דטרמיניסטי.
10. "מהן המידות המאפיינות את כל אחת מארבע האמהות?" - ובכן, מדוע אנו מניחים שארבע האמהות מדידות? אולי הן מהוות פירוק פרדוקסלי?