בדידה לתיכוניסטים תש"ע - שאלות ותשובות - ארכיון 5

שאלה

לקחתי את הש.ב שלי מבניין 216(תרגיל 4 ו-5) ובתרגיל 5 עשיתי הכל נכון חוץ משאלה 4 ד' ו-ה' חוץ מזה הכל כתוב ומסומן ב-וי(כאילו שזה נכון) וקיבלתי 88, שזה אומר שירדו לי 12 נקודות על 2 סעיפים(היו 6 סעיפים בשאלה הזו, א-ו) בחישוב קל זה יוצא קצת לא הגיוני כי יש 7 שאלות, עכשיו מכיוון שנגמר הקורס, למי אני יכול לפנות(תענו לי את התשובה בהנחה שזה חשוב לי אפילו שזה 5-8 נק'), כמובן שאני מאוד אעדיף תשובה של מתרגל... בכל מקרה תודה מראש!

תשובה

מתן נקודות זה די סובייקטיבי. ייתכן שהיא הורידה לך בנקודות אחרות על אף שהיא סימנה וי. ייתכן שהיא חילקה את הנקודות בין הסעיפים אחרת משהיית מצפה. אני לא חושב שיש על מה לערער, אלא אם מצאת ממש טעות בבדיקה. אני גם לא משוכנע שיש למי. אתה יכול לעבור שוב על התרגיל ולראות אם היא לא העירה לך עוד הערות היכנשהו על התרגיל מעבר לוי-ים שהיא סימנה Adam Chapman 23:48, 3 בספטמבר 2010 (IDT)

קודם כל היא\הוא לא העיר\ה בכלל וזה לכשעצמו רע מאוד(אני לא יודע מה ואיפה הבעיות שלי), אני מודע לזה שיש להם הרבה עומס לבדוק את של כולם, אבל אם הם כבר עושים את זה אז לא לעשות את זה בחאפריות ובזלזול, שייזכרו שיש תלמיד מאחורי קובץ הדפים הללו ומאחורי מספר תעודת הזהות. בכל זאת לא ראיתי שום טעות(חוץ מבסעיפים הללו) והשוויתי עם הפתרונות. אגב לגבי חלוקת הנקודות, זה בסדר שתיהיה סטייה קטנ לגבי סעיף\שאלה, אבל לא סטייה של כמה עשרות נקודות. למשל מחר אני אעשה קורס אחר ייתנו 8 שאלות בתרגיל ואני לא אצליח שאלה מסויימת בגלל הקושי, ובודק\בודקת יוריד\תוריד לי 30 נק' זה הרי לא פורפורציונלי בכלל, וזאת הטענה שאני מנסה להסביר.

קבוצת מנה

לא הבנתי משהו, אז אתן דוגמה ואשאל עליה וזה יעזור לי להבין:

נניח ש-R הוא יחס מודולו 2 על N (כל המספרים $(a,b)\in NxN$ כך ש-2 מחלק את a-b).

אז קבוצת המנה היא $\{1,2\}$ או $\{[1]_R,[2]_R\}$ ? כלומר, קבוצת המנה מוכלת בקבוצה $\{1,2,3\}$ למשל?

תודה מראש!

תשובה

זה יהיה לא נכון לומר ש$\{[1]_R,[2]_R\}$ מוכלת ב$\{1,2,3\}$ משום ש$[1]_R =\{1,3,5,7,\dots\} \neq 1$. מחלקת שקילות של איבר איננה שווה לאיבר עצמו אלא לקבוצה כל האיברים השקולים לו. Adam Chapman 22:19, 3 בספטמבר 2010 (IDT)

אגב, לשאלתך הראשונה, קבוצת המנה היא $\{[1]_R,[2]_R\}$. Adam Chapman 22:30, 3 בספטמבר 2010 (IDT)

תודה!

שאלה

איך מחשבים כמה פונקציות חחעיות וכמה על יש מקבוצה סופית A לק' סופית B? למה? תודה

תשובה

חח"ע: כל איבר במקור חייב ללכת לאיבר אחר בטווח. נניח מספר האיברים בB הוא n ומספר האיברים בA הוא m. לכן לאיבר הראשון במקור יש n אפשרויות לתמונות. האיבר הבא במקור חייב להשלח למשהו שונה ולכן יש לו n-1 אפשרויות. ככה לm איברים וסה"כ נקבל $n(n-1)\cdots (n-(m-1))=\frac{n!}{(n-m)!}$

שימו לב שברור מתנאי השאלה ש$n\geq m$ אחרת לא יכול להיות פונקציה חח"ע

שאלה

צריך לעשות נוסחת נסיגה למספר תת הקבוצות של 1 עד N שמכילות 2 מספרים עוקבים. האם זה נכון להגיד שבגלל שמספר תת הקבוצות שלא מכילות שני מספרים עוקבים (כמו בשאלה שבאלגוריתם שפירסמתם) היא $f(n)=f(n-1)+f(n-2)$ אז מספר תת הקבוצות שכן מכילות היא $f(n)=f(n)-(f(n-1)+f(n-2))$? זה נראה נכון, כי f(n) הוא המספר הכולל, פחות התת קבוצות שלא מכילות, אך גם משהו בזה נראה לא נכון, כי עם מצמצמים את הFN זה יוצא ש $f(n-1) = -f(n-2)$. יש פה טעות? תודה!

תשובה

אני לא כל כך מבין מה אתה מנסה לעשות. אם הגעת למסקנה שמשוואת ההפרשים היא $f(n)=f(n-1)+f(n-2)$ אז מכיוון שהיא הומוגנית אתה צריך לעבור ישר למשוואה האופיינית $p(x)=x^2-x-1=0$, למצוא לה פיתרונות (כולל ריבוב, אע"פ שפה אין כאלו) $x_1,x_2$. לאחר-מכן, לכתוב $f(n)=a x_1^n+b x_2^n$ ואחרי שמציבים את שני ערכי ההתחלה מקבלים את ערכי $a$ ו$b$ ובא לציון גואל. Adam Chapman 18:22, 2 בספטמבר 2010 (IDT)

מה? לא, לא הבנת אותי נכון. אני לא צריך לפתור את נוסחת הנסיגה. אני צריך למצוא נוסחת נסיגה חדשה, נוסחת נסיגה למספר תת הקבוצות ש-כן- מכילות שני מספרים עוקבים. אז אני שואל אם אפשר להשתמש בנוסחה לתת הקבוצות ש-לא- מכילות שני מספרים עוקבים, שאותה אני יודע, ע"י $f(n)=f(n)-[the-solution-to-the-other-question]$ כלומר $f(n)=f(n)-f(n-1)-f(n-2)$. האם אפשר לעשות את זה? אם לא, יש דרך אחרת לפתור את השאלה בעזרת הפתרון לשאלה הקודמת בלי לפתור את השאלה הזאת מחדש אם נוסחת נסיגה בהתעלמות מהפתרון הקודם? תודה!

תשובה2

אתה לא יכול להשתמש בסימון $f(n)$ לייצוג שני דברים שונים. אתה יכול לסמן כ$h(n)$ את מספר תת-הקבוצות של 1 עד n (אתה יכול להסיק מיד ש$h(n)=2^n$ ולסמן כ$g(n)$ את מספר תת הקבוצות שמכילות שני מספרים עוקבים, ולהסיק ש$g(n)=h(n)-f(n)$. אם אתה מעוניין במשוואת הפרשים, אז אתה יכול להציב במשוואת ההפרשים של $f(n)$ ולקבל $h(n)-g(n)=h(n-1)-g(n-1)+h(n-2)-g(n-2)$, לבודד את $g(n)$ ולקבל כך משוואת הפרשים חדשה. אני מקווה שזה עונה יותר טוב על השאלה Adam Chapman 22:15, 3 בספטמבר 2010 (IDT)

פתרון למבחן 2009 מועד ב' שאלה 7 א'

הפתרון של נוסחת הנסיגה $f(n)=f(n-1)+f(n-2)$ זה פתרון נכון? תודה!

תשובה

איפה אתה רואה בשאלה רקורסיה או נוסחאת נסיגה?

מישהו אמר שאסור לפתור את השאלה בעזרת נוסחת נסיגה? [התשובה הסופית שלי הייתה הפתרון לנוסחת הנסיגה ולא הנוסחה עצמה!]

תשובה2

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

הפיתרון הנכון באלה הזו הוא לשים לב לרמז: תחילה שמים את הכדורים הלבנים. אח"כ צריך לבחור m רווחים מתוך n+1 הרווחים שבין כל שני כדורים לבנים (כולל זה שלפני הכדור הראשון וזה שאחרי האחרון) ולשים בכל אחד מהרווחים הנבחרים כדור שחור אחד. התשובה היא אם כן m מתוך n+1.

Adam Chapman 14:37, 3 בספטמבר 2010 (IDT)

תודה רבה, אבל למה נוסחת הנסיגה לא נכונה? הרי אם שמים כדור לבן בהתחלה, אחריו יש f(n-1) אפשרויות חוקיות, ואם שמים כדור שחור, אחריו חייב לבוא כדור לבן ולכן יש אחריו f(n-2) אפשרויות חוקיות, סה"כ $f(n)=f(n-1)+f(n-2)$ לא?

למדנו איך עושים רקורסיה שתלוייה במשתנה אחד (n), אך בתרגיל זה יש לך 2 משתנים, n וm ולכן נוסחה של רקורסיה פשוטה שתלוייה רק בn אינה מתאימה פה (אני תלמיד לא מתרגל)

תשובה3

נוסחת הנסיגה איננה נכונה משום שאם שמים כדור שחור אז אחריו מגיע כדור לבן, אך מה שנשאר זה לא $f(n-2)$ אפשרויות חוקיות משום שאפשרות חוקית (במקרה שאתה מנסה להציג פה) כוללת m כדורים שחורים בעוד שהשתמשת כבר בכדור שחור אחד ונשארו לך רק m-1 להמשך. מי שענה לך צודק, שהיית יכול "לשפץ" את נוסחת הנסיגה שלך שתהייה תלויה בשני משתנים ולא אחד ואז אוליי היא הייתה יוצאת נכונה (אתה מאפשר חופש רק במספר הלבנים ולא בשחורים בנסיגה שלך), אולם אז היית מקבל נוסחה שמאוד קשה לפתח ממנה נוסחה מפורשת. עדיף שתשתמש בפיתרון שכתבתי לך למעלה;) Adam Chapman 22:26, 3 בספטמבר 2010 (IDT)

הבנתי את זה לבד, אבל ממש תודה רבה על כל העזרה!

פתרונות למבחנים

האם אפשר להעלות פתרונות לשאלות 2 ו3 במבחן של 2009 מועד ב'?

ואולי גם את הפתרונות של שאר המבחנים שמצויים באתר?

תודה מראש

שאלה 4 במבחן תשס"ח מועד ב

אפשר אולי רמז לשאלה?
תודה

פיתרון (סורי. רציתי לתת רמז אך אז יצאו לי רק שטויות)

קח חלוקה של n תלמידים לקבוצות. קח את הקבוצה המכילה את התלמיד הn-י. אם היא בגודל שלוש ומעלה אז כשומרידים את n נשארים עם חלוקה חוקית של n-1 תלמידים. אם היא בגודל 2 אז היא מכילה עוד איבר אחד k בין 1 לn-1 ושאר החלוקה היא חלוקה חוקית של n-2 התלמידים בין 1 לn-1 לא כולל k. לכן $f(n)=f(n-1)+(n-1) f(n-2)$ Adam Chapman 14:59, 3 בספטמבר 2010 (IDT)

תודה,נראה לי הבנתי את הרעיון,אבל אמרת אם היא בגודל 3, לא התכוונת לגודל 1 ואז פשוט מורידים את הקבוצה שכוללת את n בלבד?הרי חלוקה עם קבוצה בת 3 איברים איננה חלוקה חוקית.

אם הבנתי את השאלה נכון (וייתכן שלא) אז חלוקה חוקית היא חלוקת התלמידים לקבוצות בנות 2 ומעלה תלמידים אז חלוקה שכוללת קבוצה בת תלמיד אחד היא איננה חוקית. ייתכן ואני זוכר לא נכון את השאלה. Adam Chapman 22:33, 3 בספטמבר 2010 (IDT)

פיתרון מתוקן

אני מצטער. זכרתי את השאלה לא נכון. מדובר בחלוקה באמת לקבוצות שגודלן לכל היותר שני תלמידים בכל אחת. במקרה כזה באמת בוחרים את קבוצתו של התלמיד הn-י. אם היא בגודל אחד אז בלעדיה נשארים עם חלוקה לקבוצות חוקית של קבוצה בת n-1 תלמידים, ואם היא בגודל 2 אז יש לו בן זוג לקבוצה, נסמנו k. מה שנשאר בלי הקבוצה הזו זו חלוקה חוקית של המספרים 1 עד n-1 להוציא k (קבוצה בת n-2 איברים). יכולים להיות n-1 בני-זוג פוטנציאליים שונים לn בקבוצה בת שני איברים שעבור כל אחד יש $f(n-2)$ חלוקות אפשריות שונות, ולכן מקבלים בסופו של דבר את הנוסחה $f(n)=f(n-1)+(n-1) f(n-2)$ שבאופן משונה זהה למה שיצא לי קודם אע"פ שזכרתי לא נכון את השאלה. מזל שהיינו צריכים לתת בשאלה הזו רק את התשובה הסופית. Adam Chapman 23:24, 3 בספטמבר 2010 (IDT)

תודה רבה!

עזרה/האם הפתרון שלי נכון במבחן 2009 ב' שאלה 6

אני יכול להגיד ככה? יהי a,b שייך לA, יש 2 אפשרויות, aRb או aR'b, יהי c שייך לA, אם bRc אז aRc, אם bR'c אז aR'c וכך הלאה, ולכן אם x "נמצא ביחס" R כלומר קיים y כך של yRc אזי aRc ולכן c שייך ל [a]R ולכן $A/R = {[a]_R}$? תודה!

למה הכוונה ב"אם bRc אז aRc, אם bR'c אז aR'c וכך הלאה"? זה לא היקש לוגי תקין ממה שטענת קודם " aRb או aR'b". אם אתה בוחר להמשיך את העובדה " aRb או aR'b" הלאה אז אתה צריך לטפל במקרה שaRb ובמקרה שaR'b בנפרד. מה שיפה הוא שאם קיימים שני איברים שונים כך שaRb אז גם bRa כי R יחס שקילות. לכן אם קיימים שני איברים שונים כך ש aR'b אז גם bR'a. אולם,מכיוון שהיחס המשלים הוא טרנזיטיבי, מקבלים שbR'b וזו סתירה לbRb (זכור שR יחס שקילות ולכן רפלקסיבי). לכן לא קיימים שני איברים שונים שעבורם aR'b ולכן היחס המשלים הוא ריק, כלומר R הוא היחס המלא על A ולכן קיימת רק מחלקת שקילות אחת והיא כל A.Adam Chapman 15:21, 3 בספטמבר 2010 (IDT)

גם אם הפתרון שלך נכון (אפילו שלא הבנתי אותו), גם הפתרון שלי יכול להיות נכון, זה לא בסדר סתם לסתור את מה שאני רשמתי. הרי כמו שרשמתי, אם bRC, מכיוון שaRb, אז aRc (טרנזטיביות...). אם bR'C ומכיוון שגם aR'b אז aR'c (שוב טרנזטיביות...). אתה יכול גם להסביר את הפתרון שלך? למה אם aR'b אז bR'a ? לא נתון שR' סימטרי! למה bR'b זו סתירה? למה אם R הוא היחס המלא אז A/R=1? תודה

תשובה

אני מתנצל אם פגעתי בך. הפיתרון שלך לא נכון משום שנראה (לפחות ממה שאני מבין) שאתה משתמש בכך שהתנאים aRb וaR'b מתקיימים בו זמנית, שזה פשוט לא נכון, זו הנחת סתירה. אתה לא יכול לומר ש"אם bRC, מכיוון שaRb, אז aRc" משום שaRb הוא לא משפט בעל ערך אמת בהכרח, רק "aRb או aR'b" הוא משפט בעל ערך אמת.

אנסה לתת את הפיתרון באופן מסודר:

1) נניח בשלילה כי קיימות לפחות שתי מחלקות שקילות.

2) עקב-כך קיימים שני איברים שונים, a וb, ממחלקות שקילות שונות.

