1
|
את החידה שלפנינו חיבר המתמטיקאי האנגלי הנודע, הנרי ארנסט דודיני: הסולטאן מעוניין לשלוח לקרב יחידת חיל רגלים שאת לוחמיה ניתן לסדר בשתי קבוצות ריבועיות בתריסר דרכים שונות. מה המספר המזערי של לוחמים שיש לכלול ביחידה כזו?
דוגמה: יחידה שבה 130 לוחמים ניתנת לסידור בשתי קבוצות ריבועיות בשתי דרכים שונות:
פתרון
|
-
-
-
-
-
-
-
-
-
-
-
-
|
|
|
עריכה | תבנית | שיחה
|
2
|
מצא את המספר המינימלי המקיים:
- שתי ספרותיו האחרונות הן 56
- המספר מתחלק ב-56
- סכום ספרותיו הוא 56
פתרון
|
29899856
חידת בונוס: נסו למצוא תנאי: מתי פשוט למצוא מספר כזה ומתי לא?
פתרון
|
כל מספר שמתחלק בסכום ספרותיו. לדוגמה: 27, והפתרון הוא 272,727. מספר כזה נקרא מספר הרשאד
|
|
|
|
|
עריכה | תבנית | שיחה
|
3
|
לוקחים 28 גרגרי אורז, ומחלקים אותם לערמות בצורה כלשהי (בכל ערמה יש גרגר אורז אחד או יותר).
נמלה מגיעה לערמות הגרגרים, אוספת גרגר אחד מכל ערמה - ויוצרת מכל אלו ערמה חדשה - ערמות שהיה בהן רק גרגר אחד נעלמות כמובן. הנמלה חוזרת על הפעולה שוב ושוב. למשל - אם היו רק 6 גרגרים, המסודרים בערמות 2, 2, 2 אחרי סיבוב אחד של הנמלה המצב יהיה - 1, 1, 1, 3 אחרי הסיבוב הבא - 2, 4.
במקרה של 28 גרגרים, האם קיים מצב יציב (כלומר מצב שלאחר שמגיעים אליו הוא יישאר אותו דבר אחרי כל סיבוב של הנמלה), ומהו? האם בהכרח מכל מצב שהוא, אחרי מספיק סיבובים נגיע למצב היציב (הוכיחו שכן או מיצאו דוגמת נגד)?
פתרון
|
מצב יציב הוא מצב שבו הערמות מהוות סדרה חשבונית עם איבר פותח 1 והפרש 1 (כמו 1,2 או 1,2,3,4) במקרה שלנו 1,2,3,4,5,6,7
אפשר גם לעשות את זה על כל מספר משולשי.
|
|
|
עריכה | תבנית | שיחה
|
4
|
מהי הספרה השמינית אחרי הנקודה בפיתוח העשרוני של המספר האי-רציונלי:
פתרון
|
9. הסבר:
הביטוי שווה בערך 0.3. העלאתו בחזקת 2008 תתן מספר קטן מאד, שבו לפחות עשר הספרות מימין לנקודה הן אפס.
נסתכל על הביטוי
בפיתוח על-פי הבינום של ניוטון, מתקבל
.
בסכום הימני, הרכיבים שסימנם שלילי הם אלה שבהם k אי-זוגי. מכאן שבסכום הכולל מתקזזים כל הרכיבים שבהם k אי-זוגי ונותרים רק רכיבים שבהם k הוא זוגי, שהם הרכיבים שבהם החזקה של וגם של היא זוגית. לכן הוא מורכב כולו ממספרים שלמים ובעצמו מספר שלם.
הביטוי המקורי שווה ל
וראינו שסכום שני האיברים הראשונים
הוא מספר שלם, והאיבר השלישי
קרוב מאד לאפס. לכן חיסור האיבר השלישי מסכום שני האיברים הראשונים ייתן מספר שקרוב מאד למספר שלם, שבו לפחות עשר הספרות הראשונות מימין לנקודה העשרונית, ובפרט הספרה השמינית, הן כולן 9.
|
|
|
עריכה | תבנית | שיחה
|
5
|
נגדיר פונקציה בתור סכום הספרות הסופי של מספר טבעי. כלומר, לכל מספר טבעי סוכמים את סכום הספרות שלו שוב ושוב עד שמתקבל מספר בין 1 ל-9. לדוגמה: .
מצא את:
פתרון
|
הפונקציה למעשה נותנת את הערך 9 אם המספר מתחלק ב-9, ואחרת את השארית בחלוקה ל-9. נחשב את השארית בחלוקה ב-9:
מכיוון ש-, הרי נקבל כי
ולכן התוצאה המבוקשת היא 7.
|
|
|
עריכה | תבנית | שיחה
|
6
|
למלך היו 100 מתמטיקאים בכלא. יום אחד הוא אסף אותם והכריז: "עד הלילה תהיו ביחד ותהיה לכם הזדמנות לגבש אסטרטגיה. לאחר מכן אשים כל אחד מכם בתא מבודד. בכל זמן שארצה אבחר מישהו באקראיות ואשים אותו בחדר שכל מה שיש בו זה נורה ומתג. מי שבפנים יוכל לשנות את מצב הנורה (אם היא הייתה דלוקה לכבות ואם כבויה להדליק) או לא לעשות כלום. בהתחלה הנורה תהיה כבויה. המטרה שלכם שבאחד הימים יבוא אלי מישהו ויגיד שכולם כבר היו בחדר לפחות פעם אחת. אם הוא יצדק, אשחרר את כולכם, אך אם יטעה, אוציא את כולכם להורג." מה צריכה להיות האסטרטגיה של המתמטיקאים?
הערה: לצורך החידה למתמטיקאים יש חיי אלמוות. כל אחד מהם נכנס מספר פעמים לא מוגבל לחדר, כלומר אין דבר כזה מישהו שנכנס בפעם האחרונה. כמו כן, אין המתמטיקאים יודעים את הזמנים בהם מוכנסים אנשים ואין הם יודעים את המספר הסידורי של כניסתם (בפרט הראשון שנכנס אינו יודע שהוא הראשון).
פתרון
|
על המתמטיקאים למנות ראש קבוצה. כל אחד מה-99 האחרים יפעל לפי האלגוריתם הבא: בפעם הראשונה שהוא רואה את הנורה כבויה, הוא מדליק אותה. בכל מקרה אחר, הוא לא עושה כלום. ראש הקבוצה פועל לפי האלגוריתם הבא: אם הנורה כבויה, הוא לא עושה כלום, ואם היא דלוקה, הוא מכבה אותה וסופר את מספר הפעמים שהוא מכבה. לאחר שכיבה 99 פעמים, בהכרח כולם כבר היו בחדר כי כל אחד הדליק פעם אחת ואף אחד לא כיבה.
|
|
חידת המשך: נניח ולא ידוע המצב בתחילתי של הנורה בחדר. כלומר ייתכן שלפני שהוכנסו המתמטיקאים היא הייתה דלוקה, וייתכן שהיא הייתה כבויה. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?
פתרון
|
המתמטיקאים יפעלו על פי אותו אלגוריתם כמו קודם, רק שהפעם כל אחד מ-99 המתמטיקאים ידליק את הנורה הן בפעם הראשונה והן בפעם השנייה שהוא רואה אותה כבויה. ראש הקבוצה יספור הפעם עד 198. כך מובטח שאפילו אם הנורה הייתה דלוקה בהתחלה, וראש הקבוצה ספר אותה בטעות כמתמטיקאי, זה רק אומר שאחד המתמטיקאים הספיק להדליק את הנורה רק פעם אחת, ובכל מקרה כולם ביקרו בחדר.
|
|
חידת המשך 2: בנוסף לחידה הראשונה (הנורה בהתחלה כבויה), המלך מודיע למתמטיקאים כי הוא עלול לנסות לבלבל אותם ולשנות בעצמו מדי פעם את מצב הנורה - אך לא יותר מ-n פעמים. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?
פתרון
|
המצב בו לא ידוע מצב הנורה ההתחלתי שקול לכך שהנורה בהתחלה כבויה, אך למלך מותר לשנות את מצבה פעם אחת. על כן המתמטיקאים יפעלו על פי אותו אלגוריתם כמו קודם, אלא שעל כל מתמטיקאי שאינו ראש הקבוצה להדליק את הנורה 1+n הפעמים שהוא רואה אותה כבויה, וראש הקבוצה יספור הפעם עד 99*(n+1). כך מובטח ש-n הפעמים בהם המלך התערב בתהליך לא גרמו לכלול בספירה מתמטיקאי שכלל לא נכח בחדר.
|
|
|
עריכה | תבנית | שיחה
|
7
|
מה מספר העצים הפורשים של גרף מלא בעל n קודקודים?
הבהרת מושגים למי שלא מכיר:
- גרף הינו אוסף של נקודות ושל צלעות המחברות בין הנקודות.
- גרף מלא הינו גרף שבו כל נקודה מקושרת לכל שאר הנקודות.
- עץ הינו גרף שבו בין כל שתי נקודות מחבר מסלול אחד בלבד.
- עץ פורש הינו תת-גרף שהוא עץ המכיל את כל הנקודות של הגרף המקורי.
לדוגמה עבור הגרף המלא בגודל 3, קל לראות שיש 3 עצים פורשים.
פתרון
|
נוסחא זאת נקראת נוסחת קיילי והוכחה שלה ניתן למצוא בערך נוסחת קיילי.
|
|
|
עריכה | תבנית | שיחה
|
8
|
האם יש n טבעי גדול מ-2, שלגביו קיימים מספרים טבעיים x,y,z המקיימים את המשוואה: ?
במבוא לסדרת ספריו The Art of Computer Programming הציג דונלד קנות' בעיה זו כדוגמה לבעיה מתמטית בדרגת הקושי הגבוהה ביותר, אם כי המתמטיקאי פייר דה פרמה, שעסק בבעיה 330 שנה מוקדם יותר, טען שיש לה פתרון אך אין לו מספיק מקום לכותבו.
|
עריכה | תבנית | שיחה
|
9
|
האם קיימים 3 מספרים ראשוניים שונים ש:
מתחלק ב- ,
מתחלק ב-
מתחלק ב-
כאשר:
א) d=10
ב) d = 11 ?
פתרון
|
א) תשובה:
נניח בשלילה שקיימים מספרים כאלו. נניח ללא הגבלת הכלליות . המספר האי-זוגי מתחלק ב, מכאן אי-זוגי (ומכיוון שהוא ראשוני זה שקול לכך שהוא לא 2). לכן כי הראשונים הקטנים ביותר ש-q,r יכולים להיות הם 5 ו-7.
ואז נקבל ומכיוון שמספר לא יכול להתחלק במספר שגדול ממנו, לא מתחלק ב- .
ב) תשובה: קיימים: 2, 3, 5. זה גם המקרה היחיד, הרי בסעיף א' ראינו שהאי-קיום נבע מכך שאף-אחד מהראשוניים לא היה 2 ואז אזי קל להבין שזו היא השלשה האפשרית היחידה.
חידת בונוס: על איזה תנאים d צריך לענות בשביל שיהיו קיימים מספרים ראשוניים אלה?
פתרון
|
בינתיים לא נמצא פתרון מלא, אם כי נמצא ש-d>10, ש-d אינו יכול להיות כפולה של אף אחד מ-p,q או r, ושאם d<26 אז הוא אי-זוגי.
|
|
|
|
|
עריכה | תבנית | שיחה
|
10
|
מופע קסמים: על הבמה קוסם, שוליה, לוח שחמט ריק (8 על 8 משבצות) ו-64 מטבעות. הקוסם יוצא, והשוליה מזמין שני מתנדבים מהקהל. השוליה אומר למתנדב אחד לומר מספר מאחד עד 64, ולמתנדב השני הוא אומר לשים מטבעות על המשבצות בלוח איך שבא לו. מותר למתנדב לשים כמה מטבעות שהוא רוצה, או לא לשים בכלל, אבל אסור לו לשים מטבע על כמה משבצות, או לשים כמה מטבעות על אותה משבצת.
אחרי זה השוליה רשאי להסיר מטבע אחד בלבד מהלוח, או להוסיף מטבע אחד, או להשאיר את הלוח כפי שהוא. אסור לו להזיז מטבע למשבצת אחרת.
הקוסם חוזר, מסתכל על הלוח, והוא יודע איזה מספר המתנדב הראשון בחר. איך הם עושים את זה?
פתרון
|
השוליה והקוסם ממספרים מראש את משבצות הלוח מ-0 עד 63 בבסיס בינארי כך שכל מספר יכיל 8 ספרות (אם צריך מוסיפים אפסים בהתחלה) השוליה מבצע XOR על הערכים של המשבצות עליהן הונחו המטבעות (כל ספרה בנפרד) ושוב XOR על התוצאה ועל המספר שבחר המתנדב הראשון (פחות 1). התוצאה היא מספר בין 0 ל-63, והשוליה שם או מסיר מטבע במשבצת שזהו מספרה. כעת הקוסם יבצע XOR על כל ערכי המשבצות שמכוסות במטבעות והתוצאה (ועוד 1) היא המספר שבחר המתנדב.
|
|
|
עריכה | תבנית | שיחה
|
11
|
ישנם 111 עובדים שצריכים להצביע ליושב ראש מתוך שלושה מתמודדים (לא מתוך ה-111 אנשים). כל אחד שם פתק עם המועמד המועדף עליו
בוצעה הצבעה ראשונה- יצא תיקו.
הוחלט לבצע עוד הצבעה בדרך הבאה: כל אדם ישים שני פתקים, עדיפות ראשונה ועדיפות שנייה. לאחר ההצבעה השנייה שוב יצא תיקו.
מתמודד אחד מתוך השלושה הציע לשני האחרים אלגוריתם לבחירה: אתם תתמודדו בינכם, המנצח בינכם יתמודד מולי וכך ייבחר יושב ראש.
השאלה: נתח את ההצעה. האם ההצעה הוגנת? כלפי מי? ותן הסבר מדוע ההצעה אינה הוגנת.
|
עריכה | תבנית | שיחה
|
12
|
-
|
הוספה
|
13
|
-
|
הוספה
|
14
|
-
|
הוספה
|
15
|
-
|
הוספה
|
16
|
-
|
הוספה
|
17
|
-
|
הוספה
|
18
|
-
|
הוספה
|
19
|
-
|
הוספה
|
20
|
-
|
הוספה
|
21
|
-
|
הוספה
|
22
|
-
|
הוספה
|
23
|
-
|
הוספה
|
24
|
-
|
הוספה
|
25
|
-
|
הוספה
|
26
|
-
|
הוספה
|
27
|
-
|
הוספה
|
28
|
-
|
הוספה
|
29
|
-
|
הוספה
|
30
|
-
|
הוספה
|
31
|
-
|
הוספה
|
32
|
-
|
הוספה
|
33
|
-
|
הוספה
|
34
|
-
|
הוספה
|
35
|
-
|
הוספה
|
36
|
-
|
הוספה
|
37
|
-
|
הוספה
|
38
|
-
|
הוספה
|
39
|
-
|
הוספה
|
40
|
-
|
הוספה
|
41
|
-
|
הוספה
|
42
|
-
|
הוספה
|
43
|
-
|
הוספה
|
44
|
-
|
הוספה
|
45
|
-
|
הוספה
|
46
|
-
|
הוספה
|
47
|
-
|
הוספה
|
48
|
-
|
הוספה
|
49
|
-
|
הוספה
|
50
|
-
|
הוספה
|
51
|
-
|
הוספה
|
52
|
-
|
הוספה
|
53
|
-
|
הוספה
|
54
|
-
|
הוספה
|
55
|
-
|
הוספה
|
56
|
-
|
הוספה
|
57
|
-
|
הוספה
|
58
|
-
|
הוספה
|
59
|
-
|
הוספה
|
60
|
-
|
הוספה
|
61
|
-
|
הוספה
|
62
|
-
|
הוספה
|
63
|
-
|
הוספה
|
64
|
-
|
הוספה
|
65
|
-
|
הוספה
|
66
|
-
|
הוספה
|
67
|
-
|
הוספה
|
68
|
-
|
הוספה
|
69
|
-
|
הוספה
|
70
|
-
|
הוספה
|
71
|
-
|
הוספה
|
72
|
-
|
הוספה
|
73
|
-
|
הוספה
|
74
|
-
|
הוספה
|
75
|
-
|
הוספה
|
76
|
-
|
הוספה
|
77
|
-
|
הוספה
|
78
|
-
|
הוספה
|
79
|
-
|
הוספה
|
80
|
-
|
הוספה
|
81
|
-
|
הוספה
|
82
|
-
|
הוספה
|
83
|
-
|
הוספה
|
84
|
-
|
הוספה
|
85
|
-
|
הוספה
|
86
|
-
|
הוספה
|
87
|
-
|
הוספה
|
88
|
-
|
הוספה
|
89
|
-
|
הוספה
|
90
|
-
|
הוספה
|
91
|
-
|
הוספה
|
92
|
-
|
הוספה
|
93
|
-
|
הוספה
|
94
|
-
|
הוספה
|
95
|
-
|
הוספה
|
96
|
-
|
הוספה
|
97
|
-
|
הוספה
|
98
|
-
|
הוספה
|
99
|
-
|
הוספה
|
100
|
-
|
הוספה
|