שיחה:83-116 תשעד סמסטר א

חזרה לדף הקורס

גלול לתחתית העמוד

הוספת שאלה חדשה

הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).

-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן

אם אתם רוצים לשאול שאלה עליכם ליצור חשבון משתמש באתר.

שאלות

5-6

מה אומר הסימן דלטא בתרגילים 5 ו6?

עוד לא הגענו לזה. אלו תרגילים בתורת הקב', נלמד ביום רביעי. עדי

שאלה על תרגיל 2 שאלה 2

בשאלה 2 בסעיף ד'- מה ההגדרה לקבוצה חלקית של A? האם זו תת-קבוצה של A? האם בכל קבוצה שהיא תמיד אפשר להגיד שה"קבוצה ריקה" היא תת קבוצה שלה? תודה.

בעיקרון לא הגענו לזה בשיעור, אבל:

מה ההגדרה לקבוצה חלקית של A? האם זו תת-קבוצה של A? כן

האם בכל קבוצה שהיא תמיד אפשר להגיד שה"קבוצה ריקה" היא תת קבוצה שלה? כן, וגם הקבוצה עצמה: [math]\displaystyle{ \forall A\ \ \ A,\emptyset\subseteq A }[/math]. עדי

דף1-תרגיל5

שימו לב! כאשר נתון X ורוצים שתוכיחו Y, התחילו מלשאול-מה יוכיח לנו את Y? אח"כ השתמשו בנתון והגיעו למסקנה.

למשל בדף 1-שאלה 5, נתון שוויון בין ההפרש הסימטרי של A ו-B להפרש הסימטרי של A ו-C. רוצים שתוכיחו B=C. אם תתחילו משייכות להפרש הסימטרי לא יהיה לכם יותר מידי לאן להתקדם. התחילו מ-"מה מוכיח לנו שוויון בין קבוצות B ו-C(כנדרש)?" הכלה דו כיוונית! כלומר, ניקח איבר ב-B, נשתמש בנתון, ונירצה לקבל שהאיבר ב-C. וכנ"ל בכיוון ההפוך.

רמז- לאחר שלקחתם איבר ב-B בידקו מה קורה אם הוא שייך ל-A ואם לאו. עדי

תרגיל 2 שאלה 3 א'

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

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

תרגיל 2

היי האם הגענו לשלב שבו אנחנו יכולים לפתור את שאלות 8, 9 ו10? תודה! עמית מיכאלי

8-כן.

ל-9-אעלה הגדרה אחרי התירגול הקרוב.

את 10 סביר שראיתם בהרצאה אך עוד לא בתירגול.

עדי

תרגיל 2 שאלה 9

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

בבקשה: נתונה הקבוצה [math]\displaystyle{ I=\{2,3,4\} }[/math]. נגדיר את הקבוצות [math]\displaystyle{ A_i: i\in I }[/math], כלומר [math]\displaystyle{ A_2,A_3,A_4 }[/math], באופן הבא: [math]\displaystyle{ \forall i\in I\ A_i=\{x:x=i^2\cdot k,\ k\in N\} }[/math], ז"א [math]\displaystyle{ A_i }[/math] מוגדרת להיות אוסף כל הכפולות השלמות של [math]\displaystyle{ i^2 }[/math]. לדוגמא: [math]\displaystyle{ A_3=\{x:x=3^2\cdot k,\ k\in N\}=\{\ 3^2\cdot 1,\ 3^2\cdot 2,\ 3^2\cdot 3,\ 3^2\cdot 4,...\}=\{9,18,27,36,...\}=\{9k:k\in N\} }[/math].

כעת, נשאלת השאלה מי מהבאים: 1,8,1152 שייך לאיחוד שלושת הקב' (כלומר שייך לפחות לאחת מהן, או במילים אחרות הוא כפולה שלמה של 4 או 9 או 16), ומי שייך לחיתוך שלושת הקבוצות (כלומר, שייך לכולן, או במילים אחרות הוא כפולה שלמה של 4 וגם של 9 וגם של 16).

אנא עדכנו אותי אם התשובה עוזרת. עדי

תרגיל 3 שאלה 4

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

יש גם להראות שהוא על AXB, אבל זה החלק הקצר יותר.

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

[math]\displaystyle{ (a,b)\in A\times A,\ (c,d)\in C\times C\ \ then\ \ ((a,c),(b,d))\in (A\times C)^2\ \ }[/math]

ולכן תתי קב' שלה יהיו יחסים על [math]\displaystyle{ A\times C }[/math].

כמו כן [math]\displaystyle{ \ ((a,b),(c,d))\in A^2\times C^2 }[/math] ולכן תתי קב' שלה יהיו יחסים מ-[math]\displaystyle{ A^2 }[/math] ל-[math]\displaystyle{ C^2 }[/math].

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

למשל, אם תנאי הסימטריות דורש לוודא ש- [math]\displaystyle{ xRy\Rightarrow yRx }[/math]

אז ביחס מעל מכפלה קרטזית נוודא ש- [math]\displaystyle{ (x_1,x_2)R(y_1,y_2)\Rightarrow (y_1,y_2)R(x_1,x_2) }[/math]

כלומר נתחיל מ- [math]\displaystyle{ (x_1,x_2)R(y_1,y_2) }[/math], ניישם את היחס ונבדוק האם זה גורר ש- [math]\displaystyle{ (y_1,y_2)R(x_1,x_2) }[/math]. עדי

תרגיל 3 שאלה 1

שלום עדי, כשפיתחתי את הביטוי AXB=BXA שבשאלה הגעתי שלכל a,b:

(a∈A) & (b∈B) אם ורק אם (a∈B) & (b∈A) איך אני ממשיך מפה? האם לנסות את 2 האפשרויות- פעם אחת כששניהם מתקיימים ופעם אחת כששניהם לא מתקיימים? תודה, מרדכי.

למעשה כמעט סיימת. שים לב מה רשמת, [math]\displaystyle{ \ \ (a\in A \Rightarrow a\in B) \and (b\in B \Rightarrow b\in A) }[/math], זה בדיוק התנאי לשוויון קבוצות. רק נותר לך לטפל במיקרים שלא קיים [math]\displaystyle{ \ a\in A }[/math] או לא קיים [math]\displaystyle{ b\in B }[/math]. עדי

תרגיל 4

באופן כללי, כשרשום 'הוכח כי קיימת' זה שקול ל'תן דוגמא ל..'?

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

אוקיי, מודה לך. ועוד משהו קטן - עד איזה שאלה בתרגיל 4 כיסינו בחומר?

1, 2, 3ג ו-5 (בהרצאה כיסיתם הכל). תאריך ההגשה לא לרביעי הקרוב כמובן. עדי

דף 3-שאלה 4

שלום לכולם,

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

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

עדי

תרגיל: יהי [math]\displaystyle{ E }[/math] יח"ש על [math]\displaystyle{ A }[/math] ויהי [math]\displaystyle{ F }[/math] יח"ש על [math]\displaystyle{ B }[/math]. תהי [math]\displaystyle{ G=\{((a_1,b_1),(a_2,b_2)):(a_1,a_2)\in E,\ (b_1,b_2)\in F\} }[/math].

הוכח כי [math]\displaystyle{ G }[/math] יח"ש על [math]\displaystyle{ A\times B }[/math].

פתרון: ראשית, בואו נבין היטב את הגדרת [math]\displaystyle{ G }[/math].

יחס זה בנוי מזוגות סדורים של זוגות סדורים (לא [math]\displaystyle{ (a_1,b_1),(a_2,b_2) }[/math] שזו סתם רשימה של שני איברים, לא [math]\displaystyle{ (a_1,b_1)\times (a_2,b_2) }[/math] שאין לי מושג מה זה, ועוד כל מיני צורות כאלו ואחרות שהופיעו בפיתרונותיכם), כך שהקואורדינטות הראשונות מתייחסות ב-E והקואורדינטות השניות מתייחסות ב-F (ולא הזוג הראשון ב-E והזוג השני ב-F).

יש להוכיח ש-G יחס על [math]\displaystyle{ A\times B }[/math]:

כלומר, נתבונן על שתי הקואורדינטות באייברי G, בכל אחת מהן יושב זוג סדור אשר יש להראות שהוא מ-[math]\displaystyle{ A\times B }[/math]. ע"פ הגדרה

[math]\displaystyle{ (a_1,a_2)\in E,\ (b_1,b_2)\in F\ \Rightarrow a_1\in A \and b_1\in B \and a_2\in A \and b_2\in B }[/math],

היות וידוע כי E פועלת על A ו-F פועלת על B.

ע"פ הגדרת מכפלה קרטזית זה אומר ש- [math]\displaystyle{ (a_1,b_1)\in A\times B \and (a_2,b_2)\in A\times B }[/math],

וע"פ הגדרת יחס זה אומר ש-G היא תת קבוצה של [math]\displaystyle{ (A\times B)^2 }[/math] ולכן יחס על [math]\displaystyle{ A\times B }[/math].

כעת נותר להכיח שיחס זה הוא שקילות, כלומר:

רפלקסיביות: נרצה להוכיח שכל איבר מתייחס לעצמו ב-G.

בדיקת רפלקסיביות מתחילה מבדיקת כל איבר בקבוצה עליה פועל היחס שמוכיחים. אנחנו מוכיחים על G אשר כאמור פועלת על [math]\displaystyle{ A\times B }[/math], ולכן:

[math]\displaystyle{ \forall (a,b)\in A\times B }[/math]

(מה ידוע לנו לכל איבר כזה?)

[math]\displaystyle{ \Rightarrow a\in A \and b\in B }[/math]

