מתמטיקה בדידה                       				  	סמסטר ב' תשס"ו
מ. טרסי							מועד א' 23.6.2006

פתרון הבחינה
פתרון מלא - בכחול
שגיאות אופיניות והערות על הבדיקה -מודגשות בצהוב זוהר

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

1	בהינתן קבוצה A  ויחס S  מ-A ל-  P(A), נגדיר  את הפסוקים הבאים: 
	
	    :BA  xA  <x,B>S    
	    :     xA |{BA |<x,B>S}| < 2

	א.  הציגו נוסח מוצרן של הפסוק ) ( ~, בלי להשתמש בקשר השלילה "~".

) ( ~ שקול ל- (~)
 ובמקרה שלנו :   2xA |{BA |<x,B>S}|   BA  xA  <x,B>S     

מתנה
 
	ב.  האם קיימים קבוצה A ויחס S המקיימים את הפסוק .
לא.
לפי , S הוא יחס חד ערכי, כלומר פונקציה חלקית, ועל פי  זוהי פונקציה חלקית מ-A על P(A).
אם קיימת פונקציה חלקית כזו אפשר להרחיב אותה לפונקציה (מלאה) S’ מ-A על-P(A), למשל על ידי קביעת  S’(x)=  לכל xA  שאין לו בן זוג ב-S  (אפשרי כי הקבוצה הריקה היא תמיד אבר ב-P(A)).
לפי משפט קנטור, פונקציה כזאת אינה קיימת.

היו שהבחינו בתמונה הכללית, אבל לא דייקו בשימוש במונחים: יחס, פונקציה ופונקציה חלקית, או סיפקו הסבר אינטואיטיבי, שאינו די מדויק כאשר עוסקים בקבוצות כלליות.  אלה קיבלו בין 1/2 ל-3/4 מהציון המירבי, על פי העניין.

	ג. מהי העוצמה המכסימלית של המנה R/T ,כאשר T יחס שקילות בקבוצת המספרים 
	    הממשיים R, המקיים: <x,y>R2  x+yZ  <x,y>T ?

יחס T המקיים את התנאי הוא, למשל, T={<x,y>|x+yZ  x-yZ}, קל לראות שזהו יחס שקילות, (דומה לתרגיל 9 ג' בגליון 4 של שעורי הבית).
נחשב כעת את |R/T|: לכל מספר ממשי x  קיים בין זוג יחידy  בקטע [0,1/2] כך שx+y  או x-y הוא מספר שלם. לכן, הפונקציה המתאימה לכל מספר מתוך הקטע [0,1/2] את מחלקת השקילות שלו, היא פונקציה הפיכה מהקטע [0,1/2] למרחב המנה R/T. עוצמת המנה היא לפיכך  כעוצמת הקטע.
עוצמת כל חלוקה של R היא לכל היותר , כעוצמת הקבוצה כולה (גם טענה פשוטה לכאורה זו זקוקה להוכחה, אבל נניח לכך), ולכן זו העוצמה המכסימלית האפשרית של R/T ליחס שקילות T כלשהו.

כמעט כל הנבחנים שגו כאן קשות ב"הבנת הנקרא". אין מדובר ביחס    {<x,y>R2|x+yZ}שכלל איננו יחס שקילות, אלא ביחס שקילות T המכיל אותו. יש יחסי שקילות רבים כאלה, למשל T=R2, שמרחב המנה שלו הוא בעוצמה 1. מבין כל העוצמות האפשריות יש למצוא את זו המכסימלית. ככלל לא ניתן כאן ניקוד חלקי, גם כאשר התשובה "דומה מאוד " לכאורה לתשובה הנכונה.
2	תהינה A ו-B קבוצות. נגדיר פונקציה H  כלהלן: H=SAxB.(aA.{bB|<a,b>S})
	
א. מצאו את התחום וטווח מתאים לפונקציה H.

כפי שנאמר בכיתה, SAxB, שבצד הסימן  , הוא ביטוי שקול ל - SP(AxB) ולכן:
התחום הוא – P(AxB)
את הטווח נבחר על פי טיפוס הבטוי שאחרי ה "." שהוא פונקציה בעלת תחום A ה"מחזירה"
קבוצה של אברים מתוך B.
הטווח הוא לכן - AP(B)

טעות נפוצה: "התחום הוא AxB" –הורדת 3/8 מהנקודות . חישוב שגוי אחר של קבוצה אחת מהשתיים המבוקשות – הורדת מחצית הנקודות.

ב. H היא פונקציה הפיכה. הציגו את הפונקציה ההופכית H-1 בסימון  (אין צורך 
    להוכיח ש-H הפיכה ושזוהי אכן ההופכית לה).

H-1=f:AP(B).{<a,b>|bf(a)}

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

	ג.  פונקציה ממשית  : R  R  המקיימת: xRyR  |(x)-(y)|  |x-y| 
	     תקרא מכווצת. חשב את עוצמת קבוצת הפונקציות הממשיות המכווצות.

 על פי משפט ידוע (אינפי / חדו"א - במשפטים מקורסים אחרים, כמו למשל המשפט 1+1=2, אפשר להשתמש בלי הוכחה) פונקציה ממשית f  רציפה ב-R נקבעת על פי ערכי f(x)  ל-xQ (ראציונלים). –
 בשפת "מתמטיקה בדידה": הפונקציה מקבוצת הפונקציות הרציפות לקבוצה  QR, השולחת כל פונקציה רציפה אל הצמצום שלה ל-Q, היא חח"ע.
מכאן שעוצמת קבוצת הפונקציות הרציפות היא לכל היותר .|QR|= חסם זה חל גם על עוצמת קבוצת הפונקציות המכווצות, שהיא תת קבוצה של קבוצת הפ' הרציפות (בהגדרת הרציפות הצב =). 

מן הכיוון השני, קבוצת הפונקציות {xR.ax|a[0,1]} ( או לחילופין {xR.c|cR} ויש עוד הרבה אפשרויות נוספות) היא קבוצה של פונקציות מכווצות וקל להראות שעצמתה  כעוצמת הקטע .[0,1]  לפי "סנדויץ' " העוצמה המבוקשת היא .

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

3	א. כמה פונקציות הפיכות f מהקבוצה A={1,2,3,4,5,6,7}  לעצמה מקיימות:
		xA  f(x)=x

מדובר בכל התמורות שאינן אי סדר טוטאלי (derangements), מספרן: 7! - 7!/e

ברוב המקרים לא היו בעיות. למי שלא נתן תשובה סופית פשוטה ירדו 1/4 מהנקודות. כמובן שלא היה צורך לפתח את הנוסחה לאי סדר טוטאלי או להשתמש בנוסחת ההכלה וההדחה. 
	
	ב. בכמה מחרוזות באורך 5 של ספרות מתוך {1,2,3,4} אין שתי הופעות עוקבות של
	    ספרות זוגיות? הציגו תוצאה מספרית סופית.

נכנה מחרוזת (בכל אורך) המקיימת את התנאי "חוקית". ממחרוזת חוקית, באורך k+2, המסתיימת בספרה אי זוגית, נקבל מחרוזת חוקית כלשהי באורך k+1, על ידי הסרת הספרה האחרונה (1, או 3). אם המחרוזת מסתיימת בספרה זוגית, נקבל מחרוזת חוקית כלשהי באורך k, על ידי הסרת שתי הספרות האחרונות. הספרה הלפני אחרונה במקרה זה היא בהכרח אי-זוגית ולכן יש 4 אפשרויות שונות לשתי הספרות האחרונות (12,14,32,34). מכאן שמספר המחרוזות המבוקש, bk, מקיים את משואת הנסיגה: bk+2=2bk+1+4bk. תנאי ההתחלה הם בברור: b0=1,b1=4.
כיון שאנחנו מחפשים את b5 בלבד, אין צורך לפתור את משוואת הנסיגה, די לחשב האברים בזה אחר זה, לפי משוואת הנסיגה: b3=40 ,b2=2b0+4b1=12, b4=128 ולבסוף b5=416 

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

	ג. נסמן ב-ak את מספר המחרוזות באורך k לכל היותר של ספרות מתוך {1,2,3,4} שאין
	  בהן שתי הופעות עוקבות של ספרות זוגיות. הציגו את הפונקציה היוצרת x.k=0 ∞ akxk
	)  אין צורך לחשב את (ak. 

נחשב תחילה את הפונקציה היוצרת F=x. k=0∞ bkxk עבור bk המוגדר בפתרון הסעיף הקודם. מסכימת משוואת הנסיגה נקבל:  . מכאן נחלץ את F(x) ונקבל . לפי הגדרת  ak, הסדרה k.ak היא סדרת הסכום של k.bk ולפי "אופרטור הסכימה" הפונקציה היוצרת המבוקשת היא

היו שנתנו תשובה שאינה ביטוי סגור. במקרה זה לא ניתן ניקוד. במקרה של שגיאה שנובעת משימוש בנוסחת נסיגה לא נכונה ירדו 1/4 מהנקודות. במידה ולא נעשה שימוש נכון באופרטור הסכימה – הורדת 1/4 מהנקודות. לרבים היו טעויות חישוב, שגם הביאו להורדת 1/4 מהנקודות.

4	א. הוכיחו כי בכל צביעה של קשתות הגרף השלם Kn בפחות מ-n/2 צבעים, קיים מעגל 
	    שכל הקשתות שלו צבועות באותו צבע.

ב-Kn יש 1/2 n(n-1)  קשתות. לכן, כאשר צובעים אותן בפחות מ n/2 צבעים יש קבוצת צבע שיש בה יותר מ n-1 קשתות. לפי "משפט העצים" גרף מכסימלי ללא מעגלים הוא עץ  ויש בו n-1 קשתות. בקבוצת הצבע האמורה יש יותר קשתות ולכן היא מכילה מעגל.

לא מעט נתנו הוכחה שגויה באינדוקציה. אחרים התייחסו לצביעת קודקודים ולא לצביעת קשתות. במקרים אלה לא ניתן ניקוד. למי שלא הצליח להסביר למה יש קבוצת צבע עם יותר מ-n-1 קשתות ירדו מחצית מהנקודות. גם למי שלא ציין והסביר את העובדה שבגרף עם n קודקודים ו-n קשתות בהכרח קיים מעגל – ירדו מחצית מהנקודות.

 ב. יהיה G גרף מישורי בעל n קדקודים, שכל הפאות שלו הן מחומשים.
     הוכיחו: 5n1(mod 3).

נסמן את מספר הקשתות ב-m ואת מספר הפאות ב-f. כפי שהראנו בכיתה, סכום היקפי הפאות הוא כפליים מספר הקשתות, וכיון שכל הפאות מחומשים, 2m=5f. כמו כן מתקיימת נוסחת אוילר m=f+n-2. נכפול את השויון האחרון ב-5, נחסר ממנו את הראשון, נעביר אגפים ונקבל: 5n=3m+10, כלומר 5n-1 מתחלק ב-3. מ.ש.ל.

למי שהשתמש בנוסחאות הנכונות, אך לא הצליח להסביר למה נובעת מכאן התוצאה – ירדו מחצית מהנקודות. טעויות חישוב הביאו להורדת 1/4 מהנקודות.

 ג. הוכיחו או הפריכו: קיים גרף בעל 8 קדקודים ו-17 קשתות שהמעגל הקצר ביותר בו 
     הוא באורך 4.
 
גרף כזה לא קיים. הוכחה:
בגרף G בעל 8 קדקודים ו-17 קשתות סכום הדרגות הוא כפליים מספר הקשתות כלומר 34. לפחות קדקד אחד x הוא לכן בדרגה 5 לפחות. לולאה היא מעגל באורך 1 וזוג קשתות מקבילות הם מעגל באורך 2. אם אין כאלה, G גרף פשוט ו-x מחובר   ב-5 קשתות ל-5 קודקודים שונים. כל קשת בין שניים מקודקודים אלה, משלימה יחד עם x   משולש. בין 5 הקדקדים הללו לבין שלושת הנותרים יש לכל היותר 15 קשתות. כדי להגיע ל-17 נחוצות כל ה-15 ועוד שתי קשתות בין שלושת הקדקדים הנותרים (השלישית תשלים משולש) אבל כל אחת משתי קשתות אלה משלימה חמישה משולשים, אחד עם כל קדקוד משכני x.

רק מי שנתן תשובה שקרובה לתשובה הנכונה (והיו כאלה) קיבל ניקוד. מעטים השתמשו במשפט טורן (בלי להוכיח אותו כמובן) וקיבלו 1/4 מהנקודות. מי שהסיק באופן שגוי שהגרף דו-צדדי או מישורי לא קיבל ניקוד.