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

[math]\displaystyle{ {n \choose k} = {n!\over k!(n-k)!} }[/math]

הוראות

כאן המקום לשאול שאלות. כל שעליכם לעשות הוא ללחוץ על [עריכה] (משמאל לכותרת "שאלות"), להוסיף בתחילת הדף את השורה הבאה:

== כותרת לשאלה ==

לכתוב מתחתיה את שאלתכם, וללחוץ על שמירה למטה מימין

הודעה חשובה !!! - יש להגיש את התרגילים הנוספים (13 , ו 14 כרשות למי שמגיש ) עד ,וכולל , 16.9.2010 ! למשל לתא הבודקת הילה הלוי בכר , או לתומר ביום רביעי או לניר ביום חמישי - בתרגולי החזרה . אנא הודיעו למי שאתם יודעים שלא יגיע לתרגולים אלו . תודה:)

ארכיון

ארכיון 1 - תרגיל 1

ארכיון 2 - תרגיל 2

ארכיון 3 - תרגיל 3

ארכיון 4 - תרגיל 4

שאלות

עזרה (מבחן 2009 מועד ב' שאלה 7 ב'2 .)

הוכחתי את 1, אבל איך מוכיחים את 2.? אני ממש לא מבין למה S שווה לתוצאה (המוזרה) הזאת? תודה!

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

הפתרון של נוסחת הנסיגה [math]\displaystyle{ f(n)=f(n-1)+f(n-2) }[/math] זה פתרון נכון? תודה!

תשובה

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

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

תשובה2

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

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

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

תודה רבה, אבל למה נוסחת הנסיגה לא נכונה? הרי אם שמים כדור לבן בהתחלה, אחריו יש f(n-1) אפשרויות חוקיות, ואם שמים כדור שחור, אחריו חייב לבוא כדור לבן ולכן יש אחריו f(n-2) אפשרויות חוקיות, סה"כ [math]\displaystyle{ f(n)=f(n-1)+f(n-2) }[/math] לא?

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

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

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

תודה מראש

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

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

עזרה/האם הפתרון שלי נכון במבחן 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 ולכן [math]\displaystyle{ A/R = {[a]_R} }[/math]? תודה!

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

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

חדרי הבחינה:

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

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

בהצלחה.

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

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

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

16:00

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

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

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

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

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

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

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

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

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

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

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

שאלה

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

תשובה

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

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

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

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

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

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

למה בסוף עמוד 2 אומרים ש-[math]\displaystyle{ n \not= 0 }[/math]?

תודה מראש.

תשובה

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

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

זה תלוי בתנאי הרקורסיה. אם הוא מנוסח כ[math]\displaystyle{ f(n)=a_1 f(n-1)+\dots }[/math] אז מניחים ש[math]\displaystyle{ n\gt k }[/math] כש[math]\displaystyle{ k }[/math] זה מספר הערכים הראשונים הנתונים. אם תנאי הרקורסיה מנוסח [math]\displaystyle{ f(n+k)=\dots }[/math] אז מניחים פשוט ש[math]\displaystyle{ n }[/math] שלם אי-שלילי. העניין הוא פשוט שבנקודה הספציפית ששאלת עליה אין חשיבות לעניין האי-שוויון של [math]\displaystyle{ n }[/math] לאפס.

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

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

תשובה

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

מבחן

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

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

תודה.

תשובה

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

הלמה של צורן

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

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

תודה מראש.

תשובה

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

פתרון תרגיל 5

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

תשובה

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

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

2) להוכיח בעזרת הלמה של צורן שיש ב[math]\displaystyle{ T }[/math] איבר מקסימלי.

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, אפשר הסבר? תודה!

מה המשמעות של חיתוך של [math]\displaystyle{ A_i }[/math] עם [math]\displaystyle{ A_j }[/math]? החיתוך הוא כל הפתרונות האי-שליליים של [math]\displaystyle{ x_1+\dots+x_5=20 }[/math] כאשר [math]\displaystyle{ x_i=x_j=3 }[/math]. לכל פיתרון כזה מתאים באופן חח"ע ועל פיתרון למערכת [math]\displaystyle{ y_1+y_2+y_3=14 }[/math] (מפחיתים את [math]\displaystyle{ x_i+x_j=6 }[/math] משני האגפים בהתאמה). לכן הגודל של [math]\displaystyle{ A_i \bigcap A_j }[/math] הוא 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)? תודה!

תשובה

המילה הריקה מקיימת את התנאי באופן ריק, משום שאינה מכילה אפסים כלל, ולכן [math]\displaystyle{ f(0)=1 }[/math]. בקשר לאיזה אינדקס פותח את הסידרה, זה תלוי באסכולה. אצלנו הגדרנו לכם שזה מתחיל מ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 סטודנטים. רוצים לחלק אותם לזוגות. כמה זוגות יתכנו?

פתרון: נסדר אותם בשורה - סה"כ [math]\displaystyle{ (2n)! }[/math] תמורות. צריך לבטל שני מקרים:

1. אין סדר בין הזוגות - [math]\displaystyle{ n! }[/math] אפשרויות.
2. אין סדר בתוך הזוגות - [math]\displaystyle{ (2!)^n }[/math] אפשרויות. למה??

תשובה סופית: [math]\displaystyle{ (2n)!\over n!(2!)^n }[/math]

ואני לא הבנתי למה צריך לחלק באפשרויות שצריך לבטל, ולא פשוט להפחית אותן? כלומר שהתשובה תהיה זו: [math]\displaystyle{ (2n)!-n!-(2!)^n }[/math]. הרי אם יש מספר אפשרויות, וצריך לבטל חלק, אז אינטואיטיבית אמורים להפחית!

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

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

תשובה

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

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

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

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

לא חשוב איך מסודרים האנשים בתוך הזוג שנבחר. לא חשוב אם לסדר אותם ab או ba - זה יישאר אותו זוג, אך ב- [math]\displaystyle{ (2n)! }[/math] ספרנו את כל האפשרויות.

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

הייתה פה תשובה לשאלה שלי ומשום מה היא נמחקה! אז לגביה, לא הבנתי למה בכלל משתמשים בנוסחה של [math]\displaystyle{ n \choose k }[/math].

כי את בוחרת אנשים זוגות מתוך 2 אנשים, (יש רק אפשרות אחת כזו). בפעם הראשונה התבלבלתי בסימון, זה היה צריך להיות [math]\displaystyle{ P(n,k) }[/math] ולא [math]\displaystyle{ C(n,k) }[/math]. מחקתי כי הניסוח לא היה מפורט ומדויק.

תודה על התשובה המהירה. לא הבנתי מה זה "בוחרת אנשים זוגות", למה מתוך 2 אנשים, ומה ההבדל בין [math]\displaystyle{ P(n,k) }[/math] ל- [math]\displaystyle{ C(n,k) }[/math].

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

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

צריך לפרט?

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

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

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

תשובה

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?

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

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

תשובה

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

שאלה 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 קוביות שונות...