3) מכיוון שהם ממחלקות שקילות שונות אז לaRb יש ערך שקר.

4) מכיוון שלaRb ערך שקר אז לaR'b יש ערך אמת.

5) מאידך, משום שR יחס שקילות אז R סימטרי, ולכן לו bRa היה אמת אז גם aRb היה אמת. אולם aRb הוא שקר ולכן bRa הוא שקר.

6) מכיוון שbRa הוא שקר אז bR'a הוא אמת.

7) כעת, מתקיימים bR'a וגם aR'b בעוד שהיחס המשלים הוא טרנזיטיבי, ולכן aR'a הוא אמת.

8) אולם לaRa יש ערך אמת משום שR יחס שקילות ולכן רפלקסיבי.

9) מכיוון שaRa הוא אמת אז aR'a הוא שקר, בסתירה לשלב 7.

10) מכיוון שקיבלנו סתירה מסתמן שההנחה שלנו לא יכולה להיות נכונה ולכן מספר מחלקות השקילות איננו יכול להיות 2 ומעלה ולכן הוא 1.

מקווה שזה עוזר. אבל שמע, בכנות, אם אני (או כל איש סגל אחר) אומר לך שהפיתרון שלך איננו נכון זה לא משום שאני (או כל איש סגל אחר) רע. אם אני אומר לך שהפיתרון שלך איננו נכון אז הוא כנראה לא נכון, אלא אם אני הייתי באותו רגע תחת השפעת עייפות מצטברת או אלכוהול. אני ממליץ לך בחום לקבל הערות ולא להתגונן Adam Chapman 22:54, 3 בספטמבר 2010 (IDT)

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

