PDA

צפה בגרסה המלאה : חידת אתגר 8



yoavzilberman
20-04-2008, 18:23
כל פעם שאהוד מגיע לחבורה מסוימת, הוא קודם כל מברר מי מכיר את מי.
בשביל לזכור את זה הוא מצייר מעגל על דף נייר, ומצייר מיתר במעגל עבור כל איש בחבורה.
אם שני אנשים מכירים זה את זה, אז הוא מסמן אותם בשני מיתרים שנחתכים, אם לא – הוא
מסמן אותם באמצעות מיתרים שלא נחתכים. אם לשני מיתרים יש קצה משותף, נגיד שהם נחתכים.
אהוד משוכנע, שאפשר לצייר תרשים כזה עבור כל חבורה. האם הוא צודק?

אריאל
20-04-2008, 20:18
עבור קבוצה גדולה לדעתי לא, בגלל הדרישה שייחתכו \ ייגעו בקצה אחד של השני

yoavzilberman
22-04-2008, 09:18
נכון מאוד!
ההוכחה:

נניח שיש לנו N אנשים ממוספרים, 1, 2, 3, ..., N.
אז יש שם זוגות של אנשים. כל זוג יכול להיות זוג של אנשים שמכירים או זוג של אנשים שלא מכירים, זה 2 אפשרויות.
לכן מקבלים שיש חבורות שונות מבחינת הקשרים של היכרות.
אהוד טוען שהוא יכול לצייר תרשים עבור כל אחת מהחבורות הללו.
כאשר הוא מצייר תרשים, אפשר להניח שאין קודקודים משותפים (זו טענה שהוכחנו במהלך הפתרון השני). לכן אפשר להכין מראש מעגל ולסמן עליו N2 נקודות. אחרי זה אהוד מתחיל לצייר. נגיד שהוא מצייר את המיתרים לפי הסדר. אז יש לו דרכים לצייר את מיתר ראשון, אחרי זה (נשארו רק 2– N2 קודקודים) יש דרכים לצייר מיתר שני, ואז יש דרכים לצייר מיתר שלישי וכן הלאה.
בשיטה כזאת אפשר ליצור תרשימים שונים. אבל עבור חבורות שונות חייבים לצייר תרשימים שונים. לכן כמות החבורות השונות אינה עולה על כמות התרשימים השונים: .
כלומר, אם עבור N מסוים נוכיח שהאי-שוויון הזה לא נכון, אז נראה שיש יותר חבורות מאשר תרשימים, ולכן יש חבורה שלא קיים עבורה תרשים!
נשאר החלק הטכני של חישוב.
קל לראות שעבור N=19 זה לא נכון: 19∙20 < 400 < 210. סתירה

אליקוקוס
18-05-2008, 19:07
מבחינה סוצי אירגונומית זה אפשרי וניתן להפריך הוכחה זו ע''פ הסילבוס השיטתי של המכינקה המודרנית

אריאל
19-05-2008, 20:35
לך על זה ;)

מאור עטר
18-06-2010, 00:30
חחחחח