מספר שאלות על ההוכחה המצורפת

lalal6

New member
מספר שאלות על ההוכחה המצורפת

ראשית לגבי הביטוי של הסגמאות שמוקף בצהוב.

יש שם 3 סגמאות: את הסיגמה הראשונה נסמן ב-a, את השנייה ב-b ואת השלישית ב-c.

בעצם ממה שאני מבין, p^a מחלק את !n,

p^b מחלק את !k,

p^c מחלק את !(n-k).

מה שקצת לא מובן לי, זה איך מראים ומסבירים שהביטוי שמוקף בצהוב מחלק את n choose k.

אני מנסה להסביר זאת, אבל משהו חסר לי בהסבר...זה ההסבר:

zz n choose k = n! / k!(n-k)! zz , כאמור לעיל, p^a מחלק את המונה (קרי: מחלק את !n).

ואת המכנה מחלקים p^b וגם p^c (כל אחד מהם מחלק גורם אחד מבין שניי הגורמים).

מה שקצת חסר לי, זה איך אני יודע שאחרי החלוקות האלה, נותר מספר שלם? n choose k זה מספר שלם. אחרי שאני עושה את החלוקות האלה, מדוע אני נותר עם מספר שלם? או שבכלל זה לא אמור לעניין אותי אם אני נותר עם מספר שלם או לא?


כעת לגבי העמוד השני של ההוכחה:

מה הסיבה שאני יכול להציג את n לפי בסיס p? (שורה ראשונה בעמוד השני. שכחתי לסמן את זה בצהוב).


שורה לאחר מכן, חילקו ב-p^i, לכן בכל מחובר בסכום, החזקה מעל p היא j-i...החלק הזה מובן לי. אין בעיה איתו.

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

אני רוצה לוודא שהמעבר הזה ברור לי ע"י הוספת מעבר כזה: ערך שלם תחתון של n חלקי p^i, שווה למעשה לסכום (מ-j=0 עד t), של ערך שלם תחתון של (nj p^(j-i ?