פרטים לגבי המבחן שנשלחו במייל

הבחינה בקורס "מתמטיקה בדידה" תתקיים ביום ראשון 5/9/2010, לכל הקבוצות.

חדרי הבחינה:

8819508 של ד"ר אפי כהן ב- 605/101, 605/102

8819511 של ד"ר שי סרוסי ב- 605/103, 605/104

בהצלחה.

אם אני בקבוצה של אפי, איך אני יודע אם אני ב101 או 102? או שזה לא משנה?

לפי שמות משפחה, יתפרסם בהמשך דרך מערכת מידע אישי...

באיזו שעה המבחן?

16:00

קצת סדר במושגים (חלוקה מחלקת שקילות וכו')

אז ככה: נניח ש $A={1,2,3,4,5,6}$. חלוקה של A זה נגיד A1=1,2, A2=3,4,5, A3=6. קוראים לזה חלוקה, נכון? ואז מחלקת שקילות זה אחד מהקבוצות Ai, נכון? כלומר A1, A2, A3 הן כולן מחלקות שקילות? ואז איך קוראים לקבוצה $[a]R$? ואיך קוראים לקבוצה $A/R$? וגם מה הקבוצה האחרונה אומרת? תודה!

תשובה

$A/R$ היא קבוצת מחלקות השקילות. כך היא נקראת ופשוטה כמשמעה. במקר שלך, משום שחילקת כבר למחלקות שקילות אז אתה מקבל אוטומטית $A/R=\{A_1,A_2,A_3\}$. הקבוצה $[a]_R$ הינה מחלקת השקילות של $a$. במקרה שלך, למשל, אם $a=5$ אז $[a]_R=A_2$. אני מציע שתקראו שוב את החומר ביחסי שקילות. Adam Chapman 23:06, 3 בספטמבר 2010 (IDT)

שאלה שאני לא בטוח שאתם יכולים לענות עליה, אבל שווה את הנסיון...

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

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

תודה רבה, אתה יכול להביא קישור או להסביר איך להגיע לאתר?

תכתוב בגוגל "מערכת מידע אישי בר אילן", תמצא את האתר המתאים, תלחץ על מידע לסטודנט, מידע כללי, מועד בחינה ומיקומה, קורס 88-195 כאשר שתי הספרות האחרונות הן 08 עבור אפי, 11 עבור שי.

באתר כתוב שהבחינה בשלוש וחצי, זה השתנה ל4? תודה!

שאלה לגבי המבחן ביום ראשון

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

יש מרצה או מתרגל שיכול לענות, זה ממש יכול לעזור, תודה

מועד א' 2009, שאלה 3.ב.

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

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

אלגוריתם נוסחאות נסיגה

למה בסוף עמוד 2 אומרים ש-$n \not= 0$?

תודה מראש.

תשובה

אין חשיבות מיוחדת לזה. אתה יכול למחוק את זה בטיפקס. מה שחשוב זה שהביוטי $n a+b=0$ נכון לכל $n \in \mathbb{N}$. אם תיקח כל שני מספרים שונים ותציב אז תקבל שתי משוואות שמהן תוכל להסיק בקלות ש$a=0$ וגם ש$b=0$. זה העיקר.

אז בעצם זהו סתם קיצור דרך. תודה! והכוונה היא ש-$n \in \mathbb{N}$ כולל 0?

זה תלוי בתנאי הרקורסיה. אם הוא מנוסח כ$f(n)=a_1 f(n-1)+\dots$ אז מניחים ש$n>k$ כש$k$ זה מספר הערכים הראשונים הנתונים. אם תנאי הרקורסיה מנוסח $f(n+k)=\dots$ אז מניחים פשוט ש$n$ שלם אי-שלילי. העניין הוא פשוט שבנקודה הספציפית ששאלת עליה אין חשיבות לעניין האי-שוויון של $n$ לאפס.

ציוני התרגילים

שלום,אפשר לדעת מתי יועלו הציונים של התרגילים?

תשובה

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

מבחן

האם אתם יכולים לכוון על נושא מרכזי שיהיה במבחן, כמו שבאלגברה לינארית אמרו שתהיינה הרבה שאלות על העתקות לינאריות וכל הכלול בזה?

וכמה זמן המבחן?

תודה.

תשובה

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

הלמה של צורן

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

אפשר להעלות דף הסבר או דוגמאות לשימושים שלה?

תודה מראש.

תשובה

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

פתרון תרגיל 5

בפתרון תרגיל 5 לא מופיע פתרון שאלה 7, ובמקומו יש פתרון לשאלות 7,8,9 אחרות (שלא מופיעות בתרגיל עצמו).

תשובה

צודק. פאדיחות... בכל-אופן הפיתרון של שאלה 7 הוא כדלקמן (לפחות אלגוריתמית):

1) יש להגדיר קבוצה $T=\{A \subseteq E : \forall_{a,b \in A} a \cap b=\emptyset\}$.

