מסיבת יום הולדת לביצה (מקבץ חידות)

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

1) “פרדוקס יום ההולדת” - נניח שאנחנו נמצאים במסיבה, וכחלק ממשחק חברתי מופרע אנחנו רוצים למצוא שני אנשים שנולדו באותו יום בשנה (לא בהכרח באותה שנה). ההנחה (השגויה, אבל לא חשוב) שלנו היא שימי ההולדת מתפלגים אחיד - דהיינו, שההסתברות שמישהו נולד ביום מסויים בשנה היא 1/365 (אנחנו מתעלמים משנים מעוברות). ברור (למה?) כי הסתברות של 100% לפיה יהיו במסיבה שני אנשים שנולדו באותו היום אפשרית רק אם יש במסיבה 366 אנשים. השאלה היא כמה אנשים צריך שיהיו במסיבה כדי לקבל הסתברות של 50% לפחות.

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

2) ביציאדה: נניח שיש לנו בניין בן 100 קומות, ושתי ביצים קשוחות. האתגר - לבדוק מה הקומה המקסימלית שממנה ניתן להפיל את הביצים והן עדיין לא תשברנה (כלומר, מהו n כך שאם משליכים ביצה מקומה n ומטה היא לא נשברת, אך אם משליכים אותה מקומה n+1 היא כן נשברת). הבדיקה היחידה שמותר לנו לעשות היא להשליך ביצה מקומה כלשהי; אם היא נשברה, בעסה. אם לא, אפשר להשתמש בה שוב.

כמובן שפתרון נאיבי הוא זה: “זרוק את הביצה מקומה 1; זרוק אותה מקומה 2; וכו’ וכו’”, ושיטה זו מבטיחה שנמצא את הפתרון הנכון, אבל במספר די גדול של זריקות (עלול להיות 100). המטרה היא להביא למינימום את מספר הזריקות שלנו - מה תהיה השיטה שלנו, וכמה זריקות נצטרך בה?

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

הצלחתם? עכשיו לאתגר קצת יותר גדול - כעת רואים 10 אנשים, והמטרה היא להוכיח שאו שיש שלישיה שכל חבריה הם חברים בנפש, או שיש רביעיה שכל חבריה הם אויבים בנפש.

4) ועכשיו למשהו שלא דורש שום חשבון, אבל לדעתי טמון בו רעיון מתמטי מקסים. שני חברים מתהלכים ביער. אחד מהם מצביע על עץ ומתרברב: “אני יכול במבט אחד לדעת כמה עלים יש על כל עץ!”. השני, מתמטיקאי במקצוע, מביט בו בפקפוק, מצביע על העץ הקרוב ושואל “כמה?”. עונה לו החכמולוג: “1,301 עלים!”.

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

בהצלחה!