5 חידות קשות

[freedom rider]

5 חידות קשות

5 חידות קומבינטוריות קשות בבלוג inSite שעורך גיל כהן.

 

[טלמון סילבר]

../images/Emo58.gif ניסיון למספר 1

סה"כ מספר האפשרויות להוצאת פתקים בסדר עולה, שווה למספר הצירופים (C) מ-99 על 5. סה"כ מספר האפשרויות להוצאת 5 פתקים, כאשר הסדר חשוב, שווה למספר ה... (A) מ-99 על 5. לכן התשובה היא:

p = C(99,5) / A(99,5) = (A(99,5)/P(5)) / A(99,5) = 1/P(5) = 1/5! = 1/120​

 

[טלמון סילבר]

../images/Emo58.gif ניסיון למספר 4.

1 = (p + (1-p))^n = Σ{i=0,1,2,...,n}C(n,i) * p^i * (1-p)^(n-i) (1-2p)^n = (-p + (1-p))^n = Σ{i=0,1,2,...,n}C(n,i) * (-p)^i * (1-p)^(n-i) Σ{i=0,2,4,...,[n/2]*2}C(n,i) * p^i * (1-p)^(n-i) = = [(1-2p)^n + 1]/2​

 

[Calius]

נסיון ל- 2

נחלק את המשולש ל- 4 מש"צ בעלי אורך צלע השווה לחצי אורך הצלע המקורית. שרטוט עקום מצורף: ^ \ / \ / \_____/ \ / \/ \ / \ / \_____/\____/ ע"פ שובך היונים יש משולש קטן אחד בו יש שתי נקודות. מרחקן אחת מהשנייה מקיים את התנאי.

 

[טלמון סילבר]

../images/Emo45.gif

 

[amni]

הניסוח של החידה השניה מטעה

אבל הפתרון שלך נכון. הניסוח הנכון של התרגיל צריך להיות: בהינתן 5 נקודות בתוך משולש שווה צלעות, אפשר תמיד למצוא זוג נקודות מבין ה- 5 כך שהמרחק בין זוג הנקודות הוא לכל היותר חצי צלע המשולש. הפתרון (הקרדיט שלך) ללא שירטוט (שהשתבש) הוא כך: יהיו A ,B ו- C מרכזי צלעות המשולש שווה הצלעות, אז חצאי הצלעות של אותו משולש יחד עם הקטעים AB BC CA מחלקים את המשולש ל- 4 משולשים שווי צלעות "קטנים" כאשר אורך צלע בכל משולש קטן הוא חצי אורך צלע המשולש המקורי. ברור (לפי עקרון שובך יונים) שמבין 5 הנקודות יש לפחות זוג נקודות שנמצא בתוך משולש קטן מהסוג שתואר. ברור שהמרחק בין נקודות הזוג קטן מצלע המשולש הקטן (זה גם טעון הוכחה אבל לא נהיה קטנוניים כי זה שגרתי).

 

[שם עצם]

2 שאלות:

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

 

[טלמון סילבר]

צריך להוכיח שלא יתכן מצב, שהמרחק

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

 

[טלמון סילבר]

טוב, גם מס' 3 פשוט מאוד.

 

[1אברהם]

../images/Emo58.gif ניסיון ל 3

הסידרה נתונה על ידי

an=1+3*n n=0,1,2....33 כדי לקבל סכום 104 104=an1+an2=1+3*n1+1+3*n2=2+3*(n1+n2) 102=3*(n1+n2) 34=n1+n2​

כלומר מתוך הסידרה של השלמים 0...34 בוחרים 20 מספרים שונים וצריך ךהוכיח שלפחות 2 מהם סכומם 34 נניח בשלילה שאפשר לבחור 20 כאול שאין זוג שסכומו 34 המספר הראשון שנבחר הוא 0 אין עוד מספר בקבוצה שיחד איתו סכומם 34 המספר השני שנבחר הוא 17 אין עוד מספר בקבוצה שיחד איתו סכומם 34 נשאר לבחור עוד 18 מספרים נשים לב לכל מספר בין 1...16 יש בין זוג בקבוצה 18...33 שנותנים סכום של 34 ( למשל 1 יחד עם 33 , 2 עם 32, 3 עם 31, 4 עם 30, 5 עם 29, וכך הלאה) אבל יש לנו 18 מספרים לבחור ולכן יהיו לפחות 2 זוגות שסכומם הוא 34 כי יש 16 זוגות ואם נבחר מכל זוג רק מספר אחד ישארו לנו עוד 2 בחירות שחיבות ליפול על זוגות שכבר בחרנו ( עקרון שובך יונים )

 

[טלמון סילבר]

הצעת דרך לפתרון חידה 5.

הסבירות להשגת המספר 1 בדיוק ב-n נסיונות (n גדול או שווה 2) נראית לי כך: נפח המנסרה:

x_1 + x_2 + . . . + x_(n-1) =< 1 x_1 >= 0 . . . x_(n-1) >= 0​

במרחב n-מימדי, שזו סבירוּת אי-השגת 1 ב-(n-1) הנסיונות הקודמים, פחות נפח הפירמידה (באותו מרחב):

x_1 + x_2 + . . . + x_(n-1) + x_n =< 1 x_1 >= 0 . . . x_(n-1) >= 0 x_n >= 0​

שזה שווה, אם אינני טועה:

1/(n-1)! - 1/n! = (n-1)/n!​

ותוחלת מספר הפעמים להשגת הסכום 1, כאשר יש בדיוק n נסיונות, שווה:

n[(n-1)/n!] = 1/(n-2)!​

והתוחלת עבור כל המספרים n החל מ-2 שווה:

1/0! + 1/1! + 1/2! + 1/3! + . . . = e​

זה הרעיון שהיצעתי: שימוש בסבירות גאומטרית רגילה.