2) להוכיח בעזרת הלמה של צורן שיש ב$T$ איבר מקסימלי.

3) להראות כי האיבר המקסימלי מקיים את התנאי השני בשאלה (לדעתי זה נוח להשתמש בהנחה בשלילה)

עזרה במבחן השני (2009 מועד ב') תרגיל 3 (אין לו פתרון)

התחלתי לפתור בדרך הבאה: מספר הדרכים לשים 20 כדורים ב5 תאים הוא כמו מספר הפתרונות האי שליליים לx1+x2+x3+x4+x5=20 ולכן מספר האפשרויות הכולל הוא 5-1 מתוך 20+5-1 כלומר 4 מתוך 24 (אני לא יודע איך לעשות את הסימן של ה4 מתחת ל24). כעת Ai= התא הi הוא עם 3 כדורים. מספר האפשרויות בשביל Ai הוא 3 מתוך 20 (נכון?). חיתוך של 2 Aים הוא (נראה לי), 6 מתוך 20 כפול 3 מתוך 6 (כי בוחרים 6 כדורים מתוך ה20, בוחרים 3 מתוכם, שמים אותם באחד התאים ואת השאר בתא השני). וככה הלאה עד חיתוך של 5 Aים. הבעיה היא, שכבר בחיתוך של 2 Aים, מספר האפשרויות יוצא הרבה הרבה יותר ממספר האפשרויות הכולל! (700 אלף לעומת 10000 בערך), שזה לא הגיוני! אפשר עזרה? תודה! 

תשובה

אתה מחשב לא נכון את החיתוך של Ai עם Aj. הגודל של החיתוך הוא 2 מתוך 16 (שמים 3 בi ו3 בj ואז מחלקים 14 ל3 תאים). חיתוך של כל שלוש קבוצות כנ"ל הוא מגודל 1 מתוך 12 וחיתוך של ארבע הוא מגודל 0 מתוך 8. אין חיתוך של חמש. בעזרת הכלה-הדחה מגיעים לפיתרון מדוייק. אני ממליץ שתנסה לפתור שוב את השאלה.

ממש לא הבנתי למה חיתוך של 2 קבוצות הוא 2 מתוך 16, אפשר הסבר? תודה!

מה המשמעות של חיתוך של $A_i$ עם $A_j$? החיתוך הוא כל הפתרונות האי-שליליים של $x_1+\dots+x_5=20$ כאשר $x_i=x_j=3$. לכל פיתרון כזה מתאים באופן חח"ע ועל פיתרון למערכת $y_1+y_2+y_3=14$ (מפחיתים את $x_i+x_j=6$ משני האגפים בהתאמה). לכן הגודל של $A_i \bigcap A_j$ הוא 2 מתוך 16. Adam Chapman 18:33, 2 בספטמבר 2010 (IDT)

לא חשבתי על זה ככה, תודה!

תרגולים 4-5

מתי יעלו הציונים של תרגולים אלו? תודה מראש.

מבחן מועד ב' 2009

אפשר בבקשה את הפתרונות הסופיים של תרגילים 2 ו-3 כי הם לא נמצאים בדף הפתרונות... תודה ;)

