חידה

[טיקטי1]

חידה

http://alefefes.macam.ac.il/riddles/riddle.asp?n=217

 

[Halfbaked]

חידה יותר קשה

החליפו את המילה "טבעיים" במילה "ממשיים".

 

[Halfbaked]

חידה עוד יותר קשה

החליפו (בחידה היותר קשה) את המספרים 10,11,5 בביטויים 2n,2n+1,n בהתאמה.

 

[טלמון סילבר]

../images/Emo35.gif שתי חידות נוספות,

אחת קלה ואחת כנראה קשה (למרות שלא פתרתי את השתיים האחרונות). נתונה (בשתי החידות) מטריצה 2n+1 על 2n+1. באלכסון הראשי אפסים. כל שאר האלמנטים שווים 1 או מינוס 1, כאשר בכל שורה בדיוק n אלמנטים שווים 1, ו-n אלמנטים שווים מינוס 1. חידה ראשונה (הקלה): הוכיחו שקוצב המטריצה שווה 0. חידה שנייה (כנראה קשה): הוכיחו שמידת המטריצה שווה 2n. אני מקווה שהובנתי.

 

[yeshgvul]

מה זה קוצב?מה המונח באנגלית?../images/Emo12.gif

ומידה? האם המידה היא הדרגה ? (מספר השורות הבלתי תלויות)

 

[טלמון סילבר]

אכן: דטרמיננטה ודרגה.

 

[yeshgvul]

יש לי תחושה שהקוצב הוא ה det...

 

[טלמון סילבר]

../images/Emo35.gif חידה בקומבינטוריקה.

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

 

[djdror]

../images/Emo62.gifניחוש בלי הוכחה

לשאלה הראשונה שלך :

3^n-2​

 

[djdror]

זה בסדר טלמון - אני לבד רואה שמגיע

לי

 

[Halfbaked]

טלמון, אני הייתי מוריד את הכובע

אבל אין לי.. חידת האבנים שוות המשקל (בגירסתה ה"עוד יותר קשה") הטרידה אותי כבר זמן רב, ולא מצאתי לה פתרון. חשבתי על המטריצה האמורה, אך לא עלה בדעתי להסתכל עליה כמעל השדה Z2, כלומר להתחשב בזוגיות הדטרמיננטה בלבד. היום בבוקר ראיתי בחטף את הפתרון שלך, ובדרכי לעבודה ניסיתי להוכיח לעצמי את טענתך לגבי זוגיות הדטרמיננטה. עד מהרה נצבה לנגדי השאלה בניסוחה הנ"ל ("חידה בקומבינטוריקה"), ומיד פתרתי אותה, תוך שימוש במשפט ההכלה וההדחה, אותו למדתי בקורס מתמטיקה דיסקרטית בעבר הרחוק מדי. משפט ההכלה וההדחה: נתונות n קבוצות סופיות. עצמת איחוד הקבוצות שווה לסכום עצמות הקבוצות, פחות סכום עצמות חיתוכי כל הזוגות, ועוד סכום עצמות חיתוכי כל השלשות, פחות סכום עצמות חיתוכי כל הרביעיות, ועוד ... ועוד/פחות עצמת חיתוך כל הקבוצות. לכל i בין 1 ל-n, תהי A_i קבוצת כל הסידורים המקבעים את i. עצמת כל אחת מהקבוצות: !(n-1). עצמת כל חיתוך של k קבוצות: !(n-k) (מכיוון שהחיתוך הוא קבוצת כל הסידורים המקבעים k מספרים מסוימים). לפי משפט ההכלה וההדחה, עצמת האיחוד של n הקבוצות האלה הוא:

n*(n-1)! - (n,2)*(n-2)! + (n,3)*(n-3)! - ... +/- n*1! -/+ 1 = n! - n!/2! + n!/3! - ... +/- n -/+ 1​

(כאשר (n,k) הוא "n מעל k", מספר הבחירות של k איברים מתוך n). אנו מעונינים במשלים, כלומר ב-!n פחות הביטוי הנ"ל. נקבל

n!/2! - n!/3! - ... -/+ n +/- 1​

לסיום, נשים לב שאם n זוגי, הביטוי בהכרח אי-זוגי, כי פרט לאיבר האחרון (1-/+) כל האיברים מתחלקים ב-n. מכאן שהדטרמיננטה של המטריצה בגודל זוגי המתקבלת ממחיקת השורה הראשונה והטור הראשון, היא אי-זוגית, ובפרט שונה מאפס. הדרגה של המטריצה היא לכן לפחות 2n, והשאר הסטוריה. תודה, טלמון, ושוב תודה

 

