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

${n \choose k} = {n!\over k!(n-k)!}$

הוראות

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

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

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

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

ארכיון

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

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

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

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

מבחן מועד ב' 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)

שיעור חזרה

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

פתרונות

תעלו בבקשה את הפתרונות של תרגילים 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 קוביות שונות...