(מה ידוע לנו לכל איבר ב-A ולכל איבר ב-B? היות ש-E ו-F יח"ש ידוע לנו שכל איבר ב-A מתייחס לעצמו ב-E וכל איבר ב-B מתייחס לעצמו ב-F)

[math]\displaystyle{ \Rightarrow (a,a)\in E \and (b,b)\in F }[/math]

לפי הגדרת G, עבור איבר ב-E ואיבר ב-F, זה בדיוק אומר שהקואורדינטות הראשונות מתייחסות לקואורדינטות השניות ב-G. כלומר:

[math]\displaystyle{ ((a,b),(a,b))\in G }[/math].

סה"כ קיבלנו [math]\displaystyle{ \forall (a,b)\in A\times B\ \ ((a,b),(a,b))\in G }[/math] ולכן G רפלקסיבי.

סימטריות: נרצה להוכיח שאם איבר מתייחס לאחר אז האחר מתייחס לאיבר ב-G.

בדיקת סימטריות מתחילה מאיבר שמתייחס לאחר ביחס שמוכיחים. אנחנו מוכיחים על G אשר כאמור פועלת על [math]\displaystyle{ A\times B }[/math], ולכן:

[math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G }[/math]

(מה זה אומר לנו ע"פ הגדרה?)

[math]\displaystyle{ \Rightarrow (a_1,a_2)\in E \and (b_1,b_2)\in F }[/math]

היות ש-E ו-F יח"ש זה אומר

[math]\displaystyle{ (a_2,a_1)\in E \and (b_2,b_1)\in F }[/math]

לפי הגדרת G, עבור איבר ב-E ואיבר ב-F, זה בדיוק אומר שהקואורדינטות הראשונות מתייחסות לקואורדינטות השניות ב-G. כלומר:

[math]\displaystyle{ ((a_2,b_2),(a_1,b_1))\in G }[/math]

סה"כ קיבלנו [math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G\Rightarrow ((a_2,b_2),(a_1,b_1))\in G }[/math] ולכן G סימטרי.

טרנזיטיביות: נרצה להוכיח שאם איבר1 מתייחס לאיבר2 שמתייחס לאיבר3 אז איבר1 מתייחס לאיבר3 ב-G.

בדיקת טרנזיטיביות מתחילה איבר1 מתייחס לאיבר2 ואיבר2 שמתייחס לאיבר3 ביחס שמוכיחים. אנחנו מוכיחים על G אשר כאמור פועלת על [math]\displaystyle{ A\times B }[/math], ולכן:

[math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G\and ((a_2,b_2),(a_3,b_3))\in G }[/math]

(מה זה אומר לנו ע"פ הגדרה?)

[math]\displaystyle{ \Rightarrow \underline{(a_1,a_2)\in E} \and \underline{\underline{(b_1,b_2)\in F}}\and \underline{(a_2,a_3)\in E} \and \underline{\underline{(b_2,b_3)\in F}} }[/math]

היות ש-E ו-F יח"ש זה אומר

[math]\displaystyle{ (a_1,a_3)\in E \and (b_1,b_3)\in F }[/math]

לפי הגדרת G, עבור איבר ב-E ואיבר ב-F, זה בדיוק אומר שהקואורדינטות הראשונות מתייחסות לקואורדינטות השניות ב-G. כלומר:

[math]\displaystyle{ ((a_1,b_1),(a_3,b_3))\in G }[/math]

סה"כ קיבלנו [math]\displaystyle{ ((a_1,b_1),(a_2,b_2))\in G\and ((a_2,b_2),(a_3,b_3))\in G\Rightarrow ((a_1,b_1),(a_3,b_3))\in G }[/math] ולכן G טרנזיטיבי.

קבוצת החזקה (תרגיל 4 שאלה 5)

האם זה נכון לומר שאם {X} מוכל ב P(B) אזי x שייך לקבוצה B?

לא. אם {X} מוכל ב [math]\displaystyle{ P(B) }[/math] אז X שייך ל [math]\displaystyle{ P(B) }[/math] ולכן X מוכל ב-B.

למשל [math]\displaystyle{ B=\{1,2,3\} =\gt \{1\}\subseteq B =\gt \{1\}\in P(B) =\gt \{\{1\}\}\subseteq P(B) }[/math]

אבל [math]\displaystyle{ \{1\} }[/math] לא שייך ל-B הוא מוכל בו ({1} בתפקיד X). עדי

תרגיל 4

היי

האם בעקבות הדחיה של התרגול היום ליום ב' זה אומר שתהיה דחיה בתאריך ההגשה?

אפשרי. נחליט לפי ההתקדמות בשיעור. עדי

תרגיל 4 שאלה 4

היי עדי, אני בתרגיל 4 שאלה 4 איך אני מתחיל להוכיח? האם גם פה מתחילים ממה שצריך להוכיה או מהנתונים?

ולדוגמא בסעי' 1 איך מוכיחים שאם C אז או A או B? כי אם מנסים בשלילה-אז גם אם לא A, עדיין ייתכן שכן C, כיוון שאולי כן B. תודה

תמיד תתחיל ממה שצריך להוכיח ותשתמש בנתונים.

(*) תזכרו שביחס להרכבה הראינו שאם היא חח"ע אז הפונ' הפנימית חח"ע ואם היא על אז הפונ' החיצונית על. השתמשו בתכונות אלו בשאלה זו.

סעיף1--הכוונה האם קורה אחד מהם. בדוק כל אחד בנפרד.

הערה: בסעיפים 2,3 קיימים נתונים מיותרים. את 2 ניתן להוכיח לפי (*) גם בלי [math]\displaystyle{ hg }[/math] חח"ע וב-3, לפי (*) [math]\displaystyle{ hg }[/math] על גם בלי שיהיה נתון.

המלצה: אם התכונה (*) לא נותנת את המבוקש נסו לקבל אינטואיציה לדוגמא נגדית בדיאגרמה ואז תרגמו אותה למיספרים באופן פורמלי. דוגמא נגדית צריכה להיות פשוטה ככל האפשר.

לדוגמא סעיף 1:

[math]\displaystyle{ hgf }[/math] חח"ע ועל. אזי, לפי (*) [math]\displaystyle{ f,gf }[/math] חח"ע ו-[math]\displaystyle{ h,hg }[/math] על (חישבו ונמקו למה). מאף אחד מהם לא נובע ש-g חח"ע או על. ננסה למצוא דוגמא נגדית.

נרצה ש-f חח"ע, h על ו-g לא זה ולא זה:

[math]\displaystyle{ A\rightarrow_f B \rightarrow_g C \rightarrow_h D }[/math] (הנקודות מתחת לכל קב' מייצגות את אייבריה)

[math]\displaystyle{ .\ \ \rightarrow\ \ .\ \ \rightarrow\ \ .\ \ \rightarrow\ \ . }[/math]

[math]\displaystyle{ \ \ \ \ \ \ .\nearrow\ \ \ \ \ .\nearrow\ \ \ \ \ \ }[/math]

מצאו דוגמא פורמלית. עדי

תרגיל 4 שאלה 3

האם נכון לקחת את הביטוי בסעיף א', להפעיל עליו את הפונקציה ולקבל באגף שמאל את איחוד הקטעים D1, D2 ובאגף ימין לקבל פונקציה על ההופכי לכל אחד מהם בנפרד, ולהפעיל את הפונקציה כמו דיסטריביוטיביות? במילים אחרות, האם פונקציה ניתן להשתמש בפונקציה באופן אנלוגי לדיסטריבוטיביות?

רק אם תוכיח קודם קודם ש- [math]\displaystyle{ f[A\cup B]=f[A]\cup f[B] }[/math] (בשביל צד ימין), זה לא קשה אבל באותו אופן תוכל כבר להוכיח את המבוקש.

זיכרו

[math]\displaystyle{ y\in f[X]\Rightarrow \exists x\in X: f(x)=y }[/math].

[math]\displaystyle{ x\in f^{-1}[Y]\Rightarrow \exists y\in Y: f(x)=y }[/math].

עדי

תרגיל 4 שאלה 4.6

אם הרכבה של H על G הפיכה, וG הפיכה, אז קיימת G^(-1) ולכן אם נרכיב את H על G על G^(-1) נקבל חזרה את H. למה זה אומר שH הפיכה?

ושאלה נוספת. בתרגול הראנו שאם הרכבה של H על G חח"ע אז G חח"ע. האם זה משפט שאפשר להשתמש בו או שצריך להוכיח את זה? והאם אפשר להכליל את זה ליותר פונקציות - שהרכבה שומרת על התכונות (חח"ע\על) של הפונקצויות ממנה היא מורכבת? (הכוונה לפונ' בצוות ההרכבה - [math]\displaystyle{ h(g(f(w(x)))) }[/math] שומרת על התכונות של w ושל h?

כן, אפשר להשתמש בתכונות מהכיתה: הרכבת חח"ע היא חח"ע, והרכבת על היא על. כמובן שבאינדוקציה זה נכון גם ליותר משתי פונקציות. (אני לא בטוחה לגבי הדוגמא [math]\displaystyle{ h(g(f(w(x)))) }[/math] שומרת על התכונות של w ושל h, כי אתה אומר משהו רק לגבי הפונקציות החיצוניות. כדי שהרכבת 4 הפונ' נהיה חח"ע/על, ארבעתן צריכות להיות חח"ע/על).

לגבי סעיף 6, נכון, ואז אם תשתמש בתכונה שציינת (כמובן שאם G הפיכה אז גם [math]\displaystyle{ G^{-1} }[/math] הפיכה. והפיכות נותנת גם חח"ע וגם על) תקבל [math]\displaystyle{ H=(G^{-1}G)H=G^{-1}(GH) }[/math] ולכן...

עדי

תרגיל 4 שאלה 3

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

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

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

עדי

פונקציות-תרגיל נוסף לדוגמא

[math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה. נגדיר [math]\displaystyle{ F:P(X)\rightarrow P(Y) }[/math] ע"י

[math]\displaystyle{ \forall A\in P(X)\ F(A)=\{f(a):a\in A\} }[/math]. (כלומר התמונה של כל איבר A ב [math]\displaystyle{ P(X) }[/math] היא קבוצת התמונות שלו ב-f: [math]\displaystyle{ f[A] }[/math].)

הוכח:

א. f חח"ע => F חח"ע,

ב. f על => F על.

פתרון:

א.

[math]\displaystyle{ \underline{F(A)=F(B)}\Rightarrow \{f(a):a\in A\}=\{f(b):b\in B\} }[/math] (כלומר לכל איבר בשמאלית קיים איבר ששווה לו בימנית, ולהיפך).

לכן

[math]\displaystyle{ \forall a\in A\ \exists b\in B:f(a)=f(b)\and \forall b\in B\ \exists a\in A:f(a)=f(b) }[/math]

היות ו-f חח"ע

[math]\displaystyle{ \forall a\in A\ \exists b\in B:a=b \and \forall b\in B\ \exists a\in A:a=b }[/math]

ולכן [math]\displaystyle{ \underline{A=B} }[/math] כנדרש.

ב.

[math]\displaystyle{ \underline{\forall C\in P(Y)}\ \ \ \ \underbrace{\forall c\in C\ \exists a\in A:f(a)=c} }[/math]

[math]\displaystyle{ \ \ \ \ \ \ \ \ \ \ \ \ \ }[/math]היות ו-f על

כלומר, היות וכל איבר ב-Y הוא תמונה תחת f, בפרט כל איבר ב-C הוא תמונה תחת f. ולכן, המקור (תחת F) שיתן את קבוצת התמונות C היא קבוצת המקורות שלו:

[math]\displaystyle{ \underline{\exists A\in P(X):}A=\{a:f(a)\in C\}\ \ and\ \ therefore\ \ \underline{F(A)=}\{f(a):a\in A\}=\{f(a):f(a)\in C\}=\underline{C} }[/math].

תרגיל 4 שאלה 3

הי, למה בסעיף ד' אני לא יכול להפריך באותה צורה שעשית ב-ג'? תודה.

כי שני מקורות יכולים להישלח לאותה תמונה אבל מקור לא יכול להישלח לשתי תמונות. עדי

תרגיל 4 שאלה 4 סעיף א'

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

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

לא, אתה לא יכול להפריך דברים נכונים.

עדי

תרגיל 4 שאלה 4 סעיף 2

(*==הרכבה)האם לא מספיק ש h*g*f חח"ע בכדי לקבוע כי g*f חח"ע(לפי התכונה שראינו בשיעור)? אם כי בתשובות, כתוב כי מנתון זה מסיקים f חח"ע בלבד

נכון. ראה "הערה" בדיון שכותרתו "תרגיל 4 שאלה 4". עדי

הוכחת פונקציה כ-"על"

עדי שלום!

אנחנו חוזרים כל הזמן על ההגדרה של "על": שלכל Y בתמונה קיים X כך ש: Fx מחזיר Y. אבל כאשר אנו נדרשים להוכיח שהפונקציה היא "על" אנחנו מסתבכים ולא מבינים איך עושים את זה.. נשמח אם תוכלי להסביר לנו איך, כי כמה שאת מנסה אנחנו עדיין מתבלגנים.. תודה! אבישי וישי.

"...ההגדרה של "על": שלכל Y בטווח קיים..."

אולי כדאי שתיתנו לי דוגמא שהסתבכתם (או מס' דוגמאות ככל שתירצו) ואסביר כיצד ליישם עליהן את העיקרון. עדי

תרגיל 6 שאלה 1

היי עדי, קבעתי פונקציה f שמוגדרת מ-R ל [0,1) כך ש: לכל x היא נותנת את 1/x, אבל זה טוב רק לאיברים שמחוץ לקטע [0,1). לאיפה אני אשלח את האיברים שנמצאים בקטע הזה?

האמת שהחומר של עוצמות לא יושב לי טוב בראש. אני לא יודע איך להתחיל לעבוד על שאלה 2 לדוג'. אשמח לכיוון. מרדכי.

עוד לא תירגלנו את כל החומר. בכל מקרה שימו לב לשינוי התחום ל-[math]\displaystyle{ (0,1) }[/math] (אני פשוט לא מאמינה שנספיק להגיע להתאמה בין קטע סגור-סגור לפתוח-סגור).

בכל מקרה את העבודה הקשה עשית כשהעברת קטעים אין סופיים [math]\displaystyle{ [1,\infty) }[/math] ו- [math]\displaystyle{ (-\infty,-1] }[/math] לקטעים סופיים [math]\displaystyle{ (0,1] }[/math] ו-[math]\displaystyle{ [-1,0) }[/math] ע"י [math]\displaystyle{ \frac{1}{x} }[/math].

ראינו שלהעביר קטע סופי לקטע סופי, זה לא בעיה-ע"י כיווץ/מתיחה והזזה.

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

[math]\displaystyle{ R=(-\infty,-1]\cup(-1,1)\cup[1,\infty)\longrightarrow (0,1)=(0,1/4]\cup(1/4,3/4)\cup[3/4,1) }[/math]

(או בחלוקה לשלישים, או כל חלוקה אחרת).

כעת, התאם את ההזזה שלך [math]\displaystyle{ [1,\infty)\rightarrow (0,1]\rightarrow [3/4,1) }[/math] ע"י כיווץ הקטע [math]\displaystyle{ (0,1] }[/math] פי מינוס ארבע והזזתו 1 קדימה.

אותו הדבר לחלק השלילי: התאם את ההזזה שלך [math]\displaystyle{ (-\infty,-1]\rightarrow [-1,0)\rightarrow (0,1/4] }[/math] ע"י כיווץ הקטע [math]\displaystyle{ [-1,0) }[/math] פי מינוס ארבע.

ההתאמה בין הקטע [math]\displaystyle{ (-1,1) }[/math] לקטע [math]\displaystyle{ (1/4,3/4) }[/math] היא כמובן ע"י כיווץ פי ארבע והזזה של חצי קדימה.

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

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

[math]\displaystyle{ \vdots\ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ }[/math]

[math]\displaystyle{ (1,3)\ \ (2,3)\ \ (3,3)\ \ \cdots }[/math]

[math]\displaystyle{ (1,2)\ \ (2,2)\ \ (3,2)\ \ \cdots }[/math]

[math]\displaystyle{ (1,1)\ \ (2,1)\ \ (3,1)\ \ \cdots }[/math]

לא נירצה לסדר שורה אחר שורה, או עמודה אחר עמודה, אלא?

עדי

הוכחת הפונקציה כ"על"

לגבי דוגמה להוכחה של "על", תרגיל 5 שאלה 6D. נשמח אם נוכל לקבל הסבר. תודה.

מעולה! תעלו כמה שיותר, גם אם לא מהש.ב.

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

אשתמש בסעיפים c-d כדי להדגים את שני המיקרים.

[math]\displaystyle{ f(x)=\frac{1}{1+x^2} }[/math]

טיוטא- ניקרא לתמונה [math]\displaystyle{ y }[/math] ונחפש את מקורה [math]\displaystyle{ x }[/math]:

[math]\displaystyle{ y=\frac{1}{1+x^2} }[/math] במקרה של c האיבר y ממשי (כי הטווח הוא R), ונרצה לראות האם המקור x הוא ממשי (כי התחום הוא R).

[math]\displaystyle{ \frac{1}{y}=1+x^2 }[/math] ההופכי של ממשי הוא ממשי

[math]\displaystyle{ \frac{1}{y}-1=x^2 }[/math] ממשי פחות 1 הוא ממשי

[math]\displaystyle{ \sqrt{\frac{1}{y}-1}=x }[/math] אבל לא כל שורש של ממשי הוא ממשי.

לכן, סעיף c הוא לא על. איפה נחפש את הדוגמא הנגדית? כאשר [math]\displaystyle{ \frac{1}{y}-1 }[/math] הוא שלילי, כי שורש של שלילי איננו ממשי:

[math]\displaystyle{ y=2\Rightarrow \frac{1}{y}-1\lt 0\Rightarrow \sqrt{\frac{1}{y}-1}\in C\backslash R }[/math].

אם נשנה למשל את התחום ל-C, או את הטווח לממשיים החיוביים זה יפתור את הבעיה.

בואו נראה כיצד d פותר את הבעיה:

טיוטא:

[math]\displaystyle{ \frac{1}{1+x^2}=y }[/math] כאשר [math]\displaystyle{ y\in(0,1] }[/math]

[math]\displaystyle{ 1+x^2=\frac{1}{y} }[/math] כאשר [math]\displaystyle{ 1/y\in[1,\infty) }[/math]

[math]\displaystyle{ x^2=\frac{1}{y}-1 }[/math] כאשר [math]\displaystyle{ \frac{1}{y}-1\in[0,\infty)=R^+\cup\{0\} }[/math]

[math]\displaystyle{ x=\sqrt{\frac{1}{y}-1} }[/math] כל שורש של ממשי אי שלילי הוא ממשי אי שלילי.

כלומר, גילינו ש-[math]\displaystyle{ \forall y\in(0,1]\ \ \sqrt{\frac{1}{y}-1}\in R^+\cup\{0\} }[/math]

אם האיבר הנ"ל בתחום אז יש איבר בתחום ששווה לו, נקרא לו x, לכן:

[math]\displaystyle{ \underline{\forall y\in(0,1]\ \exists x\in R^+\cup\{0\}:} \sqrt{\frac{1}{y}-1}=x\Rightarrow }[/math]

(וזה החלק של העבודה ב"רוורס". כלומר בודדנו את x כדי לוודא שהטענה נכונה, ועכשיו נבודד בחזרה את y ונטען אותה)

[math]\displaystyle{ \underline{y=}\frac{1}{1+x^2}=\underline{f(x)} }[/math].

עדי

תרגיל 5 שאלה 7 ב'

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

בבקשה: מה שאפשר להוציא באופן אוטומטי מהפיכות ההרכבה נתן לנו את הפיכות f. מה שעומד לרשותינו כרגע זה

1. f חח"ע ועל

2. fgf חח"ע ועל

3. gf חח"ע

4. fg על

ואין מסקנות אוטומטיות נוספות, לכן נוכיח לפי הגדרה.

נרצה להוכיח ש-g חח"ע, נתחיל משוויון בין תמונות של a,b תחת g, ונקווה לגלות שוויון בין a ל-b. בדרך נשתמש ב1-4:

[math]\displaystyle{ \underline{g(a)=g(b)} }[/math]

(נרצה להשתמש בחד-חד-ערכיות של gf, ולכן כדי להוסיף את f לפני g נאמר ש-) a ו-b הם תמונות תחת f כי f על, לכן קיימים להם מקורות x ו-y בהתאמה, [math]\displaystyle{ \exists x,y:f(x)=a,f(y)=b }[/math] ולכן:

[math]\displaystyle{ gf(x)=g(f(x))=g(f(y))=gf(y) }[/math]. כעת, gf חח"ע ולכן:

[math]\displaystyle{ x=y }[/math] נפעיל f על שני האגפים, היות ו-f פונקציה נקבל:

[math]\displaystyle{ f(x)=f(y) }[/math], ולכן [math]\displaystyle{ \underline{a=b} }[/math] כנדרש.

נרצה להוכיח ש-g על, נתחיל מאיבר y בטווח של g, ונקווה לגלות שקיים לו מקור תחת g בתחום של g. בדרך נשתמש ב1-4:

מכיוון שההרכבות הנתונות מוגדרות (אחרת לא היו פונקציות ובפרט לא הפיכות) הרי שכל התחומים והטווחים בשאלה זהים:

[math]\displaystyle{ f,g:A\rightarrow A }[/math]

כעת ניקח איבר כללי בטווח g ונראה מה ידוע לנו עליו-

(ה"טיוטא" ששימשה אותי לבניית ההוכחה היא שרוצים [math]\displaystyle{ g(x)=y }[/math], כלומר נירצה לקשר בין x ל-y כאשר מתחילים מ-y.

אבל: [math]\displaystyle{ y=f^{-1}f(y) }[/math] בזכות ההפיכות של f.

אם נעביר את ההופכית של f אגף נקבל [math]\displaystyle{ fg(x)=f(y) }[/math], ולכן כל מה שחסר הוא להשתמש בתכונת העל של fg כדי לומר שלכל z יש מקור x תחת fg ולקרוא ל [math]\displaystyle{ \ \ f(y) }[/math] z (מה שמקשר את y ל-z). עכשיו נשתמש בזה ב"רוורס")

[math]\displaystyle{ \forall y\in A\ \exists z\in A:\ f(y)=z }[/math] כי f פונקציה.

כעת, מכיוון ש-fg על

[math]\displaystyle{ \forall z\in A\ \exists x\in A:\ fg(x)=z }[/math].

בסה"כ קיבלנו (אם לכל y יש z ולכל z יש x, אז בטרנזיטיביות לכל y יש x):

[math]\displaystyle{ \forall y\in A\ \exists x\in A:\ fg(x)=z=f(y) }[/math], ומכיוון ש-f חח"ע:

[math]\displaystyle{ \forall y\in A\ \exists x\in A:\ g(x)=y }[/math] כפי שרצינו.

עדי

שאלה 4 תרגיל 6

עדי בוקר טוב, בשאלה 3 הוכחנו כי העוצמה בפונ' A->B שווה B בחזקת העוצמה של A. בשאלה 4 זה נראה שאנחנו מוכיחים ש P(A) שווה ל 2 בחזקת העוצמה של A עבור מקרה פרטי שב-B יש רק 2 איברים. מה היה קורה אילו היינו לוקחים 3 איברים ב-B, או אפילו קבוצה אינסופית?

בשאלה 3 הוכחנו כי העוצמה של קב' הפונקציות מ-A ל-B שווה לעוצמת B בחזקת העוצמה של A.

בשאלה 4 זה נראה שאנחנו מוכיחים ש [math]\displaystyle{ P(A) }[/math] (שהיא איננה קב' של פונקציות כמו ב3) שווה ל 2 בחזקת העוצמה של A.

2 בחזקת העוצמה של A הוא מקרה פרטי של 3 כאשר ב-B יש 2 איברים. ולכן ניתן להשתמש ב-3 עבור מקרה פרטי זה כדי להראות שוויון בין העוצמה של קב' הפונ' מ-A לשני אייברים, שלפי 3 היא שווה ל-2 בחזקת העוצמה של A, שנרצה להוכיח ב-4 שהיא שווה לעוצמת קב' החזקה של A.

מה הקשר בין שתי הקב'? בקב' הפונ' מ-A לשני אייברים, בכל פונקציה, כל איבר יכול להישלח לאיבר הראשון או השני. בקב' החזקה של A, בכל תת קבוצה, כל איבר יכול להשתייך או לא להשתייך לתת קבוצה. נשתמש בהתאמה זו בדיוק ע"מ להראות שוויון עוצמות.

מה היה קורה אילו היינו לוקחים 3 איברים ב-B, או אפילו קבוצה אינסופית?

לא הבנתי את השאלה, או איך היא קשורה ל-4.

עדי

השאלה שלי בעצם האם ההוכחה תקפה גם כאשר B קב' הגדולה מ-2 איברים או אפילו קב' אינסופית?

אם אתה מתכוון ל-3? התשובה היא כן, [math]\displaystyle{ |\{f:A-\gt B\}|=|B|^{|A|}\ \ \forall A,B }[/math]

4 הוא מקרה פרטי של 3 כש- [math]\displaystyle{ |B|=2 }[/math]. אם תיקח [math]\displaystyle{ B }[/math] מעוצמה אחרת תקבל [math]\displaystyle{ |B|^{|A|} }[/math] שונה מ-[math]\displaystyle{ 2^{|A|} }[/math] ולכן לא רלוונטי ל-[math]\displaystyle{ P(A) }[/math].

עדי

תרגיל 6 שאלה 3

בוקר טוב עדי! לא הבנתי איך פותרים ב"פתרון" את השאלה. ובכלל, איך אפשר להגדיר פונ' הפיכה לפונ' שהיא לא חח"ע ועל!?

ראשית, אתה לא מגדיר פונ' הפיכה לפונ' שהיא לא חח"ע ועל, אתה מגדיר פונקציה הפיכה בין קבוצת פונקציות כלשהן לקבוצה אחרת, במקרה הזה-למכפלה קרטזית של הטווח. הפונקציות {f:A->B} הם המקורות שלך, הם לא בהכרח חחע/על, עליהם נפעיל פונקציה חחע ועל. כלומר ההתאמה בין אוסף הפונקציות {f:A->B} לטווח שבחרנו היא הפיכה, לא בין A לבינו.

במקרה הזה המפתח הוא ש-A ו- B הן סופיות. לכן ניתן למספר את אייברי A: [math]\displaystyle{ \ \ a_1,...,a_m }[/math] ולפי סדר זה להחשיב את סדר התמונות (שהן ב-B): [math]\displaystyle{ f(a_1)=b_{i_1},...,f(a_m)=b_{i_m} }[/math] (לא נקרא להם [math]\displaystyle{ b_1,...,b_m }[/math] כי אלו חלק מאיברי B. אנחנו פשוט רוצים לבחור m מתוכם, אבל לא בהכרח את ה-m הראשונים).

כעת, נשלח כל פונקציה מA לB (את הפונקציה עצמה. f היא מקור, אנחנו לא מגדירים f:A->B, אלא מגדירים לאן f (חחע או לא/על או לא) נישלחת ע"י פונ' g שהיא חח"ע ועל) ל-m-יית התמונות של [math]\displaystyle{ (a_1,...,a_m) }[/math]. מכיוון שתמונת [math]\displaystyle{ a_i }[/math] מוגדרת באופן אחד ויחיד, ומכיוון שכל פונקציה מגדירה m-יית תמונות באופן אחד ויחיד, ההתאמה ל [math]\displaystyle{ B^m }[/math] תהיה חח"ע ועל:

*לכל m-יה ב-[math]\displaystyle{ B^m }[/math] פונקציה השולחת את [math]\displaystyle{ (a_1,...,a_m) }[/math] אליה.

*כמו כן, פונקציות שונות יגדירו m-יות שונות היות ושוני בין פונקציות מתבטא בשוני בתמונות אשר במקרה שלנו מגדירות את ה-m-יה ב-[math]\displaystyle{ B^m }[/math] במקרה בשאלה זו אוסף המקורות הם פונקציות בעצמם

**אם הפונ' מהתחום אינה חח"ע אז ב-m-יה הסדורה שתתקבל ב- [math]\displaystyle{ B^m }[/math] יהיה אינקס חוזר, וזה בסדר גמור, יש איברים שכאלו ב-[math]\displaystyle{ B^m }[/math] ונרצה לכסות גם אותם.

**אם פונ' מהתחום אינה על אז אז ב-m-יה הסדורה ב- [math]\displaystyle{ B^m }[/math] לא יופיעו כל [math]\displaystyle{ b_1,...,b_n\in B }[/math], , וזה בסדר גמור, יש איברים שכאלו ב-[math]\displaystyle{ B^m }[/math] ונרצה לכסות גם אותם.

עדי

תרגיל 6 שאלה 1 ד'

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

השימוש הוא לא בהכלה דו כיוונית אלא חד-כיוונית פעמיים. A הוא ריבוע שמכיל את העיגול B, השתמש בריבוע C המוכל ב-B ותקבל: [math]\displaystyle{ C\subseteq B\subseteq A }[/math] אשר גורר כי: [math]\displaystyle{ |C|\leq |B| \leq |A| }[/math]. שיוויון העוצמות בין A ל-C נעשה כמו בכיתה ע"י טרנספורמציות לינאריות בשתי הקואורדינטות. כתוצאה מכך תקבל שב-[math]\displaystyle{ |C|\leq |B| \leq |A| }[/math] הקצוות שווים ולכן גם האמצע. עדי

תרגיל 6 שאלה 2

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

אני מניחה שהתכוונת לתרגיל 7, שאלה 2. הסוגריים תקינים, קודם "וגם q" אח"כ "או r". עדי

תרגיל 7

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

Done

תרגיל 8 שאלה 4 סעיף א'

היי, תוכלי בבקשה להסביר את הפתרון לסעיף הזה?

תודה רבה

תחשוב על השאלה כך: יש כיתה עם שבעה תלמידים (אז אפשר להבדיל בין כל אייברי הקבוצה, כנדרש בשאלה), מהם 4 בנים ו-3 בנות (אז אפשר לחלק את הכיתה לשתי תתי קבוצות זרות ומשלימות, כמו בשאלה). עכשיו זה כמו בחירת הועד (בלי תפקידים, כי סדר הבחירה לא משנה) שפתרנו בכיתה. כלומר, נרצה לבחור ועד בן 3 תלמידים כך שבדיוק שניים מהם בנים (וממילא השלישית תהיה בת) ולכן, שלב I: בחירת תת קב' של 2 מ-4 (4 מעל 2), שלב II: בחירת תת קב' של 1 מ-2 (2 מעל 1), והכפלה בין השלבים. עדי

שאלה בקומבינטוריקה

שאלה ששאלו אותי ולא הצלחתי לפתור.. בכמה דרכים אפשר לסדר 300 כדורים זהים, ב3 תאים כך שכל תא מוגבל לעד 180 כדורים? תודה!

[math]\displaystyle{ x_1+x_2+x_3=300:\ \ 0\leq x_i\leq 180\ \ \forall i }[/math].

נגדיר

[math]\displaystyle{ U=\{x_i\geq 0\} }[/math]

[math]\displaystyle{ \ A_i=\{x_i\geq 181\},\ i=1,2,3 }[/math].

רוצים[math]\displaystyle{ |\cap A_i^c| }[/math] שהם:

[math]\displaystyle{ |\cap A_i^c|=|U|-|\cup A_i|= }[/math]

[math]\displaystyle{ |U|-(|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_3\cap A_2|+|A_1\cap A_2\cap A_3|) }[/math].

[math]\displaystyle{ :|A_i| }[/math]

[math]\displaystyle{ x_1+x_2+x_3=300: x_i\geq 181, x_j\geq 0\ \ \forall j\ne i }[/math]

שקול: [math]\displaystyle{ y_1+y_2+y_3=300-181:\ y_i\geq 0\ \forall i }[/math]

[math]\displaystyle{ :|A_i\cap A_j| }[/math]

[math]\displaystyle{ x_1+x_2+x_3=300: x_i,x_j\geq 181, x_k\geq 0\ \ \forall k\ne i,j }[/math]

שקול: [math]\displaystyle{ \ \ y_1+y_2+y_3=300-2\cdot 181:\ y_i\geq 0\ \forall i }[/math]=> 0 אפשרויות, ובוודאי [math]\displaystyle{ |A_1\cap A_2\cap A_3|=0 }[/math].

(למעשה קל לראות שרק בתא אחד יכולים להיות יותר מ-180 כדורים בו זמנית. לכן המשלים למאורע המבוקש הוא קיים תא בודד ובו יותר מ-180 כדורים).

לכן: [math]\displaystyle{ |\cap A_i^c|=|U|-3|A_i| }[/math] שהם ([math]\displaystyle{ \ 300+3-1 }[/math] מעל [math]\displaystyle{ \ 3-1\ }[/math]) פחות 3 פעמים ([math]\displaystyle{ \ 119+3-1\ }[/math] מעל [math]\displaystyle{ 3-1\ }[/math]).

עדי

רקורסיה משיעור החזרה

from the end of the lesson I didn't understand why this is right: f(n-1)(odd)= f(n-2) I would think it should be f(n-1)(odd)= 10*f(n-2)

There's a difference between adding an [math]\displaystyle{ n-1^{th} }[/math] unknown digit after [math]\displaystyle{ n-2 }[/math] known digits, and adding [math]\displaystyle{ n-2 }[/math] unknown digits before one known digit in the [math]\displaystyle{ n-1 }[/math] possition.

We apply the first one when expressing [math]\displaystyle{ f(n-1) }[/math] - that is, if [math]\displaystyle{ n-2 }[/math] positions are know, then if the [math]\displaystyle{ n-2 }[/math] position is odd, indeed you have [math]\displaystyle{ 10 }[/math] ways to fill the [math]\displaystyle{ n-1^{th} }[/math] position, and if it's even you have 5 ways.

We apply the second one when expressing [math]\displaystyle{ f^{(odd)}(n-1) }[/math] - that is, if the [math]\displaystyle{ n-1 }[/math] position is known and odd (which you have 5 options for) then you have [math]\displaystyle{ f(n-2) }[/math] ways to fill in the [math]\displaystyle{ n-2 }[/math] previous positions for each of the 5 odd digits: [math]\displaystyle{ 5f(n-2) }[/math].

Adi

אם כך אמור להתקיים הזהות: f(n)= 5f(n)(odd)+5f(n)(even)

זה לא קשור לשאלה, אל תבלבל. הדבר היחיד שהשתנה הוא שזה 5 כפול f(n-2) ולא f(n-2) לבד.

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

איזה תכונות דיסטריביטיות אנו מכירים בקבוצות

דיסטריביטיביות האיחוד מעל החיתוך. דיסטריביטביות החיתוך מעל האיחוד. האם קיימת דיסטריביטביות החיתוך מעל החיסור. תוכלי להסביר עם סימנים?

נשאלת השאלה: האם [math]\displaystyle{ (A\setminus B)\cap C=(A\cap C)\setminus (B\cap C) }[/math]?

ובכן, ידוע לנו ש- [math]\displaystyle{ A\setminus B=A\cap B^c }[/math] (כי שניהם אומרים "שייך ל-A וגם לא שייך ל-B"). ולכן הביטוי המקורי שלנו אומר: האם [math]\displaystyle{ (A\cap B^c)\cap C=(A\cap C)\cap (B\cap C)^c }[/math]?

נבדוק:

מצד שמאל: [math]\displaystyle{ (A\cap B^c)\cap C=A\cap B^c\cap C }[/math].

מצד ימין: [math]\displaystyle{ (A\cap C)\cap (B\cap C)^c=(A\cap C)\cap (B^c\cup C^c)=(A\cap C\cap B^c)\cup(A\cap C\cap C^c) }[/math], לפי דה-מורגן והדיסטריבוטיביות שציינת של חיתוך על איחוד.

מכיוון ש-[math]\displaystyle{ (A\cap C\cap C^c) }[/math] היא קבוצה ריקה, נקבל שביטוי זה הוא בדיוק [math]\displaystyle{ (A\cap C\cap B^c) }[/math], ולכן הדיסטרובוטיביות הנ"ל אכן מתקיימת.

עדי

קומבינטוריקה תרגיל 8 שאלה 8

מדוע בחירת r מתוך מספרים שונים 1,2,3,...n זה כמו לסדר r אחדים וn אפסים כך שאין שני אחדים ברצף?

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

עדי

הגדרת השאלה

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

סתם...

אני לא מצליח להבין מה אתם דורשים בדיוק בבקשות להלן (לבצע אני כן מצליח): הוכח / הוכח פורמלית / הוכח ע"פ הגדרה

אני חושב שזה בעיקר סביב נושא הקב', אז אשתמש בהם לדוג':

לפעמים הכוונה היא להישאר בעולם הקב'-

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

ולפעמים הכוונה היא לחזור לעולם הלוגיקה השלם, ולהתייחס לשייכות של האיברים עצמם לקב'-

ואז חזרתם לאטומים ופס', והשתמשנו בהתאם בקשרים ('וגם', 'גורר', 'שלילה' וכו'), והראנו שהדברים נגררים/שקולים.

מקווה שהשאלה הייתה ברורה.

תודה מראש

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

לא זכור לי שראיתי דרישה להוכיח "ע"פ הגדרה", אם מצאת משהו כזה תשלח לי.

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

עדי

מכפלה קרטזית בין קבוצות

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

קבוצה מוגדרת ע"י [math]\displaystyle{ A=\{x:x\in A\} }[/math] וריקה במקרה שלא קיים x כזה.

מכפלה קרטזית מוגדרת ע"י [math]\displaystyle{ X_1\times...\times X_n=\{(x_1,...,x_n):x_i\in X_i\} }[/math], ולכן אם קיים i אשר עבורו לא קיים [math]\displaystyle{ x_i\in X_i }[/math] (כלומר [math]\displaystyle{ X_i }[/math] היא הקבוצה הריקה כפי שדרשת) אז [math]\displaystyle{ X_1\times...\times X_n }[/math] ריקה (לא קיימים איברים ב-[math]\displaystyle{ X_i }[/math] ולכן לא קיימות n-יות סדורות, או זוגות סדורים במקרה הפרטי ש-n=2 כפי שאתה תיארת, כך ש האיבר ה-i מגיע מהקבוצה ה-i).

עדי

שאלה 3ג בתרגול חזרה

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

אני ממש לא מבינה. את מי אתה מחשיב כוקטור? (איברי מכפלה קרטזית הם וקטורים, אבל בשום שלב לא מכפילים ביניהם ואני לא מבינה כיצד מכפלה כזו תוכיח שוויון עוצמות) מי הם i ו-j?

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

עדי

תרגיל 5 שאלה 7 סעיף ב

מדוע g על?

צודק, חסר שם חלק בהוכחה...

ראשית נציין שמתוך ההרכבה הנתונה [math]\displaystyle{ f:A \rightarrow B,g:B\rightarrow A }[/math] אחרת ההרכבות לא מוגדרות.

החלק החסר:

טענת עזר- אם fg על ו-f חח"ע אז g על.

הוכחה-

[math]\displaystyle{ \forall a\in A \exists b\in B: f(a)=b }[/math] כי f פונקציה.

[math]\displaystyle{ \forall b\in B \exists b'\in B: fg(b')=b }[/math] כי fg על.

ולכן:

[math]\displaystyle{ \forall a\in A \exists b'\in B:f(a)=fg(b') }[/math]. היות ו-f חח"ע זה אומר:

[math]\displaystyle{ \forall a\in A \exists b'\in B:a=g(b') }[/math] אשר מוכיח את טענת העזר.

כעת fgf הפיכה, לכן fgf=(fg)f חח"ע ועל ולכן f חח"ע, fg על ותנאי טענת העזר מתקיימים.

עדי

עדי, האם אפשר להגיד כי f הפיכה לפי סעיף א', ולכן תהי f^-1 הופכית לf, ואז: f^-1 fgf f^-1 היא הרכבה של פונקציות הפיכות, ולכן היא גם הפיכה, ומצד שני f^-1 f היא פונקציית הזהות, ולכן נשארים רק עם g, ומכאן נובע שהיא הפיכה?

בהחלט! עדי

קומבינטוריקה

שלום עדי! למה חשוב לנו להמיר את הגדלים בבעיה לגדלים שהם =<1 או 0, כמו בדוגמא ה3 שהבאת לנו בכיתה? מה עומד מאחורי העניין ומתי אנחנו יודעים שצריך להמיר ואיך? תודה ישי ואבישי.

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

אופן ההמרה- ע"י מניפולציות אלגבריות, נבין בהתאם לנתון מי המשתנה שיהיה גדול או שווה מאפס, כאשר תמיד המשתנים שלמים:

[math]\displaystyle{ x_i\geq t =\gt y_i=x_i-t\geq 0 }[/math]

[math]\displaystyle{ x_i\gt t =\gt x_i\geq t+1 =\gt y_i=x_i-t-1\geq 0 }[/math]

[math]\displaystyle{ x_i\leq t =\gt y_i=t-x_i\geq 0 }[/math]

[math]\displaystyle{ x_i\lt t =\gt x_i\leq t-1 =\gt y_i=t-1-x_i\geq 0 }[/math]

והמקרה הפחות פשוט [math]\displaystyle{ k\leq x_i\leq t }[/math] שפותרים ע"י הכלה והדחה כפי שהראיתי בדיון קודם "שאלה בקומבינטוריקה- שאלה ששאלו אותי ולא הצלחתי לפתור.. בכמה דרכים אפשר לסדר 300 כדורים זהים, ב3 תאים כך שכל תא מוגבל לעד 180 כדורים? תודה!"

עדי

??? לא ראינו דוגמא כזאת(השניים האחרונים, איך אנחנו מכניסים את y(i) למשוואה כאשר xi שלילי? צריך להפחית אותו בצד השני של המשוואה?

בהחלט ראינו, כל המישתנים יהיו שליליים ולכן [math]\displaystyle{ ...-X_1-X_2-...=...-(X_1+X_2+...) }[/math] ונציב במקום הסכום. עדי

תרגיל 6 שאלה 1.א

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

תזיז לקטע סימטרי ביחס ל-0 (למשל (1,1-)) ורק אז תזיז את הקטע הזה לקטע המבוקש בשאלה ע"י כיווץ והזזה.

בעיקרון אנחנו מסתכלים על R כעל קטע פתוח-פתוח בין מינוס אינסוף לאינסוף:

<--------------(------)------------->

כאשר הקטע (1,1-) כבר בתחום המבוקש, רק תכווץ אותו כדי "לפנות מקום" ליתר הממשיים. למשל

[math]\displaystyle{ (-1,1)\rightarrow (-1/2,1/2) }[/math].

כעת ע"י [math]\displaystyle{ 1/x }[/math] נכניס את יתר הממשיים לקטע המבוקש, נכווץ ונזיז כדי לא לפגוע בחח"ע:

[math]\displaystyle{ (-\infty,-1]\rightarrow (-1,-1/2] }[/math]

ו- [math]\displaystyle{ [1,\infty)\rightarrow [1/2,1) }[/math].

עדי

סורי שזה חוזר על עצמו.. אבל כדי להוכיח שהפונ' חח"ע ועל אמרת שהיא על תחומים שונים, וליניארית... אבל 1/ax למיטב ידיעתי אינה פונקציה ליניארית... אז השאלה למה אני טועה? או האם צריך להוכיח את כל האפשרויות, למשל בחח"ע - שאם הXים באים מאותו תחום, או מתחומים שונים. ואז יש בעצם 6 אפשרויות שצריך לחשוב עליהם...

לא אמרתי שהיא צריכה להיות לינארית, אמרתי שאם היא לינארית אז החח"ע היא מיידית (למשל בפונ' שתשלח את (1,1-) ל-(1/2,1/2-)).

בכל מקרה אם הפונקציות פועלות על תחומים זרים (שנותנים יחד את כל התחום) ושולחות לטווחים זרים (שנותנים יחד את כל הטווח) אז רק נותר לבדוק חח"ע ועל של כל פונקציה (או במקרה שלנו נותר לבדוק חח"ע ועל עבור הפונקציות ששולחות [math]\displaystyle{ (-\infty,-1]\rightarrow (-1,-1/2] }[/math] ו- [math]\displaystyle{ [1,\infty)\rightarrow [1/2,1) }[/math]).

עדי

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

אתה צודק, היא לא לינארית בכל תחום אלא חח"ע, תיקנתי את זה. אם הפונ' שולחת תחומים שונים לתמונות זרות אז מן הסתם בין תחומים שונים לא תהיה חזרה על תמונות ולכן נותר לבדוק רק Xים מאותם תחומים-במקרה שלנו פונקציות לינאריות (שהן חח"ע ועל) ופונ' מהצורה [math]\displaystyle{ \frac{1}{ax}+b }[/math] (שהן חח"ע) מתחום לתמונה שלהן (ולכן על). עדי

קב' החזקה של בת מניה

בוקר טוב

1. למה כשאנחנו מגדירים את עוצמת קב' החזקה של הטבעיים, אנחנו מתייחסים לקב' הטווח כ-2?

2. למה בתכונה עצמה - עוצמת קב' החזקה = עוצמת הטווח בחזקת עוצמת התחום, אנחנו לא משתמשים ב'מקור' וב'תמונה'- שזה יותר אינטואיטיבי?

תודה מראש ושבת שלום

ללא קשר לטבעיים, לכל קבוצה A עוצמת קבוצת החזקה היא [math]\displaystyle{ 2^{|A|} }[/math].

ללא קשר לקבוצת החזקה, עצמת קבוצת הפונקציות מ-A ל-B היא [math]\displaystyle{ |B|^{|A|} }[/math].

ניתן להוכיח את הראשון באמצעות השני ע"י השוואת עוצמת קבוצת החזקה של A לעוצמת קבוצת הפונקציות מ-A לקבוצה בת שני איברים. כלומר, בהנחה שהוכחת את השני, ניישם אותו עבור [math]\displaystyle{ |B|=2 }[/math], נקבל [math]\displaystyle{ 2^{|A|} }[/math], ונראה שוויון עוצמות ע"י הפונקציה אשר שולחת כל תת קבוצה של A לפונקציה האופיינית שלה (הפונקציה השולחת את אייברי תת הקב' ל-1 והיתר ל-0).

"עוצמת קב' החזקה = עוצמת הטווח בחזקת עוצמת התחום"-בקבוצת חזקה אין תחום וטווח אז אני לא מבינה למה הכוונה. נראה לי שבילבלת בין השניים אולי?

"אנחנו לא משתמשים ב'מקור' וב'תמונה'- שזה יותר אינטואיטיבי"- לא הבנתי את ההערה. (בכל מקרה מקור הוא מהתחום ותמונה היא מהטווח.)

עדי

רקורסיה

נסמן ב An את מס המילים השונות באורך n המורכבות מאותיות a-g שבהן האות a איננה מופיעה פעמיים. א. מצא תנאי נסיגה עבור [math]\displaystyle{ a_n }[/math] שאלה שלי: מדוע לא נכון להגיד:

[math]\displaystyle{ a(n)= 6a^{(a)}(n-1)+7a^{(b)}(n-1)+7a^{(c)}(n-1)+ }[/math]

[math]\displaystyle{ 7a^{(d)}(n-1)+7a^{(e)}(n-1)+7a^{(f)}(n-1)+7a^{(g)}(n-1) }[/math]

כי המיגבלה לך היא לא לגבי האות האחרונה (אין רצף של a-ים) אלא לגבי כל המילה (a לא מופיעה פעמיים):

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

ניקח את [math]\displaystyle{ A_{n-1} }[/math] ונירצה להשלים את המקום ה-n.

אם [math]\displaystyle{ a\in A_{n-1} }[/math] אז יש 6 דרכים להשלים, אם [math]\displaystyle{ a\notin A_{n-1} }[/math] אז יש 7 דרכים להשלים. לכן: [math]\displaystyle{ f(n)=6f^{(a\in)}(n-1)+7f^{(a\notin)}(n-1)=6f(n-1)+f^{(a\notin)}(n-1) }[/math]. מילה מאורך n-1 ללא a היא מילה מעל b-g ללא מיגבלות ולכן: [math]\displaystyle{ f(n)=6f(n-1)+6^{n-1} }[/math] כאשר [math]\displaystyle{ 6^{n-1} }[/math] הוא החלק הלא הומוגני.

(אשמח לדעת מאיפה התרגיל)

עדי

טעיתי בניסוח, a איננה מופיעה פעמיים ברצף. עכשיו מדוע הנוסחא שלי לא נכונה?

למה החלטת שהיא לא נכונה? זו איננה תשובה סופית אבל ההתחלה נכונה. עדי

כי בכיתה ראינו שלוקחים an= 6a(A)(n-1)+7a(b-g)(n-1)

a(b-g)(n-1)=a(n-2)

לא נכון, לא איחדנו בין המיקרים ללא המיגבלה באופן- [math]\displaystyle{ a(b-g)(n-1)=a(n-2) }[/math], אלא פירטנו מה קורה בכל מקרה.

למשל ב"סדרות שוחד" ראינו מה קורה אם ניגמר ב-2,4 ו-6 בניפרד, על אף של-2 ו-4 אין מיגבלה, כל אחד "זכה" ל-[math]\displaystyle{ a(n) }[/math] משלו.

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

[math]\displaystyle{ a(n)= 6a^{(a)}(n-1)+7a^{(b)}(n-1)+7a^{(c)}(n-1)+ }[/math]

[math]\displaystyle{ 7a^{(d)}(n-1)+7a^{(e)}(n-1)+7a^{(f)}(n-1)+7a^{(g)}(n-1)= }[/math]

[math]\displaystyle{ 6a(n-1)+a^{(b)}(n-1)+a^{(c)}(n-1)+a^{(d)}(n-1)+a^{(e)}(n-1)+a^{(f)}(n-1)+a^{(g)}(n-1)= }[/math]

[math]\displaystyle{ 6a(n-1)+6a(n-2) }[/math]

בכיתה פתרנו שאלה עם אי זוגי וזוגי. מדוע

f(n) = f(odd)(n)+f(even)(n)

הרי f(n)(odd) מוגדר להיות מס המספרים, כאשר הספרה האחרונה אי זוגית ספציפית. ולא כל האי זוגיים, אז למה זה מרכיב את כל f(n)

אתה צודק, חסר שם *5 לכל האורך

זה אמור להיות: [math]\displaystyle{ f(n)=5\cdot 5f^{even}(n-1)+5\cdot 10f^{odd}(n-1)= }[/math]

[math]\displaystyle{ 5 f(n-1)+5\cdot 5 f^{odd}(n-1)=5 f(n-1)+5\cdot 5 f(n-2) }[/math].

אפשר לראות זאת גם בתנאי ההתחלה השני (עם היוצא מן הכלל 4* בגלל שזה אחרי הסיפרה הראשונה שלא יכולה להיות 0).

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

עדי

כשיעלה תיקון אני אפרסם שעלה בפורום בפייסבוק

לדעתי אמור להתקיים הזהות: f(n)= 5f(n)(odd)+5f(n)(even)

ולא f(n)= f(n)(odd)+f(n)(even

כן, זה התיקון

תודה. העלתי קובץ מתוקן לשיעור חזרה (בדף הבית של הקורס).

שיעור החזרה בדף הבית לא עודכן

עודכן

תודה, פורסם בפורום שלנו. חננאל

למעשה הרעיון היה לפצל את אוסף המילים מאורך n-1 למילים שנגמרות בסיפרה זוגית ומילים שניגמרות בסיפרה אי זוגית, שזה גם פיצול לשתי קבוצות זרות. במילים אחרות לומר [math]\displaystyle{ f^{odd}(n)=f^{1}(n)+f^{3}(n)+f^{5}(n)+f^{7}(n)+f^{9}(n) }[/math]

ו-[math]\displaystyle{ f^{even}(n)=f^{0}(n)+f^{2}(n)+f^{4}(n)+f^{6}(n)+f^{8}(n) }[/math]

ואז התיקון לגירסה הקודמת הוא רק בעובדה ש- [math]\displaystyle{ f^{odd}(n-1)=5f(n-2) }[/math] ולא [math]\displaystyle{ f(n-2) }[/math] כמו שהופיע בהתחלה. אך מכיוון שבכל התרגילים פירטנו את כל האפשרויות לתו במקום ה-n-1 עדיף שהפיתרון יופיע ככה, כלומר [math]\displaystyle{ f^{odd}(n)=f^{1}(n)=f^{3}(n)=f^{5}(n)=f^{7}(n)=f^{9}(n) }[/math]

ו-[math]\displaystyle{ f^{even}(n)=f^{0}(n)=f^{2}(n)=f^{4}(n)=f^{6}(n)=f^{8}(n) }[/math]

ויש 5 מכל אחד. עדי

תשובות לשאלות רקורסיה

היי, בכל שאלה של רקורסיה, בתשובות נתת תשובה מאוד מפורטת וארוכה (כמובן כדי שאנחנו נבין). השאלה, האם גם אנחנו צריכים פירוט כזה במבחן, או מספיקה ההקדמה בסגנון: 'נגדיר Ai מלה באורך i, וf(i) מס' הדרכים ליצור אותה....'..

מה למשל פירטתי שאת/ה לא בטוח/ה לגביו? עדי

הפירוט מצויין. השאלה האם גם אני צריך לפרט כך במבחן?

הבנתי את השאלה. אני שואלת על איזה חלק בפירוט אתה שואל אם ניתן לוותר? עדי

'נגדיר Ai מלה באורך i, וf(i) מס' הדרכים ליצור אותה. A(x)i מלה הנגמרת בX... (וכו')' ומכאן לעשות פשוט את המשוואות... [math]\displaystyle{ f(n)=f(x)(n-1)+..... }[/math]ובסוף תנאי התחלה? או שצריך ממש לרשום: [math]\displaystyle{ f(n)=f(x)(n-1)+f(y)(n-1)+...= }[/math]

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

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

תרגיל 8 שאלה 2 ב'

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

איפה היתה לך דרישה ששתי אותיות יהיו סמוכות?

באופן כללי אם דורשים ש-A ו-B יהיו סמוכות יש 2! דרכים לעשות זאת. זה לא אותו הדבר כמו ש-A מופיע פעמיים וצריך לחלק ב-2! כי אין חשיבות לסדר בין A ל-A.

עדי

קומבינטוריקה

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

תודה רבה, טל

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

שאלה 4 תרגיל 8 קומבינטוריקה

שאלה 4 תרגיל 8 סעיף ד: שואלים מה מספר האפשרויות לבחור 3 כדורי כך שיהיו את 2 הצבעים. פתרתי בעזרת משלים: 3 מתוך 7 פחות 3 מתוך 4 פחות 3 מתוך 3. מדוע זה לא נכון? (קיבלתי תוצאה שונה מזו בתשובה)

זה יוצא בדיוק אותו הדבר. עדי

קבוצת מנה

בקבוצה N של מספרים טבעיים מגדירם יחס m,n) ∈ R) אם ורק אם 3 מחלק את (m^2-n^2) כמה איברים בקבוצת המנה N/R??? אם אפשר לחזור על הגדרות איך למצוא קבוצת מנה

קב' המנה היא קבוצה של נציגי מחלקות השקילות. לכן גודל קבוצת המנה הוא מספר מחלקות השקילות.

(רמז: [math]\displaystyle{ 3|(m^2-n^2) =\gt m^2-n^2=3k:k\in Z =\gt m^2=n^2(mod 3) }[/math] .) עדי

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

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

[1]= {1,2,4,5,7,8,10,11...}

[3]={3,6,9,12...}

שתי הקבוצות מרכיבות את כל הטבעיים

[math]\displaystyle{ N/R=\{[3],[1]\} }[/math]

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

[math]\displaystyle{ \forall \ n\in N\ \ n=0mod3\ or\ \ 1mod3\ or\ \ 2mod3 }[/math]

[math]\displaystyle{ if\ \ n=0mod3,\ \ then\ \ n=3k\ =\gt \ \ n^2=9k^2=0mod3 }[/math]

[math]\displaystyle{ if\ \ n=1mod3,\ \ then\ \ n=3k+1\ \ =\gt \ \ n^2=9k^2+6k+1=1mod3 }[/math]

[math]\displaystyle{ if\ \ n=2mod3,\ \ then\ \ n=3k+2\ =\gt \ \ n^2=9k^2+12k+4=9k^2+12k+3+1=1mod3 }[/math]

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

קומבינטוריקה- בלי חשיבות לסדר ועם חזרות

שלום עדי, יש לנו שתי נוסחאות שונות מההרצאה לבלי חשיבות לסדר ועם חזרות. הראשונה היא n+k-1 choose k והשניה n+k-1 choose k-1. אשמח לדעת האם מדובר בשתי נוסחאות שקולות, ואם לא באיזו להשתמש..

אתם בטוחים שלא רשום הראשונה היא n+k-1 choose k והשניה n+k-1 choose n-1?

נכון סליחה, התבלבלתי עם השניה... אני שואלת את זה בהקשר לשאלה 10 תרגיל 8 שאני לא בטוחה מי ה-n ומי ה-k..

יש 300 קילו שמתחלקים בין 4 אנשים כמו 300 אחדים שמתחלקים בין 4 משתנים או 300 כדורים זהים שמתחלקים בין 4 תאים. בקיצור n=4, k=300. עדי

תרגיל 8 שאלה 5 ג'

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

הסיבה שציינת היא בדיוק הסיבה שזה לא יוצא. אם תחשוב על זה לרגע החיתוך "קטן" יותר מנחתכיו ולכן גודלו לא יכול להתקבל ע"י הכפל ביניהם. (למשל מבין 1,2,3,4,5,6 יש שניים שמתחלקים ב-3 ושלושה שמתחלקים ב-2 אבל רק אחד שמתחלק ב-6. אולם: יש 2/6 שמתחלקים ב-3, ו-3/6 שמתחלקים ב-2 ואכן 1/3 כפוך 1/2 הם 1/6 שהוא בדיוק החלק שמתחלק ב-6). אם כן, היכן מופיע גודל החיתוך? בתוך נוסחת הכ"והד:

[math]\displaystyle{ |A\cup B|=|A|+|B|-|A\cap B| }[/math] ולכן התשובה לשאלתך היא: [math]\displaystyle{ |A\cap B|=|A|+|B|-|A\cup B| }[/math] (למשל בדוגמא מלמעלה: 1=2+3-4). עדי

תרגיל 9 שאלה 1 סעיף ב קומבינטוריקה

תרגיל 9 שאלה 1 סעיף ב, מבקשים את מספר האפשרויות לסידור 3 מבוגרים ו5 ילדים בשורה כך שבין כל שני מבוגרים יעמוד לפחות ילד אחד. פתרנו בשיטת המשלים כאשר U הוא 8! וזה פחות האפשרות בה כל המבוגרים צמודים (6!*8!).מאיך שהבנו את השאלה, המשלים הוא כאשר אין אף ילד בין המבוגרים. מדוע זה לא נכון?

עמית: כי לפי האפשרות שרשמתם יש מצב ל2 מבוגרים צמודים ילד ואז עוד מבוגר. צריך שלא יהיה שום מצב של מבוגרים צמודים - זה המשלים שלכם..

נכון. עדי

תרגיל 9 שאלה 7ב'

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

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

נכון. עדי

מדוע אי אפשר לקחת את הפתרון של א' ולחלק ב4! כסידור פנימי של המזמינים??

נישאל באופן כללי מדוע החלק התחתון השמאלי בטבלה לא יכול להתקבל מהחלק התחתון הימני בטבלה כפי שעשינו בחלק העליון?

ובכן, התשובה היא מכיוון שיש חזרות. כלומר, בעוד [math]\displaystyle{ (1,2)\ne (2,1) }[/math], מתקיים [math]\displaystyle{ (1,1)=(1,1) }[/math]. סוג זה של איברים לא קיים בחלק העליון של הטבלה. כלומר, אם נחלק ב-4!, או במקרה הכללי ב- k! נוריד יותר מידי מיקרים (מיקרים אלו הם איברים מסוג (a,a) אשר מופיעים פעם אחת, וביטול הסדר מחשיב כאילו מופיעים פעמיים וצריך לבטל אחד מהם). אתה גם יכול לראות ש-[math]\displaystyle{ 3^4 }[/math] הוא מיספר אי זוגי ולכן חלוקתו ב-4! תיתן מספר לא שלם, מה שלא יתכן בספירת מספר אפשרויות.

ניתן להדגים זאת במקרה מאוד בסיסי: בחירת שניים מתוך 1,2,3 (באופן המדובר-עם חזרות, בלי סדר). אם יש חשיבות לסדר אז יהיו [math]\displaystyle{ 3^2 }[/math] אפשרויות:

11, 12, 13, 21, 22, 23, 31, 32, 33

אשר אם נחלק ב-2! יהיו 4.5... מדוע? ובכן, אי חשיבות לסדר תזהה את [math]\displaystyle{ 12=21,13=31,23=32 }[/math] אבל תמשיך ספור את 11,22,33 בניפרד (מה שכאמור לא קיים בחלק העליון של הטבלה), ואין איבר שיזוהה להם. אבל חלוקה ב-2! תחלק גם אותם... ניתן לחלק ב-2! רק את החלק שהוא ללא חזרות: 6לחלק ל-2!, ולהוסיף את הבחירות עם חזרות: 3. או פשוט 2+3-1 מעל 3-1 שהם 6. עדי

CNF

איך מעבירים את הפסוק הבא לצורת CNF? ^=וגם

-= משלים

p^-(q^r

אני פשוט עשיתי דה מורגן אחד וזה הופך לצורת CNF, אבל בתשובות יצא ביטוי ארוך

הכוונה [math]\displaystyle{ p\and\urcorner(q\and r) }[/math]? עדי

כן

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

הכלה והדחה

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

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

כלומר, אם נגדיר U להיות בחירה ללא המיגבלה (ז"א ללא חשיבות לסדר ובלי חזרות: 52 מעל 5) ו-[math]\displaystyle{ A_i }[/math] להיות בחירה ללא הסוג ה-i (ז"א שנותרו 52-13 קלפים, ו-[math]\displaystyle{ i=1,2,3,4 }[/math] עבור ארבעת הסוגים האפשריים), אז הרי שמבקשים [math]\displaystyle{ A_i^c }[/math] לכל i (כי הדרישה היא שלא יהיה חסר אף אחד מהם):

[math]\displaystyle{ |\cap_{i=1}^4 A_i|=|U|-|\cup_{i=1}^4 A_i| }[/math] (לפי דה-מורגן). כעת, את הגודל הימני במישוואה נפרש לפי הכ"והד, ולכן נירצה את גודל כל [math]\displaystyle{ A_i }[/math] (כאשר [math]\displaystyle{ A_i }[/math] אומר בחירה ללא הסוג ה-i, וגודלו זהה לכל i), גודל חיתוך כל שני [math]\displaystyle{ A_i }[/math]-ים (כאשר [math]\displaystyle{ A_i\cap A_j }[/math] אומר בחירה ללא הסוג ה-i וה-j, וגודלו זהה לכל i,j), גודל חיתוך כל שלושה [math]\displaystyle{ A_i }[/math]-ים (כאשר [math]\displaystyle{ A_i\cap A_j\cap A_k }[/math] אומר בחירה ללא הסוג ה-i, ה-k וה-j, וגודלו זהה לכל i,j,k) וגודל חיתוך ארבעת ה-[math]\displaystyle{ A_i }[/math]-יםכאשר [math]\displaystyle{ \cap A_i }[/math] אומר בחירה ללא שום סוג):

[math]\displaystyle{ =U }[/math] 52 מעל 5

[math]\displaystyle{ =|A_i| }[/math] [math]\displaystyle{ 52-13 }[/math] מעל 5, ויש 4 מעל 1 דרכים לבחור את הסוג שיושמט.

[math]\displaystyle{ =|A_i\cap A_j| }[/math] [math]\displaystyle{ 52-13\cdot2 }[/math] מעל 5, ויש 4 מעל 2 דרכים לבחור את שני הסוגים שיושמטו.

[math]\displaystyle{ =|A_i\cap A_j\cap A_k| }[/math] [math]\displaystyle{ 52-13\cdot3 }[/math] מעל 5, ויש 4 מעל 3 דרכים לבחור את שלושת הסוגים שיושמטו.

ו- מספר הבחירות ללא שום סוג=0.

לכן (כאשר [math]\displaystyle{ (a\ \ b) }[/math] מסמן a מעל b): [math]\displaystyle{ |\cap_{i=1}^4A_i|=|U|-|\cup_{i=1}^4 A_i|=(52\ \ 5)-\left((4\ \ 1)(39\ \ 5)-(4\ \ 2)(26\ \ 5)+(4\ \ 3)(13\ \ 5)-0\right) }[/math]. עדי

קומבינטוריקה-חלוקה בין מספר משתנים

זכור לי מהשיעור שאמרת שכשיש משוואה x1+x2+x3=100 ונניח כל אחד מהמשתנים הוא בין 0 ל-30, אז אפשר להגדיר משתנים חדשים y1 y2 y3 y1=30-x1 y2=30-x2 וכו'. אז למה אי אפשר לעשות את זה בשאלה שכותרתה "שאלה בקומבינטוריקה" ? מתי כן אפשר להשתמש בדרך שהראית בשיעור? תודה.

ראשית המשתנים שהגדרת נכונים כש [math]\displaystyle{ x_i\leq 30 }[/math] זה לא אותו הדבר כמו [math]\displaystyle{ 0\leq x_i\leq 30 }[/math] אשר פותרים ע"י הכ"והד כפי שניתן לראות בדיון קודם (על חלוקת כדורים זהים לתאים).

את ההערה "למה אי אפשר לעשות את זה בשאלה שכותרתה "שאלה בקומבינטוריקה" ? " ממש לא הבנתי. עדי

כלומר הדרך נכונה רק כאשר אין למשתנים הגבלה מלמטה?

זה נכון כשיש מיגבלה או מלמטה או מלמעלה. כשיש משניהם זה הכ"והד. זה מפורט מאוד בדיון:

"קומבינטוריקה שלום עדי! למה חשוב לנו להמיר את הגדלים בבעיה לגדלים..."

עדי

מועד ב'

שלום עדי

לקראת מועד ב', תוכלי לתת לנו הכוונה וטיפים?

תודה מראש,

נראה לי בשם כל הנבחנים