רקורסיה

אתם יכולים להעלות את האלגוריתם? זה ממש יעזור, ואם אפשר תוסיפו קצת הסברים ודוגמאות, הנושא קצת לא מובן, תודה!

מצטרף לבקשה!

עכשיו ישAdam Chapman 16:07, 1 בספטמבר 2010 (IDT)

תודה אדם

מבחן 1 שאלה 4 ב'

הסתכלתי בפתרון, מה זה לפי ק.ש.ב? תודה!

משפט קנטור שרדר ברנשטיין

נוסחאות נסיגה

כשיש נוסחת נסיגה (למשל כמו בתרגילים לדוגמה של נוסחאות נסיגה, תרגיל I, שאלה 1 א', אז f(0) שווה 0 או 1? צריך בכלל לשים את f(0) או שמתחילים מf(1)? תודה!

תשובה

המילה הריקה מקיימת את התנאי באופן ריק, משום שאינה מכילה אפסים כלל, ולכן $f(0)=1$. בקשר לאיזה אינדקס פותח את הסידרה, זה תלוי באסכולה. אצלנו הגדרנו לכם שזה מתחיל מ0 ולא מ1. (זה מתקשר בעקיפין לדיון האם 0 הוא טבעי). Adam Chapman 16:09, 1 בספטמבר 2010 (IDT)

תודה!

שיעור חזרה

מתי ואיפה יהיה שיעור החזרה מחרתיים? תודה רבה.

הפרטים כעת מופיעים. Adam Chapman 16:10, 1 בספטמבר 2010 (IDT)

אני לא מוצא איפה כתוב מתי ואיפה השיעור חזרה, אתם יכולים לפרט איפה ומתי הוא יתקיים?

פרטים מופיעים בעמוד הראשי.

פתרונות

תעלו בבקשה את הפתרונות של תרגילים 4 ו5.

n קטן מדי

חלק מהשאלות דורשות שמספר הטלות הקוביה/העוצמה של קבוצה/... יהיה גדול ממספר כלשהו כדי שמספר האפשרויות המבוקש יהיה גדול מ-0. למשל, ב-3ב' n צריך להיות לפחות 3.

אם התשובה הסופית מתאפסת במקרה ש-n קטן מדי, צריך לציין בסיפור של ההוכחה (אם השתמשנו בכזה) שאנחנו מניחים ש-n גדול מספיק, ולהסביר למה התשובה נכונה גם אם לא?

תשובה

במקרה של 3ב' זה מספיק טריוויאלי ואין צורך להסביר. אפשר לציין שהתשובה נכונה עבור n גדול או שווה ל- 3.

במקרים שהמגבלות על n לא נובעים ישירות מניסוח השאלה, צריך להסביר.

שאלה בנוגע להגשת התרגיל

האם כמו בלינארית גם כאן הציון של התרגילים יקבע לפי ה4 הכי טובים ? בדף הקורס של לינארית כתוב שבכלל לא חייבים להגיש את תרגיל 5. האם זה נכון גם לגבי בדידה?

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

תשובה

יש חובת הגשה של ארבעה תרגילים מתוך חמישה. אם הוגשו 5 תרגילים, ניקח את ארבעת הציונים הטובים. (גרישה אושרוביץ')

שאלה 7

האם e היא קבוצה סדורה חלקית?

תשובה

רק אם תגדיר עליה את יחס סדר חלקי.

תרגיל נוסף מהתירגול

בתירגול פתרנו תרגיל כזה: בקורס יש 2n סטודנטים. רוצים לחלק אותם לזוגות. כמה זוגות יתכנו?

פתרון: נסדר אותם בשורה - סה"כ $(2n)!$ תמורות. צריך לבטל שני מקרים:

1. אין סדר בין הזוגות - $n!$ אפשרויות.
2. אין סדר בתוך הזוגות - $(2!)^n$ אפשרויות. למה??

תשובה סופית: $(2n)!\over n!(2!)^n$

ואני לא הבנתי למה צריך לחלק באפשרויות שצריך לבטל, ולא פשוט להפחית אותן? כלומר שהתשובה תהיה זו: $(2n)!-n!-(2!)^n$. הרי אם יש מספר אפשרויות, וצריך לבטל חלק, אז אינטואיטיבית אמורים להפחית!

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

=================================================================

תשובה

מפחיתים ממספר האפשרויות את מספר האפשרויות. במקרה הזה, $(2!)^n$ וגם $n!$ הם לא מספר האפשרויות אלה מספר הפעמים שספרנו אותן אפשרויות. כלומר, ב- $(2n)!$ הסידורים ספרנו $n!$ פעמים את אותן זוגות בדיוק. לדוגמא: נניח כי יש 4 אנשים {a,b,c,d}, אזי הסידורים abcd ו- cdab זהים, כי בחרנו אותן זוגות. יתרה מכך, גם הסידורים bacd, badc, cdba, dcab זהים. זה אומר שצריך לבטל את הסדר של אנשים בתוך הזוגות שנבחרו. מקווה שעזרתי. באופן כללי, אני מציע להשתמש יותר בשעות הקבלה של המתרגלים.

אם כך, מחלקים מספר אפשרויות במספר הפעמים שספרנו אותן. מפחיתים מספר אפשרויות ממספר אפשרויות אחר. תודה רבה, הבנתי!

מה עם השאלה הראשונה? (לגבי ביטול מספר 2, כשאין סדר בתוך הזוגות)

... גם הסידורים bacd, badc, cdba, dcab זהים. זה אומר שצריך לבטל את הסדר של אנשים בתוך הזוגות שנבחרו...

לא חשוב איך מסודרים האנשים בתוך הזוג שנבחר. לא חשוב אם לסדר אותם ab או ba - זה יישאר אותו זוג, אך ב- $(2n)!$ ספרנו את כל האפשרויות.

==================================================================

הייתה פה תשובה לשאלה שלי ומשום מה היא נמחקה! אז לגביה, לא הבנתי למה בכלל משתמשים בנוסחה של $n \choose k$.

כי את בוחרת אנשים זוגות מתוך 2 אנשים, (יש רק אפשרות אחת כזו). בפעם הראשונה התבלבלתי בסימון, זה היה צריך להיות $P(n,k)$ ולא $C(n,k)$. מחקתי כי הניסוח לא היה מפורט ומדויק.

תודה על התשובה המהירה. לא הבנתי מה זה "בוחרת אנשים זוגות", למה מתוך 2 אנשים, ומה ההבדל בין $P(n,k)$ ל- $C(n,k)$.

התכוונתי "זוגות אנשים" ולא "אנשים זוגות", מתוך 2 כי בכל זוג יש 2 אנשים, וההבדל בין $P(n,k)$ ל- $C(n,k)$ הוא ש-$P(n,k)=\frac{n!}{(n-k)!},\ C(n,k)={n\choose k}=\frac{n!}{k!(n-k)!}$.

הבנתי את ההבדל בין C ל-P. אבל מהן התשובות לשאלות שלי? (כמו שאמרת, הניסוח קודם לא היה ממש מובן..). ושוב תודה רבה!

צריך לפרט?

צריך לפרט למה:

1. $\forall k,n\in\mathbb N\cup\{0\}\ \and\ 0\le k\le n:\ {n\choose k}\in\mathbb N\setminus\{0\}$?
2. מספר המספרים מ-1 עד n שמחלקים את $2^k$ ללא שארית אבל לא את $2^{k+1}$ הוא $\left\lfloor\frac n{2^k}\right\rfloor-\left\lfloor\frac n{2^{k+1}}\right\rfloor$?
3. מספר המספרים מ-r עד n שמחלקים את $2^k$ ללא שארית הוא $\left\lfloor\frac n{2^k}\right\rfloor-\left\lfloor\frac{r-1}{2^k}\right\rfloor$?
4. החזקה השלמה הגדולה ביותר של 2 שנמצאת בין 1 ל-n (למשל, עבור n=10 חזקה זו היא $2^3=8$, עבור n=16 - $2^4=16$ וכו') היא $2^{\lfloor\log_2(n)\rfloor}$?

או שזה מספיק טריוויאלי? תודה

תשובה

1, 4 - לא. 2, 3 - כן, בקצרה.

תרגיל מהתירגול

בתירגול פתרנו תרגיל כזה: מהו מספר האפשרויות לסידור 11 אנשים במעגל? תשובה: n!/n (כלומר !(n-1)). לא הבנתי למה, ובכיתה לא כתבנו הסבר, רק ציור שמראה את ההבדל בין סידורם בקו לסידורם במעגל (את ההבדל הזה הבנתי).

אפשר הסבר איך פותרים את התרגיל? תודה מראש!

מספר הדרכים לסדר n אנשים אחד אחרי השני (בקו) הוא n! - כי יש n אפשרויות לבחירת האדם הראשון, n-1 לשני וכן הלאה. כעת, במעגל אין משמעות לראשון ולאחרון, אלא רק מי נמצא אחרי מי. לכן, בהנתן סידור מסוים של האנשים במעגל, יש n אפשרויות לבחור מי יהיה הראשון. כלומר כל אפשרות למעגל מופיעה n פעמים בסידור קו ישר (כל פעם בוחרים מישהו אחר להיות הראשון).

לכן סה"כ מספר המעגלים הוא מספר הקוים חלקי n שווה ל n!/n

תודה רבה!

שאלה כללית

אם אני מטיל קוביה n פעמים. האם נכון לומר שמס' האפשרויות להופעת 2 מס' שונים לפחות פעם אחת הוא 6 בחזקת n פחות 4 בחזקת n?

שאלה 6

אם אני בונה כלל נסיגה אז מה צריך להיות המשתנה? K או N?

מהי הנוסחא למספר פתרונות המשוואה

אשמח אם מישהו יוכל לתת את הנוסחא למציאת מספר פתרוות של משוואה- כמו שלמדנו בכיתה ודוגמא קצרה שתסביר כי לא הבנתי איך הנוסחא עובדת. תודה :)

תשובה

הנוסחה היא:${n+k-1 \choose n}$ כאשר n הוא המס' הקבוע(בצד ימין בד"כ) ו-k הוא מס' המשתנים. למשל: מצא את מס' הפתרונות האי שליליים של המשוואה a+b+c=10 כלומר n=10,k=3 אז מספר הפתרונות יהיה ${12 \choose 10}$. כאשר מבקשים רק חיוביים(בלי ה-0) אז הנוסחה היא: ${n-1\choose k-1}$

שאלה 4.ב.

אפשר רמז בנוגע למתחלק ב7?

שאלה 3.ב.

הטלנו n פעמים אז איך יצאו 3 ערכים?

תשובה

דוגמא:ניקח n=10. הסדרות להלן מכילות בדיוק3 איברים שונים (כל אחד מהן) {1,2,2,6,1,2,6,6,2,1} או {3,4,3,3,5,5,5,5,3,4}

רגע... זה סדרות או קבוצות? (לפי השאלה זה אמור להיות סדרות, לא? ופה כתבת קבוצות..)

סדרות. גם את סדרות אפשר לכתוב בסוגריים מסולסלות.

שאלה 2

זה בסדר להוכיח באינדוקציה?

תשובה

מותר. אבל עדיף אם תתנסה בדרך אלגוברית ו/או קומבינאטורית.

שאלה כללית

אם שואלים אותי מה מספר האפשרויות למשהו ואני מחלק למקרים. בסוף אני צריך לכפול את כל האפשרויות מכל המקרים כדי לקבל את מס' האפשרויות למשה (הכללי)?

תשובה

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

שאלה 4ד'

אפשר עזרה לגבי התשובה? האם התשובה צריכה להיות A איחוד B איחוד C (כאשר כל אחת מהקבוצות הן מספר שמתחלק ב3 4 ו5 בהתאמה בין 1 ל1000) או A איחוד B איחוד C פחות (A חיתוך B) פחות (A חיתוך C) פחות (A חיתוך B חיתוך C) פחות (A חיתוך B חיתוך C)? במילים אחרות, האם יכול לצאת מצב שיוצא 2 קבוצות מתוך האיחוד ביחד ואז זה לא טוב ואני צריך להוריד את האפשרויות האלה, או שבאיחוד כבר הורדנו אותן? תודה

מס' שאלות

2.) איך יתכן שזה ייתקיים עבור n=0? 3.)מה הכוונה ב"מהן מספר האפשרויות"? אפשרויות למה? 4.) מה זה ריבועים שלמים?

