הנה חידונת

jaXon

New member
הנה חידונת

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

איייייל

New member
לא ניסיתי להביא הוכחה מלאה

מה שכתבתי זה רק הרעיון של ההוכחה... את ההוכחות המלאות אני משאיר למתמטיקאים
 

jaXon

New member
הוא נתן כמעט הוכחה מלאה

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

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

jaXon

New member
מקווה שההסבר הבא ברור

ניקח דוגמא : 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 סכום שלוש השורות הראשונות הוא (2,2,2,0) - כל הערכים זוגיים. אבל אם נבצע סכום וקטורי, כאשר נתייחס לכל וקטור כאל וקטור מסוג Z2^4 (כלומר כל אחד מ4 הקואורדנטות הוא משדה Z2), אז נקבל סכום (0,0,0,0). זה תמיד יתרחש כאשר הסכום הרגיל מכיל רק איברים זוגיים (כי ב Z2 מתקיים 1+1=0). נניח גודל הטבלה n. נגדיר מרחב וקטורי V להיות Z2^n, מעל שדה Z2. ברור כי כל שורה או עמודה בטבלה הם וקטורים מהמרחב הזה. 1) הסכום הרגיל של וקטורים (שמכילים 0 ו1 בלבד) מכיל מספרים זוגיים בלבד אם ורק אם הסכום הוקטורי שלהם במרחב V הוא וקטור ה 0. (קל לראות - לפי הדוגמא למשל) 2) סכום וקטורים ב V הוא צירוף לינארי שלהם (עם כל המקדמים 1). ולפי אלגברה לינארית : בהנתן אוסף וקטורים במרחב וקטורי, קיים צירוף לינארי שלהם שנותן את וקטור האפס, אם ורק אם הוקטורים הללו תלוים לינארית. 3) מ 1 ו2 נובע שקיים אוסף שורות בטבלה שסכומם הוקטורי הרגיל מכיל רק מספרים זוגיים אם ורק אם הם תלויים לינארית במרחב V. 4) מאלגברה לינארית : בכל מרחב וקטורי מתאים שנבחר, שורות מטריצה תלויות לינארית אם ורק אם עמודותיה תלויות לינארית. 5) מ3 ו 4 נובע : קיים אוסף שורות בטבלה שסכומם הוקטורי הרגיל מכיל רק מספרים זוגיים אם ורק אם העמודות תלויות לינארית תחת V. 6) אם נוסיף כעת את טענות 2 ו 1 לטענה 5, נקבל ש: קיים אוסף שורות בטבלה שסכומם הוקטורי הרגיל מכיל רק מספרים זוגיים אם ורק אם קיים אוסף עמודות בטבלה שסכומם הוקטורי הרגיל מכיל רק מספרים זוגיים, וזה מה שרצינו להוכיח.
 
....

א. גם אני מצטרף שזה תרגיל נחמד מאוד. ב. פירוט: שם לב שב-Z2 חיבור מספר לעצמו תמיד ייתן 0. ולכן אם בחיבור רגיל סכום של אחדים ואפסים ייתן מספר זוגי אזי בחיבור מודולו 2 הסכום ייצא 0. וכן הכללה בווקטורים. אם עדיין לא הבנת אז נסה למקד את בעייתך. ג. בגלל שאם הוכחנו זאת עבור מעבר משורות לעמודות אז אפשר להוכיח זאת ע"י שימוש ב- At [אני מקווה שאתה מבין למה אני מתכוון. פעם הסברתי לך את המושג]
 
איגור, גם אני לא למדתי.

כששמעתי פעם ראשונה בחיים שלי את המילה "מחשב" הייתי ב-5 שנים יותר מבוגר מהגיל שלך היום! אמרו לנו ששם שיטה בינרית, ונוח לנו לכתוב זאת באוקטלית (בסיס 8), אז לא שאלנו שאלות, שיהיה אוקטלית, מה זה משנה? אנחנו הרי לא הולכים עכשיו לעשות חישובים כלשהם בשיטת ספירה זו או אחרת, אז מה אכפת לנו? מה יש פה ללמוד? ביחוד אם נשווה עם דברים שכבר למדתָ ואתה יודע! ובמשחק "נים" דובר בדיוק בחיבור וקטורים במודולו 2!
 
משחק "נים".

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

jaXon

New member
יפה!!

זו בדיוק הסיבה שאני מצאתי לנכונות של זה. לא מאמין שיש הסבר קצר יותר...
 
למעלה