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

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

הוראות

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

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

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

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

ארכיון

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

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

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

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

שאלות

שאלה 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]. הרי אם יש מספר אפשרויות, וצריך לבטל חלק, אז אינטואיטיבית אמורים להפחית!

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

צריך לפרט?

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

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]?

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

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

בתירגול פתרנו תרגיל כזה: מהו מספר האפשרויות לסידור 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 קוביות שונות...