שאלה 5 מועד ב' 2006
6 views
Skip to first unread message
אריאל
Jul 2, 2009, 5:52:24 AM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
בפתרון כתוב כאילו כל 3 התשובות נכונות, כלומר בכל גרף יש חתך בגודל
לפחות חצי ממספר הקשתות (שזה מה שלמדנו בתרגול).
אבל מדוע יש בכל גרף חתך בגודל לכל היותר חצי ממספר הקשתות?
לפחות חצי ממספר הקשתות (שזה מה שלמדנו בתרגול).
אבל מדוע יש בכל גרף חתך בגודל לכל היותר חצי ממספר הקשתות?
arisha84
Jul 2, 2009, 7:01:39 AM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
בדיוק מאותה סיבה.. אם החתך הממוצע הוא בגודל חצי מקשתות הגרף אז או שכל
החתכים הם בגודל בדיוק חצי או שקיים חתך גדול מחצי, ולכן בהכרח קיים גם
חתך קטן מחצי.
החתכים הם בגודל בדיוק חצי או שקיים חתך גדול מחצי, ולכן בהכרח קיים גם
חתך קטן מחצי.
Noam Schachter
Jul 2, 2009, 7:05:57 AM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
למדנו שתחולת גודל החתך המינימלי היא חצי ממספר הקשתות.
מוכיחים ע"י הגרלה של מספר קבוצה ( 1 / 2 ) לכל קודוקוד.
הסיכוי לכל קשת להיות בחתך הוא הסיכוי שקודודיה יקבל 12 או 21 - בדיוק
חצי. וזוהי תוחלת גודל החתך.
מוכיחים ע"י הגרלה של מספר קבוצה ( 1 / 2 ) לכל קודוקוד.
הסיכוי לכל קשת להיות בחתך הוא הסיכוי שקודודיה יקבל 12 או 21 - בדיוק
חצי. וזוהי תוחלת גודל החתך.
לפי חוקי התוחלת:
יש לפחות חתך אחד שגדול או שווה ל-חצי ממספר הקשתות (תשובות ב ו-א)
ויש לפחות חתך אחד שקטן או שווה ל-חצי מספר הקשתות (תשובה ג).
On 2 יולי, 12:52, אריאל <arieleva...@gmail.com> wrote:
Reply all
Reply to author
Forward
0 new messages