חידה מתמטית

[wow1234 תפוז]

חידה מתמטית

תהי פונקציה f שעבור כל x = (x1,x2,..,xn)^t , f(x) = max(xi | i in {1,..,n} ) zz ותהי A מטריצת nxn כך שלכל x כנ"ל, f(x) = f(Ax) zz. הוכח כי קיים m טבעי עבורו A^m = Id_nxn. (אינדו'?)

 

[ייץ]

נסיון

לא יודע לנסח זאת בשפה מתמטית אבל, תשתכנע ש A חייבת להיות פרמוטציה על ה Xים. כלומר בהנתן X1,X2,,,,XN אזי A(X) dd יהיה חייב להשאיר את ה Xים רק לא באותו סדר. (תניח שאחד ה Xים משתנה אז תבחר וקטור X כזה שהמינימום הוא זה שמשתנה ותקבל סתירה עם ה f.) בהנתן ש A מבצעת פרמוטציה אז קיים K כך ש A^K יתן את מטריצת היחידה. מקווה שאני לא טועה.

 

[גיל14]

מישהו יכול לנסות להרחיב על כך מתמטית?

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

 

[MelodicTruth]

רעיון:

כפל ב-(0, 0...1, 0...0) מראה שהאיבר הגדול ביותר בכל עמודה הוא 1, וקיים לפחות אחד כזה בכל עמודה. כפל ב-(0, 0...1-, ...0, 0) מראה שכל האיברים במטריצה אינם שליליים, ושקיים לפחות 0 אחד בכל עמודה. עכשיו, כפל ב-(1/2, 1/2...1...1/2, 1/2) בהתאם למקומות בהם מופיעה הספרה 1, מראה כי בכל שורה בה מופיע 1, שאר הספרות הן בהכרח 0. לכן, A התקבלה מ-I ע"י החלפת שורות. אם אני כותב ב-4 לפנות בוקר, רוב הסיכויים שאני בכלל לא בכיוון. תנו צ'אנס בכל זאת.

 

[גיל14]

בעיה עם זה

הכפל בe_i מראה שהאיבר הגדול ביותר בכל עמודה הוא יכול להיות גם 1-.

 

[MelodicTruth]

רק רגע,

אנחנו מדברים על {max{x1...xn או על {|max{|x1|...|xn? אם זה המקרה הראשון (אמנם יש לי בעיה עם הפונטים בתפוז, אבל זה מה שאני רואה על המסך), אז לא נראה לי שאתה צודק. למרות שהטענה שלך גורמת לי להאמין שזה המקרה השני...

 

[גיל14]

המקרה השני כמובן ../images/Emo13.gif

 

[ייץ]

הוכחה פשוטה

אם מוסכם ש A מבצעת פרמוטציה בלבד אז: (כי אם יש איבר שמשתנה אזי בהכרח קיים וקטור X כך שהאיבר המקסימלי בוקטור ישתנה ואז F של X לא תהיה F של AX.)

if A(x) --> permute of X then A^2(x) --> permute of X A^2(x)=A[A(x)]=A[permute of X] = permute of X. כיוון ש אן סופית מספר הפרמוטציות הוא סופי לכן לפי שובך היונים או ש A=I , A^2=I , A^4=I , A^8=I ... או A^(2^t)(x) = A^(2^p)(x) p>t כי באיזשהו שלב הפרמוטציה תחזור על עצמה. A^(2^p)-A^(2^t)=0 A^(2^t)*[A^(2^p-2^t)-I]=0 A^(2^t) !=0 ==> A^(2^p-2^t) = I מש"ל​

 

[ייץ]

אם אני לא טועה

המטריצה A צריכה להיות עם 1 יחיד בכל שורה ובכל עמודה. למשל:

0 1 0 0 0 1 1 0 0​