great expectations

בפוסט קודם הבאתי חידה שנפתרה ע"י צביקה.

החידה:

תערוכה מסויימת ישנם 27 פסלים ו 11 אנשים הגיעו לצפות בה.

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

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

ולמעונינים הנה הפתרון:

ניקח את המבקר שצפה בהכי הרבה פסלים נקרא לו A. (אם יש יותר מאחד כזה נבחר אחד שרירותי).

A לא צפה בכל הפסלים, לכן ישנו פסל, x, שנצפה ע"י מבקר אחר (נקרא לו B) אבל לא ע"י A.

לכן קיים פסל אחר, y, ש A ראה ו B לא, אחרת B ראה את כל הפסלים ש A ראה  וגם ראה את פסל x, כלומר B בסה"כ ראה יותר פסלים    מ A וזו סתירה למקסמליות של A.