2- כי 0 עצרת זה 1, תחשב וזה יוצא נכון. 3- כמה אפשרויות לתוצאות יכולות לצאת. כמה תוצאות שונות יכולות לקרות. 4- ריבוע של מספר שלם, כלומר 1,4,9 וכו'

שאלה 3

לא כתבתם למה התכוונתם, האם הסדר משנה או לא? כלומר, האם כשמטילים את הקובייה פעמיים למשל, כשיוצא 5 ראשון ואחר כך 6, וכשיוצא 6 ראשון ואחר כך 5, האם התוצאות האלה שונות או לא? תודה.

תשובה

ראה למטה.

שאלה 3, למה אתם מתכוונים?

מה זה אומר ב-ב', "שהתקבלו עבור בדיוק 3 ערכים שונים"? אני לא מבין את המשפט (מבחינה תחבירית) למה התכוונתם? וחוץ מזה, אפשר רמז לגבי הפתרון? תודה רבה.

תשובה

מהו מספר אפשרויות לקבל ב-n הטלות בדיוק 3 ערכים שונים. למשל, רק מספרים {1,2,3} או {2,4,6}.

המשך שאלה האם יש חשיבות לסדר? למשל עבור 4 הטלות והמספרים {1,2,3}, האם יש הבדל בין (1,2,3,1) ל- (1,1,2,3)? הניסוח של השאלה באמת ממש לא מובן...

תשובה

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