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

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

הוראות

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

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

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

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

ארכיון

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

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

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

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

ארכיון 5 - לקראת המבחן

שאלות

פרטים בקשר למבחן

בחלק מהמקומות כתוב שהמבחן ב4 ובחלק 3 וחצי, אפשר שעה (וגם מיקום, אם אפשר) סופיים? תודה!

הרכבה ריקה

אם [math]\displaystyle{ S=\{(a,b)\} }[/math] ו-[math]\displaystyle{ R=\{(b,c)\} }[/math] אז S הרכבה R זו קבוצה ריקה, או "לא קיים"?

סריג

אפשר בבקשה דוגמה לסריג?

שאלה על אחת השאלות פה

מה זה: "מספר היחסים על קבוצה בעלת n איברים"? מה הכוונה?

מספר היחסים מA לA (למשל "קטן מ" בקבוצה של מספרים)

תודה. הכוונה לכל יחס אפשרי? אז יש אינסוף! למשל: קטן, גדול, מקיים [math]\displaystyle{ a-b \in Z }[/math], מקיים [math]\displaystyle{ a^2=b }[/math] ועוד ועוד ועוד... נראה לי שלא הבנתי.

ולמה זה הגודל של [math]\displaystyle{ P(A \times A) }[/math]?

העובדה שרשמת שלוש נקודות לא את הופכת הרשימה לאינסופית. יחס, כפי שלמדתם, הוא תת קבוצה של [math]\displaystyle{ A\times A }[/math]. הרי בין כל זוג סדור של איברים מהקבוצה יכול להתקיים היחס או לא להתקיים. היחס הוא הקבוצה של כל הזוגות הסדורים בינהם מתקיים היחס. בפרט, כל קבוצה המוכלת ב[math]\displaystyle{ A\times A }[/math] מהווה יחס אחד. אוסף כל היחסים הינו אוסף כל תתי הקבוצות הנ"ל וזה בדיוק [math]\displaystyle{ P(A\times A) }[/math]. ארז שיינר 15:15, 4 בספטמבר 2010 (IDT)

אההה.. הבנתי. תודה! (ומה שאני רשמתי הוא אמנם אינסופי, כי למשל [math]\displaystyle{ a^n=b }[/math] לכל [math]\displaystyle{ n \in N }[/math] הוא יחס נפרד, אבל יש שם יחסים שקולים כי הקבוצה סופית).

בדיוק, ומעל קבוצה אינסופית כמו השלמים בהחלט יש אינסוף יחסים. ארז שיינר 15:38, 4 בספטמבר 2010 (IDT)

שאלה 3 2008 מועד ב' סעיף ב'

