בכפר זוג

[the YOOK]

../images/Emo35.gifבכפר זוג

בכפר זוג, שבו 64 תושבים, מאוד אוהבים להקים ועדות. כל כך הרבה ועדות קמו בכפר, שההתושבים כבר לא ידעו נפשם מבלבול, בנוסף לכן, בהרבה מהועדות שקמו היה מספר זוגי של תושבים, וכך לפעמים לא הצליחו להחליט בועדה החלטות... התושבים החליטו שכדי לייעל ולצמצם את מספר הועדות יש לשמור על שני חוקים: א. גודל כל ועדה יהיה אי זוגי. ב. גודל חיתוך כל 2 ועדות יהיה זוגי (כלומר מספר האנשים המשותפים ל- 2 ועדות מסויימות הוא תמיד זוגי). מהו המספר המקסימלי של ועדות שניתן להקים בצורה זו? - כמובן, תשובות רק יתקבלו עם הוכחה/נימוק.

 

[slallum]

אממ

ניקח לדוגמא איש א' לוועדה A (אי זוגי) ואיש ב' לועדה B (גם אי זוגי), החיתוך בין הועדות הוא 0 - וזה זוגי. ככה שבעצם אפשר ליצור 64 ועדות מ-64 אנשים שונים. אבל עכשיו אסור ליצור עוד אף ועדה, כי ועדה C אשר מורכבת מאיש א' תיצור חיתוך אי זוגי עם ועדה A (איש א' נמצא בשניהם). וככה גם ועדה עם 3 אנשים או יותר. אז בנתיים הצלחתי למצוא 64, אבל כמו שאני מכיר את YOOK הפתרון הוא בטח יותר מ-64, לפחות פי 2

 

[the YOOK]

זה פיתרון חלקי...

הוכחת שאין יותר מ- 64 ועדות עבור המקרה בו אתה מתחיל בכך שכל אדם מהווה ועדה מלכתחילה. אבל מה עם מקרים שונים? - למשל, דרך נוספת ליצור 64 ועדות היא שכל 63 תושבים בכפר יצרו ועדה (בדוק שזה באמת מקיים את החוקים)... האם במקרה זה יכולות לקום עוד ועדות? ומה עם המקרה הכללי? הפתרון שאני מכיר, אגב, דורש קצת הכרה של מונחים באלגברה לינארית, אבל לדעתי אפשר גם בלי.

 

[slallum]

יש מצב שאתה מכוון אותי קצת? ../images/Emo13.gif

 

[the YOOK]

ובכן,

קודם כל, אתה צדקת... אכן 64 הוא מספר הועדות המקסימלי. דבר שני, אם אתה מכיר קצת אלגברה לינארית, תחשוב בכיוון של תלות לינארית (או אי- תלות...). עוד כיוון שאתה יכול לנסות הוא להמשיך במה שהתחלת. תחשוב מדוע לא יתכנו 65 ועדות (ולכן גם לא יותר).

 

[DirectT]

[התשובה] זה לא המקסימלי, לדעתי...

אם חלק מהאנשים משתתפים בכמה ועדות אז יש לנו פה עניין עם תורת הקבוצות יותר מאלגברה רגילה, לדוגמא: נגיד שיש 3 אנשים, ויכול להיות מספר אי זוגי של ועדות איש א',ב,ג - שייכים לקבוצה אחת א, ב,ג, ל-3 קבוצות בהתאמה אם כך יש לנו כאן 4 קבוצות, והמספר הזה רק עולה עם מספר האנשים, כך שעבור 63 [או 64, לא עקרוני] המספר המקסימלי הוא עצום. כל זאת, בהנחה כמובן, שאדם יכול להשתתף ביותר מועדה אחת.

 

[the YOOK]

../images/Emo13.gif נסה להוכיח ותיווכח...

ואדם יכול להשתתף ביותר מועדה אחת... אחרת לא היה הגיוני להציב כלל על חיתוך הועדות... הדוגמא שלך, בגלל הכלל הנ"ל, נופלת. וכן, בעזרת אלגברה רגילה (לא תיכונית כמובן...), וקצת כושר תיחכום ניתן לפתור את הבעיה.