כעת, עבור j < i , מתקיים ש- (p ^(j-i קטן מ-1 , לכן אם גם (nj p^(j-i קטן מ-1, אז הפעלת ערך שלם תחתון תיתן אפס, ולכן סוכמים באמת אפסים. אבל מי אמר ש-

(nj p^(j-i קטן מ-1? מי אמר שהוא גדול מ-0?

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

אם n=13, p=2, k=10
אז לפי בסיס 2 מתקיים:
k = 1010
n-k = 0011
והחיבור שלהם הוא:
1101

מספר עמודות הנשא בחיבור האחרון הוא 1 (יש נשא מעמודה 2 לעמודה 3).

לכן 2 בחזקת 1, מחלק את zz 13 choose 10 zz , בעוד שלמשל 2 בחזקת 2, לא מחלק אותו.

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

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

הביטוי שבעמוד הראשון מבטא את החזקה המקסימלית של p שמחלקת את n. (קוראים לזה ה-ולואציה (valuation) או בעברית ההערכה הp-אדית של n, ומסמנים את זה v_p(n) zz).

כעת, לכל שני מספרים טבעיים a,b מתקיים ש- a מחלק את b אמ"ם החזקה pהמקסימלית של p שמחלקת את a, היא לכל היותר החזקה המקסימלית שמחלקת את b (כלומר, v_p(a)<=v_p(b) zz), לכל p ראשוני.

לכן, מכיוון שמתקיים אי-שוויון לכל p, באמת המכנה מחלק את המונה.

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

הוכחת האי-שוויון נובעת מהנוסחה שבעמוד הראשון ומהעובדה הכללית הבאה: (*) החלק השלם של x+y הוא >= ל- (החלק השלם של x) + (החלק השלם של y).

כדי לענות על השאלה מתי המנה מתחלקת ב- p, צריך לענות על השאלה השקולה, מתי מתקיים, עבור p נתון, שכל האי-שוויונות (כלומר לכל i) הם שוויונות?

לצורך כך נחזק את (*) ונשים לב שב- (*) מתקיים שוויון אם"ם (החלק השברי של x + החלק השברי של y ) קטן מ- 1.

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

lalal6

New member
בנוגע להתחלה

בהינתן מספר ראשוני כלשהו p, ומספר כלשהו n, למה החזקה הגבוהה ביותר שאשים על p, ושתחלק את !n, היא סכום הערכים התחתונים של n/p^i , כאשר i רץ מ-1 עד אינסוף?
 

lalal6

New member
סליחה..זה דווקא מובן לי

לוקחים גורמים המתחלקים ב-p, גורמים המתחלקים ב-p^2 וכן הלאה...ולכן הטור מ-1 עד אינסוף של הערכים השלמים התחתונים של n/p^i זו החזקה הגבוהה ביותר שאם נשים אותה על p, אז p בחזקתה, יחלק את !n.

למשל אם n=12 ו-p=3, אז ערך שלם תחתון של 12/3 ועוד ערך שלם תחתון של 12 חלקי 2^3 , זה 4+1=5.

כלומר החזקה הגבוהה ביותר של p שתחלק את !12 היא p^5.

כעת לגבי הביטוי עם שלושת הסגמאות בסוף העמוד הראשון. למה p בחזקתו, מחלק את n choose k?
 

lalal6

New member
המשך:

למה p בחזקתו מחלק את n choose k, בעצם עניתי על זה כבר.

אני רוצה להראות שכאשר מחלקים את המונה של הביטוי n choose k, ב-p^a, ואת המכנה של הביטוי הזה ב-p^b ו-p^c, מקבלים מספר שלם.

לא ממש הבנתי את תשובתך.
 
זה קשור לתכונות הולואציה

אם נסמן את הולואציה ה p-אדית ב v, אז לכל x,y שלמים מתקיים v(xy)=v(x)+v(y) zz. (=תכונת האדיטיביות על מכפלות). מכאן נובע שאם a מתחלק ב b אז v(a/b)=v(a)-v(b) zz (פשוט להעביר אגפים).
מכאן הטענה שלך נובעת באופן מיידי. מתקבל מספר שלם, שאינו מתחלק ב- p.

אגב, בעזרת התכונה v(a/b)=v(a)-v(b) zz מרחיבים את הולואציה ה p אדית לכל המספרים הרציונליים השונים מאפס (תוכל לראות שזה לא תלוי בייצוג של המספר הרציונלי כשבר, ושתכונת האדיטיביות נשמרת גם שם).
 
* לכל x,y טבעיים

ולא שלמים כפי שנרשם. או יותר כללית, לשלמים שונים מ- 0.
 

lalal6

New member
האמת שלא למדתי את המושגים האלה

ולואציה pאדית.

אז קצת קשה לי להבין אותך.

המשפט שאני מדבר עליו הוכח במסגרת קורס בקומבינטוריקה. :/
 
למדת אותם עכשיו

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

lalal6

New member
מדוע החזקה המקסימלית של p שמחלקת את המכנה

של הביטוי שנותר מ- zz k! (n-k)! zz, היא לכל היותר החזקה המקסימלית של p שמחלקת את המונה שנשאר מ- !n ?

בעצם הצגת טענה שאומרת ש-x מחלק את y <=> החזקה המקסימלית - k, של p, כך ש- p^k | x , קטנה שווה מהחזקה המקסימלית - 'k של p, כך ש- zz p^k' | y zz , לכל p ראשוני.

לדוגמה (אני פשוט רוצה לוודא שאני מבין את הטענה):

אם x=6 ו y=18 ו p=2, אז 6 מחלק את 18, כי 2 בחזקת 1 מחלק את 6, ו-2 בחזקת 1 מחלק את 18 ו-1 קטן שווה ל-1.

היות וצריך שהטענה תתקיים לכל p ראשוני שקטן או מ-x או מ-y, אז יש להראות גם עבור 3 ו-5. עבור 3 זה מתקיים ועבור 5 זה גם מתקיים (עם חזקה מקסימלית 0). (אני צודק?).

כעת, חזרה למשפט..במשפט, x זה מה שנשאר מ-zz k!(n-k)! zz לאחר חילוק ב- p^b ו-p^c , כאשר b זו החזקה המקסימלית של p שמחלקת את !k, ו-c החזקה המקסימלית של p שמחלקת את !(n-k) ?

y זה מה שנותר מ-!n לאחר חלוקה ב-p^a , כאשר a זו החזקה המקסימלית של p שמחלקת את !n?

מדוע מתקיים ש: החזקה המקסימלית - k, של p, כך ש- p^k | x , קטנה שווה מהחזקה המקסימלית - 'k, של p, כך ש- zz p^k' | y zz , לכל p ראשוני ??
 
יש לך קצת בלבול

לגבי החלק הראשון- הבנת נכון.

כעת, אם
a=v(n!),b=v(k!),c=v((n-k)!)

(ביחס לראשוני p מסוים), אז צריך להוכיח ש- a+b<=c לכל p כדי לראות ש- n choose k שלם.
את זה עושים בעזרת הנוסחה ל- v(x) שאתה רשמת בדף הראשון, והאי-שוויון שכתבתי לגבי החלק השלם.

שים לב שאם y=n!/p^a אז v(y)=0 (כלומר אחרי שחילקת בחזקה המקסימלית של p, קיבלת מספר שכבר לא מתחלק ב-p, כלומר שהחזקה המקסימלית המחלקת אותו היא p^0. לכן האי שוויון שאתה שואל לגביו הוא אי שוויון טריוויאלי, 0>=0.

נסה לחזור לתשובה הראשונה שלי ולהתקדם משם.
 

lalal6

New member
תגובה

כמה דברים:

1. כשאתה אומר "כדי לראות ש- n choose k שלם", אתה לא באמת מתכוון ל-n choose k, אלא אתה מתכוון למה שנשאר במונה (!n), לאחר חלוקה ב-p^a, ולמה שנשאר במכנה (=zz k!(n-k)! zz), לאחר חלוקה ב-p^b ו- p^c ??? כי הרי n choose k עצמו, שלם משיקולים קומבינטוריים.


מעתה ואילך, במקום לומר "מה שנשאר במונה לאחר חלוקה ב-p^a בלה בלה בלה...", אני אומר מונה ומכנה (כשהכוונה היא לאחר החלוקה של כל אחד מהם, ולא למונה ולמכנה המקוריים בביטוי n choose k ).

2. אם התשובה לשאלה 1 היא "כן", אז מהטענה שכתבת בהתחלה
(" לכל שני מספרים טבעיים a,b מתקיים ש- a מחלק את b אמ"ם החזקה pהמקסימלית של p שמחלקת את a, היא לכל היותר החזקה המקסימלית שמחלקת את b (כלומר, v_p(a)<=v_p(b) zz), לכל p ראשוני"),
נובע שהמכנה מחלק את המונה (שוב מזכיר שלא מדובר על המונה
והמכנה המקוריים של n choose k, אלא לאלו שמתקבלים אחרי החלוקות בחזקות של p), אם ורק אם החזקה המקסימלית של p שמחלקת את המכנה, היא לכל היותר
החזקה המקסימלית של אותו p, שמחלקת את המונה.

מי זו החזקה המקסימלית שמחלקת את המכנה? b+c .
מי זו החזקה המקסימלית שמחלקת את המונה? a.

לכן מהטענה שלך, אני מסיק שהמכנה מחלק את המונה, אם ורק אם b+c <= a .

אתה כתבת a+b<=c .

האם טעית? או שאני טועה? חשוב לי לדעת, כדי לוודא שאני איתך בכלל ושאני מבין על מה אתה מדבר.

במידה ולא טעיתי, על מנת לוודא שהמכנה מחלק את המונה, יש להוכיח ש- b + c <= a.

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

בדף הראשון, שורה אחת לפני השורה האחרונה, יש 3 סכומים: הסכום הראשון הוא a (החזקה המקסימלית של p שמחלקת את !n) פחות שניי סכומים: החזקה המקסימלית של p שמחלקת את !k (קרי: b) והחזקה המקסימלית של P שמחלקת את zz (n-k)! zz (קרי: c).

למעשה עליי להוכיח שהסכום הראשון, פחות השני, פחות השלישי >= 0.

וכאן אני גם אמור להשתמש בטענה שלך איכשהו...

האמת אני לא מצליח להתקדם מכאן... :/// מה שכתבתי עד לפה נכון בכלל??
 
תגובה

1. אני כן מתכוון ל- n choose k. כפי שכתבתי, אפשר לראות שהוא שלם גם משיקולים קומבינטוריים, אבל זה חשוב להבין את ההוכחה שהוא שלם בעזרת ההערכה ה p-אדית, בשביל ההמשך. (שים לב שהשאלה אם הוא שלם שקולה לשאלה אם לכל p, ההערכה v של המונה גדולה או שווה להערכה v של המכנה, כלומר לשאלה האם a >= b+c, ואילו השאלה אם בהינתן שהוא שלם, הוא מתחלק ב- p שקולה לשאלה אם ההערכה של המונה גדולה ממש מההערכה של המכנה, כלומר a<b+c).

2. אכן, נכתב בטעות a+b<= c במקום a>= b+c. השאר לא רלוונטי כי כאמור אנחנו לא מדברים על אותו השבר. אבל אחזור על מה שאמרתי בתגובה הקודמת: המספרים שאתה קורא להם המונה והמכנה, אינם מתחלקים ב-p, כי הם התקבלו מחלוקה של מספרים אחרים בחזקה המקסימלית של p שמחלקת אותם. אז לא נותר מה להוכיח לגביהם.
 
למעלה