פורטל:מתמטיקה/חידות קשות/אוסף

1 את החידה שלפנינו חיבר המתמטיקאי האנגלי הנודע, הנרי ארנסט דודני: הסולטאן מעוניין לשלוח לקרב יחידת חיל רגלים שאת לוחמיה ניתן לסדר בשתי קבוצות ריבועיות בתריסר דרכים שונות. מה המספר המזערי של לוחמים שיש לכלול ביחידה כזו?

דוגמה: יחידה שבה 130 לוחמים ניתנת לסידור בשתי קבוצות ריבועיות בשתי דרכים שונות:

עריכה | תבנית | שיחה
2 מצא את המספר המינימלי המקיים:
  1. שתי ספרותיו האחרונות הן 56
  2. המספר מתחלק ב-56
  3. סכום ספרותיו הוא 56
עריכה | תבנית | שיחה
3
Ant Receives Honeydew from Aphid.jpg

לוקחים 28 גרגרי אורז, ומחלקים אותם לערמות בצורה כלשהי (בכל ערמה יש גרגר אורז אחד או יותר). נמלה מגיעה לערמות הגרגרים, אוספת גרגר אחד מכל ערמה - ויוצרת מכל אלו ערמה חדשה - ערמות שהיה בהן רק גרגר אחד נעלמות כמובן. הנמלה חוזרת על הפעולה שוב ושוב. למשל - אם היו רק 6 גרגרים, המסודרים בערמות 2, 2, 2 אחרי סיבוב אחד של הנמלה המצב יהיה - 1, 1, 1, 3 אחרי הסיבוב הבא - 2, 4.

במקרה של 28 גרגרים, האם קיים מצב יציב (כלומר מצב שלאחר שמגיעים אליו הוא יישאר אותו דבר אחרי כל סיבוב של הנמלה), ומהו? האם בהכרח מכל מצב שהוא, אחרי מספיק סיבובים נגיע למצב היציב (הוכיחו שכן או מיצאו דוגמת נגד)?

עריכה | תבנית | שיחה
4 מהי הספרה השמינית אחרי הנקודה בפיתוח העשרוני של המספר האי-רציונלי:

עריכה | תבנית | שיחה
5 נגדיר פונקציה בתור סכום הספרות הסופי של מספר טבעי. כלומר, לכל מספר טבעי סוכמים את סכום הספרות שלו שוב ושוב עד שמתקבל מספר בין 1 ל-9. לדוגמה: .

מצא את:

עריכה | תבנית | שיחה
6 למלך היו 100 מתמטיקאים בכלא. יום אחד הוא אסף אותם והכריז: "עד הלילה תהיו ביחד ותהיה לכם הזדמנות לגבש אסטרטגיה. לאחר מכן אשים כל אחד מכם בתא מבודד. בכל זמן שארצה אבחר מישהו באקראיות ואשים אותו בחדר שכל מה שיש בו זה נורה ומתג. מי שבפנים יוכל לשנות את מצב הנורה (אם היא הייתה דלוקה לכבות ואם כבויה להדליק) או לא לעשות כלום. בהתחלה הנורה תהיה כבויה. המטרה שלכם שבאחד הימים יבוא אלי מישהו ויגיד שכולם כבר היו בחדר לפחות פעם אחת. אם הוא יצדק, אשחרר את כולכם, אך אם יטעה, אוציא את כולכם להורג." מה צריכה להיות האסטרטגיה של המתמטיקאים?

הערה: לצורך החידה למתמטיקאים יש חיי אלמוות. כל אחד מהם נכנס מספר פעמים לא מוגבל לחדר, כלומר אין דבר כזה מישהו שנכנס בפעם האחרונה. כמו כן, אין המתמטיקאים יודעים את הזמנים בהם מוכנסים אנשים ואין הם יודעים את המספר הסידורי של כניסתם (בפרט הראשון שנכנס אינו יודע שהוא הראשון).


חידת המשך: נניח ולא ידוע המצב בתחילתי של הנורה בחדר. כלומר ייתכן שלפני שהוכנסו המתמטיקאים היא הייתה דלוקה, וייתכן שהיא הייתה כבויה. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?


חידת המשך 2: בנוסף לחידה הראשונה (הנורה בהתחלה כבויה), המלך מודיע למתמטיקאים כי הוא עלול לנסות לבלבל אותם ולשנות בעצמו מדי פעם את מצב הנורה - אך לא יותר מ-n פעמים. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?

עריכה | תבנית | שיחה
7 מה מספר העצים הפורשים של גרף מלא בעל n קודקודים?

הבהרת מושגים למי שלא מכיר:

  • גרף הינו אוסף של נקודות ושל צלעות המחברות בין הנקודות.
  • גרף מלא הינו גרף שבו כל נקודה מקושרת לכל שאר הנקודות.
  • עץ הינו גרף שבו בין כל שתי נקודות מחבר מסלול אחד בלבד.
  • עץ פורש הינו תת-גרף שהוא עץ המכיל את כל הנקודות של הגרף המקורי.

לדוגמה עבור הגרף המלא בגודל 3, קל לראות שיש 3 עצים פורשים.

עריכה | תבנית | שיחה
8 האם יש n טבעי גדול מ-2, שלגביו קיימים מספרים טבעיים x,y,z המקיימים את המשוואה: ?

במבוא לסדרת ספריו The Art of Computer Programming הציג דונלד קנות' בעיה זו כדוגמה לבעיה מתמטית בדרגת הקושי הגבוהה ביותר, אם כי המתמטיקאי פייר דה פרמה, שעסק בבעיה 330 שנה מוקדם יותר, טען שיש לה פתרון אך אין לו מספיק מקום לכותבו.

עריכה | תבנית | שיחה
9 האם קיימים 3 מספרים ראשוניים שונים ש:

מתחלק ב- ,

מתחלק ב-

מתחלק ב-

כאשר:
א) d=10
ב) d = 11 ?

עריכה | תבנית | שיחה
10 מופע קסמים: על הבמה קוסם, שוליה, לוח שחמט ריק (8 על 8 משבצות) ו-64 מטבעות. הקוסם יוצא, והשוליה מזמין שני מתנדבים מהקהל. השוליה אומר למתנדב אחד לומר מספר מאחד עד 64, ולמתנדב השני הוא אומר לשים מטבעות על המשבצות בלוח איך שבא לו. מותר למתנדב לשים כמה מטבעות שהוא רוצה, או לא לשים בכלל, אבל אסור לו לשים מטבע על כמה משבצות, או לשים כמה מטבעות על אותה משבצת.

אחרי זה השוליה רשאי להסיר מטבע אחד בלבד מהלוח, או להוסיף מטבע אחד (למשבצת עליה אין מטבע), או להשאיר את הלוח כפי שהוא. אסור לו להזיז מטבע למשבצת אחרת.

הקוסם חוזר, מסתכל על הלוח, והוא יודע איזה מספר המתנדב הראשון בחר. איך הם עושים את זה?

עריכה | תבנית | שיחה
11
-
הוספה
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
-
הוספה