אני לא מאמין, כתבתי עכשיו עשרות שורות של הפתרון שלי כדי לשאול אם הוא נכון, אבל זה נמחק לי =[. אז פשוט אשאל, אם אפשר, בבקשה, פתרון נכון לשאלה 3 סעיף ב', איזה פונקציה חח"ע ועל אפשר לעשות? זו שאלה קשה אז אני בטוח שיש עוד הרבה שירצו גם פתרון. תודה!!

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

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

שאלה 2 מועד ב' 2008

יש לי פתרון אבל אשמח מאם מישהו (עדיף מתרגל) ייתן את הפתרון כדי שאני אהיה בטוח, אני אנסה לכתוב את הפתרון שלי כאן: [math]\displaystyle{ (-1)^n*{1519-101n \choose 20} }[/math][math]\displaystyle{ {1519 \choose 20} + \sum_{n=1}^{14} }[/math] שיאללה אני לא מאמין שהצלחתי לכתוב את זה

אני לא מתרגל, יצא לי דומה לשלך רק שהכנסתי את הגורם הראשון לתוך הסכום, וגם נראה לי שצריך להוסיף כמה פעמים כל חיתוך של קבוצות מופיע, למשל יש 2 מתוך 20 פעמים חיתוך 2 Ai ים (אם עשית את זה בעיקרון הכלה והדחה וצריך לצאת בערך כמו שלך רק עם i מתוך 20 בתוך הסכום

כן כן שמתי לב לזה עכשיו, כתבתי את החלק של הכמה יש מתוך בדף אבל התלהבתי כל כך שהצלחתי לכתוב את זה באתר ששכחתי להוסיף, התוצאה שלי היא כזאת:

[math]\displaystyle{ ((-1)^n*{1519-101n \choose 20}*{20 \choose n}) }[/math][math]\displaystyle{ {1519 \choose 20} + \sum_{n=1}^{14} }[/math]

האמת שעכשיו אני לא בטוח אם זה צריך להיות [math]\displaystyle{ {1519-101n \choose 20} }[/math] או [math]\displaystyle{ {1519-101n \choose 20-n} }[/math]

איך להוכיח (2008 מועד ב' שאלה 1 א')

האם אפשר להוכיח ככה, או שיש דרך אחרת? נניח [math]\displaystyle{ f(x1,u1)=f(x2,u2) }[/math] וכן [math]\displaystyle{ f(x1,u1)={v1 (muchal-be) u1 | x1 (shayach-le) v1}, f(x2,u2)=cmo-x1,u1 }[/math] ולכן לכל V1, V2 שמוכלים בU1, U2 מתקיים V1=V2 ולכן U1=U2 וגם x1=x2? משהו לא נכון בהוכחה הזאת נכון? אז איך מוכיחים? תודה!

שאלות 2א+ב מועד ב 2009

שלום רב, כיצד עליי לנמק בפתרון השאלה 2א? התחלתי את הפתרון כך:

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

1. [math]\displaystyle{ n }[/math] לפני [math]\displaystyle{ n-1 }[/math]

2. [math]\displaystyle{ n }[/math] אחרי [math]\displaystyle{ n-1 }[/math]"

השאלה שלי היא איך אני מנמק לאחר מכן שקיימות [math]\displaystyle{ 0.5n! }[/math] תמורות כנדרש:

1. "...לכן לכל תמורה שתי אפשרויות ולכן בסה"כ יש [math]\displaystyle{ 0.5n! }[/math] תמורות שעונות לתנאי זה".

2. "כעת נגדיר [math]\displaystyle{ A }[/math] קבוצת כל התמורות העונות על תנאי 1, [math]\displaystyle{ B }[/math] קבוצת כל התמורות העונות על תנאי 2. כמו כן נגדיר פונקציה [math]\displaystyle{ f:A-\gt B }[/math] ע"י לכל [math]\displaystyle{ x }[/math] ב-[math]\displaystyle{ A }[/math] יתקיים ש[math]\displaystyle{ f(x)=y }[/math]כאשר [math]\displaystyle{ y }[/math] היא התמורה בה איברי [math]\displaystyle{ x }[/math] מופיעים בסדר הפוך (כלומר התמורה [math]\displaystyle{ 1,2 }[/math] תהפוך ל-[math]\displaystyle{ 2,1 }[/math]). פונקציה זו חח"ע ועל ולכן [math]\displaystyle{ |A|=|B| }[/math] ומכיוון שהחיתוך ביניהם זר הרי שאפשר לומר ש-[math]\displaystyle{ |A|+|B|=2|A|=|C| }[/math] (כאשר [math]\displaystyle{ C }[/math] היא קבוצת כל התמורות). נציב [math]\displaystyle{ |C|=n! }[/math] ונקבל את העוצמה הדרושה של [math]\displaystyle{ A }[/math]...".

הבעיה היא שדרך 1 נקראית לי לא מפורטת מספיק ודרך 2 היא די ארוכה. בסעיף א זה עוד נסבל אבל בסעיף ב זה בכלל נורא כי כבר קיימות 6 אפשרויות (ואז עליי לבנות 6 פונקציות) אז איך עליי לנמק את מה שאמרתי? תודה מראש, גל.

תשובה

אני לא מתרגל אך יש לי את הפתרון שאדם כתב באחד התרגולים שלו. כמו שאמרת, יש סך הכל [math]\displaystyle{ n! }[/math] אפשרויות לסדר את המספרים. ניתן לחלק מספר זה של אפשרויות ל2 חלקים: חלק ראשון הוא האפשרויות ש[math]\displaystyle{ n-1 }[/math] מופיע לפני [math]\displaystyle{ n }[/math] והחלק השני הוא ההפוך- [math]\displaystyle{ n }[/math] מופיע לפני [math]\displaystyle{ n-1 }[/math], ניתן לראות כי 2 חלקים אלה הם שווים, נניח אתה בודק את מספר האפשרויות בהן [math]\displaystyle{ n-1 }[/math] מופיע לפני [math]\displaystyle{ n }[/math], אז מספר האפשרויות ההפוך הוא אותו מספר כיוון שהפעם החלפת בכל אפשרות בין [math]\displaystyle{ n }[/math] ל[math]\displaystyle{ n-1 }[/math], ולכן התוצאה היא [math]\displaystyle{ 0.5n! }[/math]. בסעיף ב' אתה משתמש בתוצאה של סעיף א' ואתה יודע שהיא מתחלקת ל-3 אפשרויות ובאותו אופן כמו בסעיף א' גם 3 אפשרויות אלה הן שוות ולכן בסך הכל התוצאה היא [math]\displaystyle{ 1/6n! }[/math]. אני שוב אומר שאני לא מתרגל אבל זאת הדרך בה אדם פתר את התרגיל הזה

שאלה קצרצרה נוספת

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

תשובה

מספר היחסים על קבוצה A בת n איברים היא הגודל של [math]\displaystyle{ P(A \times A) }[/math], שהיינו [math]\displaystyle{ 2^{n^2} }[/math]. Adam Chapman 11:57, 4 בספטמבר 2010 (IDT)

שאלה קצרה מאוד על עוצמות

קבוצת כל הפונקציות מהטבעיים לקבוצת תת הקבוצות של הטבעיים, מהי עוצמתה? לפי החישוב שלי, הקבוצה שווה לP)N( בחזקת N, כלומר העוצמה שווה ל-א בחזקת א0. אך מהי העוצמה א בחזקת א0? א? או יותר, 2 בחזקת א? איך אפשר לדעת את זה? תודה רבה!

תשובה

ישנן כמה נוסחאות לגבי עוצמות אינסופיות שצריך לדעת. אחת מהן היא שאם [math]\displaystyle{ k }[/math] אינסופית ו[math]\displaystyle{ \lambda\lt k }[/math] אזי [math]\displaystyle{ k^\lambda=k }[/math]. Adam Chapman 11:29, 4 בספטמבר 2010 (IDT)

3 שאלות על הרכבת פונקציות

-אם [math]\displaystyle{ g*f=Id }[/math] אז [math]\displaystyle{ g(f(x))=x }[/math] או ש [math]\displaystyle{ f(g(x))=x }[/math]? כי ניתקלתי בבעיה שקשורה לזה (השאלה השניה). -אפשר להגיד ש אם F חחע אז F הפיכה משמאל ואם F על אז היא הפיכה מימין, נכון? -איך מוכיחים את מה שצריך להוכיח בשאלה 2 במבחן 2007 מועד א' (http://math-wiki.com/images/4/4f/BdidaExamMoedA2007.pdf) ?

ב-א', הוכחתי את הכיוון משמאל לימין, ע"י כך שאם g1*f=g2*f אז בגלל שf הפיכה מימין אז נרכיב את f-1 מימין ואז g1=g2. בכיוון השני נתקעתי.

ב-ב', לא הצלחתי בכלל. התחלתי ככה: צריך להוכיח שf חחע, כלומר או שנוכיח שאם f(a1)=f(a2) אז a1=a2 או שנוכיח שהיא הפיכה משמאל (לא בטוח מה עדיף). הפונקציה הזאת שמסומנת בסימון של קבוצה ריקה היא על ולכן והפיכה מימין, ולכן O*h=Id ולכן (ופה נתקעתי, לא הייתי בטוח [math]\displaystyle{ O(h(x))=x }[/math] ולכן (?) [math]\displaystyle{ h(x)*f=x }[/math] ופה יש משהו לא הגיוני. אפשר עזרה? תודה!

תשובה

אם [math]\displaystyle{ g*f=Id }[/math] אז [math]\displaystyle{ g(f(x))=x }[/math].

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

כיוון אחד

1) אם [math]\displaystyle{ f }[/math] חח"ע אזי היא הפיכה מימין ע"י איזושהי פונקציה שנסמנה [math]\displaystyle{ h : B \rightarrow A }[/math].

2) כעת, לכל פונקציה [math]\displaystyle{ \psi \in C^A }[/math] יש מקור [math]\displaystyle{ g=\psi \circ h \in C^B }[/math] לפי פונקציה [math]\displaystyle{ \Phi }[/math], כי [math]\displaystyle{ \Phi(g)=g \circ f=\psi \circ h \circ f=\psi }[/math] ולכן [math]\displaystyle{ \Phi }[/math] על.