[טלמון סילבר]

~ ~ ~

אני שמח שעזרתי. על הפתרון שלך לחידה בקומבינטוריקה אחשוב בהזדמנות

 

[yeshgvul]

../images/Emo62.gif ? נסיון לראשונה

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

 

[טלמון סילבר]

../images/Emo127.gif כמובן ../images/Emo70.gif

אני רואה שקיבלתָ את המילה 'קוצב'

האמת לא למדתי מתמטיקה בארץ, ואינני מכיר את רוב המונחים בעברית. היה נדמה לי שראיתי באיזשהו מקום 'קוצב', אבל עכשיו אני כבר לגמרי לא בטוח... ומי יציב לי

או

?

 

[טלמון סילבר]

../images/Emo62.gif נסיון לפתרון העוד יותר קשה.

נתונה מטריצה ריבועית m על m: באלכסון הראשי אפסים, כל שאר האברים שווים פלוס או מינוס אחד. תרגיל: למה שווה הדטרמיננטה של המטריצה הזו במודולו 2? כלומר, האם היא מספר זוגי או אי זוגי? לפי הגדרת הדטרמיננטה (לפחות אחת ההגדרות, שהיא אקוויוולנטית להגדרות אפשריות אחרות) היא שווה לסכום כל המכפלות האפשריות של m אברים, כולם משורות שונות ומטורים שונים, כאשר כל מכפלה כזאת מוכפלת בפלוס או מינוס 1. סה"כ !m מכפלות. במקרה שלנו כל מכפלה שווה או 0, או 1 או מינוס 1, ומכיוון שמעניינת אותנו רק הזוגיות של הסכום כולו, מעניין אותנו רק מספר המכפלות השונות מ-0, ולגבי כל אבר שונה מ-0 לא חשוב לנו אם הוא שווה 1 או מינוס 1. נסמן את ערך הדטרמיננטה במודולו 2 כ-(Q(m, והשאלה היא, אם הוא שווה 0 (זוגי) או 1 (אי זוגי). נפרק את הדטרמיננטה לפי אברי השורה העליונה, סה"כ m-1 אברים שונים מ-0. כל אבר מוכפל ב... גם לזה אינני יודע איך קוראים בעברית: המשלים האלגבראי, האָדיוּנקט שלו, שזה הדטרמיננטה של המטריצה המתקבלת מהמטריצה המקורית ע"י מחיקת הטור והשורה של האבר, כפול פלוס או מינוס 1, שזה לא משנה במקרה שלנו. מתקבלות m-1 מטריצות קטנות יותר, m-1 על m-1. בכל אחת מהן אפשר להחליף ביניהן מספר שורות (מה שלא ישנה את זוגיות הדטרמיננטה), עד שהיא תיראה כך: כל האברים שאינם על האלכסון הראשי שווים 1 או מינוס 1. כל האברים על האלכסון הראשי למעט העליון השמאלי שווים 0. להבדיל מהמטריצה המקורית, במטריצות הקטנות האבר העליון השמאלי שווה 1 או מינוס 1. הבה נספור את מספר המכפלות השונות מ-0 בחישוב הדטרמיננטה של המטריצה החדשה. מספר המכפלות האלו, בהן האבר השמאלי העליון אינו משתתף, הוא בעצם (Q(m-1. מספר המכפלות האלו, בהן הוא משתתף (כנציג היחידי של השורה העליונה ושל הטור השמאלי) הוא (Q(m-2. סה"כ בכל אחת מהמטריצות הקטנות (Q(m-1)+Q(m-2 מכפלות שונות מ-0. מכאן:

Q(m) = (m - 1)[ Q(m - 1) + Q(m - 2) ]​

וכמו כן:

Q(2) = 1 Q(3) = 0​

(במקרה של m=3 יש שתי מכפלות שונות מ-0, שזה מספר זוגי). ומכאן:

Q(2n+1) = 0 Q(2n) = 1​

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

 

[טלמון סילבר]

../images/Emo62.gif לטבעיים (ולרציונליים). XOR.

לא ממש, אבל "בערך ממש"

נתונה קבוצה של m מספרים שלמים לא שליליים (בינתיים לא חשוב עם זה מספר אי-זוגי או זוגי). נתונה התכונה הבאה של קבוצת המספרים הללו: אם נשים בצד כל אחד מהם, אפשר יהיה לחלק את השאר לשתי קבוצות (לאו דווקא עם אותה כמות אברים) שסכום אבריהן שווה. טענה ראשונה: אם נחסר מכל m המספרים הנתונים מספר שלם כלשהו (כך שאף אחד מהם לא יהפוך לשלילי), התכונה תישאר תקפה לקבוצה החדשה. טענה שנייה: אם נכפיל את כל המספרים במספר כלשהו (כך שהם ישארו שלמים לא שליליים), התכונה גם כן תישאר תקפה לקבוצה החדשה. אם איש אינו מתנגד, נדלג על הוכחת שתי הטענות. נשים בצד את המספר ה-p ונכתוב את השוויון המתקיים לגבי שאר המספרים. כנ"ל נשים בצד את המספר ה-q ושוב נכתוב את השוויון לגבי שאר המספרים. נחבר את שני השוויון PER אגף (לא חשוה מי מימין ומי משמאל). בכל מקרה נקבל שסכום או הפרש המספר ה-p והמספר ה-q הוא זוגי! כי שאר המספרים יופיעו פעמיים, באגף זה או אחר, ויצטמצמו או יוכפלו. לכן למספרים ה-p וה-q אותה זוגיות: או שניהם זוגיים, או שניהם אי-זוגיים. משמע: לכל המספרים אותה זוגיוּת. אם כולם שווים 0, אז הוכחנו שהם שווים ביניהם. נניח שלא. אם כולם זוגיים נחלק את כולם ל-2 ונקבל קבוצה חדשה, השומרת על התכונה, ולכן גם לכל המספרים החדשים אותה זוגיות. אם גם הם כולם זוגיים, נחלק שוב ל-2. בסופו של דבר חייבים להתקבל מספרים אי-זוגיים, ומכיוון שגם הם ישמרו על התכונה, הם יהיו כולם אי-זוגיים. כאשר התקבלו m מספרים אי-זוגיים השומרים על התכונה, נחסר מכולם את המספר 1, ושוב נקבל מספרים זוגיים השומרים על התכונה, ושוב נחלק אותם ל-2, וכן הלאה עד ש... עד שהמספר הגדול ביותר מהמספרים המקוריים (במקרה שלא כולם היו שווים 0) יהפוך ל-1. כל המספרים האחרים יכולים להיות שווים 0 או 1, אבל מכיוון שכולם אי-זוגיים, אז גם הם שווים כולם 1. התקבלו מספרים שווים 1. אם נלך אחורנית עד למספרים המקוריים, ממילא יתקבלו מספרים שווים. זהו. אם באחד השוויונים, המתארים את תכונת הקבוצה, מספר האברים בשתי תת-הקבוצות שונה, אז כל המספרים שלנו, שכבר הוכחנו שהם שווים ביניהם, יהיו לא סתם שווים ביניהם, אלא כולם שווים 0. בפרט, כאשר m זוגי, תמיד יהיו כולם שווים 0. עבור m אי-זוגי התכונה מתקיימת תמיד כאשר כל המספרים שווים ביניהם. המעבר למספרים שלמים כלשהם: פשוט נוסיף לכולם מספר טבעי גדול, כך שלא יהיו בהם שליליים, וניווכח שכולם שווים. כנ"ל המעבר לרציונליים: נכפיל במכנה משותף.

 

[טלמון סילבר]

../images/Emo41.gif הערות חשובות מאוד ../images/Emo62.gif

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

 

[Halfbaked]

לא ירדתי לסוף דעתך..

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

 

[טלמון סילבר]

עניתי בשרשור החדש, להלן העתק:

בנוגע למספרים השלמים\רציונליים סתם כתבתי שטות, ומצאתי לנכון לציין זאת לתשומת לבם של כל משתתפי הפורום. ההתחכמות המיותרת גם התגלתה כשגוייה. עכשיו לענייננו. הטענה נמסרה לי ע"י ידיד, ואני יכול לבקש ממנו הוכחה מלאה, אבל אנסה בעצמי. נכתוב את 2n+1 המשוואות. נניח שקיים פתרון ממשי שונה מ-1:1:...:1 אזי דרגת המטריצה: m<2n. קיימת תת-מטריצה m על m שדרגתה m. ניקח בהתאם לתת-מטריצה זו m משוואות עם m נעלמים, כאשר שאר 2n+1-m הנעלמים מועברים לאגף הימני. ניתן לנעלמים שהעברנו לאגף הימני ערכים רציונליים שונים כלשהם (העברנו לפחות 2 נעלמים). מכיוון שכל המקדמים רציונליים, גם הפתרון (היחיד) ל-m הנעלמים הוא רציונלי (דטרמיננטה עם מקדמים רציונליים חלקי עוד אחת כזאת). קיבלנו 2n+1 מספרים רציונליים, לא כלם שווים, המקיימים את 2n+1 המשוואות המקוריות.