הבדלים בין גרסאות בדף "מערכי תירגול"
| שורה 11: | שורה 11: | ||
'''תוספת לשיעור. | '''תוספת לשיעור. | ||
| + | |||
הראינו ש-<math>(NxN,<_{cart})</math> מקיים את תנאי המינימליות. | הראינו ש-<math>(NxN,<_{cart})</math> מקיים את תנאי המינימליות. | ||
נראה זאת עבור <math>(N^k,<_{cart}) ו-(N^*,<_{cart})</math>. | נראה זאת עבור <math>(N^k,<_{cart}) ו-(N^*,<_{cart})</math>. | ||
גרסה מ־14:25, 25 בדצמבר 2012
תוספת לשיעור.
הראינו ש-
מקיים את תנאי המינימליות.
נראה זאת עבור 
.
ניתן ל NxN להוות את מקרה הבסיס. באינדוקציה, נניח ש 
מקיים את תנאי המינימליות ונוכיח עבור 
. כפי שעשינו ב-NxN, נבחר את כל המילים אשר יש להן קואורדינאטה מינימלית, ומתוכן נבחר את המילים מאורך אשר התת-מילה מאורך k-1 שאינה כוללת קואורדינאטה זאת היא המינימלית. מילים אלו יהיו המינימליות ב-.
עבור 
(לקבוצה של עדי, למעשה הוכחנו זאת במשפט הראשון, אך בטעות המשכנו לחפש את כל המינימליות, צריך רק להראות שקיימת מינימלית), בכל תת קבוצה A ניתן למצוא תת קבוצה שלה B של המילים בעלות האורך המינימלי. היות ובתת קב' B כולן מאותו אורך, ע"ס החלק הקודם ניתן לבחור מינימלית ביניהן, b,והיא תהיה מינימלית בכל A. (אם יש מילה מחוץ ל-B אשר קטנה מ-b באחת הקואורדינאטות אז הרי שלא ניתן להשוות ביניהן היות ואורכה בוודאי ארוך יותר מאורכה של b, לכן אין מילה שנמצאת מתחת ל-b ביחס)
