GRE Subject Test · GRE Mathematics · נושא 26
הכנה למבחן GRE לתואר ראשון. מטרות מקומיות בתוך היקף ETS הנבדק; זהו הוראה מקורית, ולא מבחן רשמי או חיזוי ציון.
תנאי קדם: מקדמי בינומי, משלימים ועקבות הצגה.
הרכבה חלשה: הקצאה מסודרת של סך כלל לחלקים של מספרים שלמים אי-שליליים.
אינבריאנט לולאה: תכונה הנשמרת לפני ואחרי כל איטרציה של לולאה.
| English | עברית |
|---|---|
| weak composition/wiːk ˌkɒmpəˈzɪʃn/ | הרכבה חלשה |
| loop invariant/luːp ɪnˈveərɪənt/ | אינווריאנט מחזורי |
מספר הפתרונות של מספרים שלמים אי-שליליים של x₁+⋯+x_k=n הוא C(n+k−1,k−1), עבור n≥0 ו-k≥1. נגלם n כוכבים זהים המופרדים ל-k קופסאות ממונות על ידי k−1 פסיסים; פסיסים סמוכים ופסיסי קצה מאפשרים כניסות אפס. הקופסאות נבדלות זו מזו, האובייקטים אינם נבדלים. ספירת טוקנים שונים תעניק במקום זאת לכל טוקן באופן עצמאי, ותניב k^n לפני שאר האילוצים. החלט על הדגם מה שהאובייקטים והקבלנים מייצגים, ולא מתוצאה בינומית בעלת מראה מוכר.
עבור הקצאות חיוביות x_i≥1, השתמשו ב-z_i=x_i−1; הסך הנותר הוא n−k, מה שמניב C(n−1,k−1) כאשר n≥k. גבולים תחתונים כלליים יותר x_i≥a_i מטופלים על ידי חיסום כל a_i. ישנות לפחות אפס אחד היא המשלימה של כל הכניסה חיובית: חסרו C(n−1,k−1) מהסך האי-שלילי. מקרים חופפים כמו בדיוק שתי תיבות ריקות דורשים ספירה שונה; חיסום כל מקרה תיבה ריקה בנפרד מכפיל שגיאה בחפיפות שלהם.
עקוב אחר סכמת זרימה ביצוע statement אחד אחר אחד, ורשום משתנים בטבלה. הבדל בין הטלה לבין בדיקת שוויון מתמטית; צד ימין של הטלה משתמש בערך הישן לפני ההחלפה. רשום איזה ענף יבוצע לאחר מכן ואילו משתנים יושבו מחדש. מועמד חדש לסביבה חיצונית עשוי לשבת מחדש סכמה פנימית ללא לשבת את המועמד עצמו. עבור תהליך שמווסף 1,3,5,… ל-S מאפס, לאחר m הוספות S=m² והתוסף הבא הוא 2m+1.
אינבריאנט לולאה נכון לפני ואחרי כל איטרציה. אינבריאנט הסכום-ריבועים מתקיים בתחילה ב-m=0 ונשמר כי m²+(2m+1)=(m+1)². אינבריאנט לבדו אינו מוכיח הגעה לסוף. לבדוק אם מספר שלם N≥0 הוא ריבוע על ידי הוספת מספרים זוגיים עד S≥N, S גדל ללא גבול; במשוואה m עולה וחייב להגיע לגבול כמו N. בקצה, שוויון מעיד על ריבוע וחריגה מעיד על אי-ריבוע. ערך מודפס חייב להישג בדרך ביצוע בפועל; דפוס מספרי סביר לבדו אינו עקוב אמיתי.
חלק 11 טוקנים זהים בין 4 קופסאות נקובות. מספר ההקצאות הלא-שליליות הוא C(14,3)=364; מספר ההקצאות החיוביות כולן הוא C(10,3)=120. לכן 244 הקצאות יש לפחות קופסה ריקה. עבור בדיסת סכום זוגי עם N=10, S מתקדם 0,1,4,9,16; הוא חורג הגבול ומדחה 10. עבור N=9 הוא יוצא ב-S=9 לאחר שלוש הוספות. התוספים הבאים הם 1,3,5,7,9; עמודות הסכום והתוסף הבא אינם צריכים להתבלבל.
אובייקטים זהים ואובייקטים נבדלים משתמשים בדגמים שונים. לפחות קופסה ריקה אחת אינה זהה למדויק אחת. במפה זרימה, שמור על סדר העדכון והחל רק משתנים שהמסלול המבוצע בפועל מאפס.
ספירת פתרונות אי-שליליים של $a+b+c=8$ עם $a\ge2$. כמה מהם גם כוללים $b,c\ge1$? כמה מהקבוצה הראשונה יש להם לפחות אחד מ-b,c שווה לאפס?
הציבו $u=a-2$. אזי $u+b+c=6$ יש לו $\binom82=28$ פתרונות אי-שליליים. דרישת b,c חיוביים וחיסום אחד מכל אחד נותן סך של ארבעה בשלושה משתנים אי-שליליים, שנמדד על ידי $\binom62=15$. ספירת המשלימה היא $28-15=13$. ישירות b=0 נותן שבעה, c=0 נותן שבעה, ושניהם אפס נספר פעמיים, מה שמניב $7+7-1=13$.
עקוב אחר אלגוריתם זה עבור N=15 ו-N=16: התחל S=0, k=1; בזמן ש-S<N, בצע S=S+k, ולאחר מכן k=k+2; דווח האם S=N. נסח אינווריאנט, והוכח גימור עבור שלם $N\ge0$.
לאחר m איטרציות, $S=m^2$ ו$k=2m+1$. זוגות העקוב (S,k) הם $(0,1),(1,3),(4,5),(9,7),(16,9)$. לכן 15 נדחה על ידי חריגה ו16 מתקבל. האינבריאנט מתקיים בתחילה ונשמר כי $m^2+(2m+1)=(m+1)^2$. הסכום גדל ללא גבול, ולכן יגיע לבסוף או יעלה על N; לדוגמה m=N מספיק כאשר N חיובי. עבור N=0 הלולאה מושהה והשוויון מתקיים. אינבריאנט לבדו לא יקיף הגעה לסוף.
לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.
טוען נושאים…