כפר זוג- פתרון.
לפני כשבוע נתתי חידה על כפר זוג. ולמי שלא זוכר- כאן. מכיוון שהחידה עדיין לא נפתרה, אציג בזאת את הפתרון (האלגנטי ביותר) שאני מכיר. לפני שמוכיחים כי בעצם מספר הועדות המקסימלי האפשרי הוא 64, יש להבין קצת מושגים בסיסיים באלגברה לינארית. תוכלו לקרוא קצת על הנושא- כאן2. כדאי לקרוא את הסיכומים לא רק בשביל פתרון החידה, אלא גם כי בכלליות זה מתמטיקה פשוטה ונחמדה. (זה אולי נראה קצת קשה... אבל אפשר לדפדף קצת ולקרוא עד שמבינים את המושגים החשובים. הסיכומים כאן קצת מרחיבים על נושאים פחות חשובים לעניין זה כמו שדות ומספרים מרוכבים- כל הזכויות שמורות (כמעט) לדינה זיל). . . . כעת, אחרי שסיימנו לקרוא סעיפים 1-3, נוכל להוכיח את מה שרצינו... נסתכל על המרחב ממימד 64 מעל Z_2 (השדה שכולל 0 ו- 1). לכל שני וקטורים
לפני כשבוע נתתי חידה על כפר זוג. ולמי שלא זוכר- כאן. מכיוון שהחידה עדיין לא נפתרה, אציג בזאת את הפתרון (האלגנטי ביותר) שאני מכיר. לפני שמוכיחים כי בעצם מספר הועדות המקסימלי האפשרי הוא 64, יש להבין קצת מושגים בסיסיים באלגברה לינארית. תוכלו לקרוא קצת על הנושא- כאן2. כדאי לקרוא את הסיכומים לא רק בשביל פתרון החידה, אלא גם כי בכלליות זה מתמטיקה פשוטה ונחמדה. (זה אולי נראה קצת קשה... אבל אפשר לדפדף קצת ולקרוא עד שמבינים את המושגים החשובים. הסיכומים כאן קצת מרחיבים על נושאים פחות חשובים לעניין זה כמו שדות ומספרים מרוכבים- כל הזכויות שמורות (כמעט) לדינה זיל). . . . כעת, אחרי שסיימנו לקרוא סעיפים 1-3, נוכל להוכיח את מה שרצינו... נסתכל על המרחב ממימד 64 מעל Z_2 (השדה שכולל 0 ו- 1). לכל שני וקטורים
v_1=(a_1,a_2,...,a_64), v_2=(b_1,b_2,...,b_64)
נגדיר "מכפלה":<v_1,v_2>=a_1*b_1+a_2*b_2+...+a_64*b_64
קבוצה של וקטורים תיקרא "מיוחדת" אם "כפל" של כל שני וקטורים שונים יהיה 0, ו"כפל" של וקטור עם עצמו יהיה 1. כעת נוכיח כי קבוצה "מיוחדת" היא תלתי תלויה לינארית. נניח שקיימים t_1,...t_n סקלרים בשדה, כך ש-t_1*v_1+t_2*v_2+...+t_n*v_n=0
לכל i ניקח "נכפול" את המשוואוה משני הצדדים עם הווקטור E_i שהוא 0 בכל המקומות, חוץ מבמקום ה- i בו יש 1. נקבל t_i=0. לכן כל המקדמים מתאפסים, ולכן קבוצה הוקטורים בלתי תלויים לינארית. כעת נחזור לכפר זוג, ונניח שיש m ועדות שמקיימות את התנאים. נגדיר u_j את הוקטור שמציין את הועדה ה- j, כאשר חברי הכפר ממוספרים מ- 1 עד 64, ואם הבן אדם ה- i נמצא בועדה ה- j אז בוקטור u_j במקום ה- i יש את המספר 1. מתנאי א' קל לראות שנובע כי "כפל" של וקטור ועדה בעצמו ייתן תמיד 1 (מאי זוגיות האנשים בועדה), ו"כפל" של שתי ועדות שונות יתן 0 (מזוגיות החיתוך), לכן קבוצת כל הועדות היא קבוצה "מיוחדת", ולכן בלתי תלויה לינארית, ולכן לא יכולה להיות גדולה יותר מ- 64. מש"ל עכשיו, נכון שזה היה ארוך.... אבל נחמד, לא?