כיוון שני

1) אם [math]\displaystyle{ f }[/math] לא חח"ע אז קיימים [math]\displaystyle{ a_1,a_2 \in A }[/math] שונים כך ש[math]\displaystyle{ f(a_1)=f(a_2) }[/math].

2) לכן לכל [math]\displaystyle{ g \in C^B }[/math], הפונקציה [math]\displaystyle{ \Phi(g)=g \circ f }[/math] מקיימת [math]\displaystyle{ g \circ f(a_1)=g \circ f(a_2) }[/math].

3) אולם, קיימות הפונקציות [math]\displaystyle{ h \in C^A }[/math] כך ש[math]\displaystyle{ h(a_1) \neq h(a_2) }[/math], כי [math]\displaystyle{ C }[/math] מכילה לפחות שני איברים, וכתצואה מכך [math]\displaystyle{ \Phi }[/math] איננה על.

Adam Chapman 11:25, 4 בספטמבר 2010 (IDT)

שאלה (קצת מוזרה, אבל מבלבלת) על איחוד קבוצות

נניח שX שייך לA חיתוך B חיתוך C. אני יכול להגיד בוודאות ש X שייך ל

(AחיתוךBחיתוךC) איחוד (AחיתוךBחיתוךC'(משלים)) איחוד (AחיתוךB'חיתוךC') איחוד (A'חיתוךB'חיתוךC)? האם זה נכון בטוח בגלל שאחד מהגורמים באיחוד הוא A חיתוך B חיתוך C? תודה!

תשובה

כן. ניתן לומר זאת בודאות כי אחד הגורמים באיחוד הוא הוא A חיתוך B חיתוך C.

Adam Chapman 10:49, 4 בספטמבר 2010 (IDT)

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

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

הוכחתי את 1, ע"י חילוק למקרים, אם C=100 אז A וB יכולים להיות מ1 עד 99, 99 בריבוע אפשרויות, אם C=98 אז יש 98 בריבוע אפשרויות וכך הלאה ומקבלים את הסכום הדרוש. אבל לא משנה איך אני מנסה להסתכל על זה, אני לא רואה איך העוצמה של S שווה לתוצאה שכתובה ב2. אפשר עזרה לפני המבחן? תודה רבה!!

תשובה

את חלק ב' מוכיחים באופן קומבינטורי. כשיש לנו שלישיה סדורה [math]\displaystyle{ (a,b,c) }[/math] כך ש[math]\displaystyle{ a\lt b \wedge a\lt c }[/math] אז קורה אחד (ואחד בלבד) משלושת הדברים הבאים:1) [math]\displaystyle{ b=c }[/math] או 2) [math]\displaystyle{ b\lt c }[/math] או 3) [math]\displaystyle{ b\gt c }[/math]. כל המקרים ב1) מכוסים באופן חח"ע ועל על-ידי בחירת שני איברים מתוך 100, הצבת הקטן מבין השניים באינדקס הראשון והצבת הגדול מבין השניים באינדקסים השני והשלישי; כל המקרים ב2) מכוסים באופן חח"ע ועל על-ידי בחירת 3 איברים מתוך מאה, הצבת הקטן ביותר באינדקס הראשון, הצבת האמצעי באינדקס השני והצבת הגדול ביותר באינדקס השלישי; כל המקרים ב3) מכוסים באופן חח"ע ועל על-ידי בחירת 3 איברים מתוך מאה, הצבת הקטןביותר באינדקס הראשון, הצבת הגדול ביותר באינדקס השני והצבת האמצעי באינדקס השלישי. עקב כך, מקבלים את הנוסחה הרשומה בטופס המבחן בסעיף ב'.Adam Chapman 10:46, 4 בספטמבר 2010 (IDT)

תודה

איחוד או חיתוך

סליחה שאני שואלת המון שאלות..

איך מוכיחים שאם X מוכלת ב-A חיתוך B אז X מוכלת ב-A וגם X מוכלת ב-B? (במיוחד צריך לשים לב שההוכחה לא מתאימה גם לאיחוד במקום חיתוך, בשונה מההוכחה אצלי במחברת)

שוב, תודה מראש!

שאלות זה טוב

אם [math]\displaystyle{ X \subseteq A \bigcap B }[/math] אז לכל [math]\displaystyle{ x \in X }[/math] מתקיים [math]\displaystyle{ x \in A \bigcap B }[/math], דהיינו [math]\displaystyle{ x \in A }[/math] וגם [math]\displaystyle{ x \in B }[/math]. מכיוון שלכל [math]\displaystyle{ x \in X }[/math] מתקיים [math]\displaystyle{ x \in A }[/math] אז [math]\displaystyle{ X \subseteq A }[/math], ומכיוון שלכל [math]\displaystyle{ x \in X }[/math] מתקיים [math]\displaystyle{ x \in B }[/math] אז [math]\displaystyle{ X \subseteq B }[/math]. Adam Chapman 00:16, 4 בספטמבר 2010 (IDT)

תודה רבה, אבל: אם [math]\displaystyle{ X \subseteq A \bigcup B }[/math] אז לכל [math]\displaystyle{ x \in X }[/math] מתקיים [math]\displaystyle{ x \in A \bigcup B }[/math], דהיינו [math]\displaystyle{ x \in A }[/math] או [math]\displaystyle{ x \in B }[/math]. לכל [math]\displaystyle{ x \in X }[/math] מתקיים [math]\displaystyle{ x \in A }[/math] ואז*** [math]\displaystyle{ X \subseteq A }[/math], או [math]\displaystyle{ x \in B }[/math] ואז*** [math]\displaystyle{ X \subseteq B }[/math].

מה שמסומן ב-*** כמובן לא נכון, אבל איך מסבירים את זה שהדבר נכון רק עבור חיתוך ולא איחוד?

כל [math]\displaystyle{ x\in X }[/math] מקיים [math]\displaystyle{ x\in A }[/math] -או- [math]\displaystyle{ x\in B }[/math]. בפרט, מאד ייתכן שקיים [math]\displaystyle{ x\in X }[/math] כך ש[math]\displaystyle{ x\notin A }[/math]. אתה שינית לוגית את המשפט - במקום לומר 'כל איבר שייך לA או B' אמרת 'כל האיברים שייכים לA או כל האיברים שייכים לB'. ארז שיינר 01:18, 4 בספטמבר 2010 (IDT)

באמת שיניתי לוגית את המשפט בלי לשים לב! אם כך, רק אם לכל [math]\displaystyle{ x \in X }[/math] מתקיים [math]\displaystyle{ x \in A }[/math] אז [math]\displaystyle{ X \subseteq A }[/math], ובאיחוד זה לא לכל x. הבנתי, תודה לכם!

הוכחה טריוויאלית

מהי הדרך הנכונה ביותר להוכיח שאם [math]\displaystyle{ P(A) }[/math] מוכל (או שווה) ב(ל)-[math]\displaystyle{ P(B) }[/math] אז A מוכל (או שווה) ב(ל)-B?

(פשוט ההוכחה אצלי במחברת לא ברורה לי)

תשובה

אם [math]\displaystyle{ P(A) \subseteq P(B) }[/math] אז לכל [math]\displaystyle{ X \in P(A) }[/math] מתקיים [math]\displaystyle{ X \in P(B) }[/math]. בפרט, [math]\displaystyle{ A \in P(A) }[/math] ולכן [math]\displaystyle{ A \in P(B) }[/math], כלומר [math]\displaystyle{ A \subseteq B }[/math]. Adam Chapman 23:57, 3 בספטמבר 2010 (IDT)

אהה, תודה!

יחסים

האם האיבר הקטן ביותר הוא תמיד המינימלי היחיד? (כשהוא קיים)

תשובה

כן Adam Chapman 23:32, 3 בספטמבר 2010 (IDT)

תודה!