הוכיחו כי מספר האפשרויות לבחור k מספרים מתוך \{1,...,n\} כך שלא נבחרו זוג מספרים עוקבים שווה למספר המילים הבינאריות באורך n בהן מופיעים k אחדים בדיוק ואין בהן שני אחדים רצופים.
אני בעצם צריך להראות בייקציה בין שתי הקבוצות הבאות:
קבוצה A - מכילה את כל האפשרויות לבחור k מספרים מתוך \{1,...,n\} כך שלא נבחרו זוג מספרים עוקבים.
קבוצה B - מכילה את כל המילים הבינאריות באורך n בהן מופיעים k אחדים בדיוק ואין בהן שני אחדים רצופים.
לשם כך, הגדרתי את ההעתקה הבאה - תהי f\,:\,B\to A העתקה המוגדרת בצורה הבאה: אם הביט ה- 1\leq i\leq n דלוק אז הפונקציה תחזיר i, אחרת המספר i לא יוחזר.
הצלחתי להראות כי הפונקציה מוגדרת היטב אבל אני תקוע בשלב שבו מוכיחים כי הפונקציה חח"ע ועל. אשמח לעזרה בשני התת-שלבים הנ"ל.
לדעתי פונקציה חח"ע ועל ביניהן היא דרך קצת מסורבלת. אם המטרה היא להראות שקילות עוצמה אז אפשר ברקורסיה די בקלות (דרך קומבינטורית). אני לא יודע אם השאלה ביקשה מפורשות לבנות פונקציה כזו ולכן לא אכנס לדרך שאני מדבר אליה אלא מעתה ואילך אתעסק רק במה ששאלת.
נגדיר את f כפונקציה המוגדרת f((a_1,...,a_n)) = \{b_1,...,b_k\} כאשר לכל a_i, אם a_i\neq 0 אזי i\in \{b_1,...,b_k\} אחרת לא נעשה כלום.
כעת: יהי S=\{b_1,...,b_k\}\in A. נרכיב את הוקטור הבינארי V=(a_1,...,a_n) על ידי a_i = \begin{cases} 1, \ i\in S \\ 0, \ \text{otherwise} \end{cases}. יש כמה דברים שנרצה להראות. ראשית נרצה להראות ש-f(V)=S, אבל זה די פשוט לפי איך שהגדרנו.
שנית נרצה להראות ש-V\in B - אז נניח בשלילה שהוא לא. נשים לב ש-V מכיל בדיוק k אחדים, מאחר וב-S יש k מספרים שונים שלמים מהתחום [1,n], ולכן בהתאמה יש k איברים a_i כך ש-i\in S. לכן, אם יש k אחדים והנחנו בשלילה ש-V\not \in B, אזי יש לפחות שני אחדים עוקבים. נשים לב שלפי איך שהגדרנו, ינבע שב-S יש שני מספרים עוקבים. אבל אז S\not \in A - סתירה. הראינו שהפונקציה היא על.
עכשיו נרצה להראות ש-f חח"ע.
יהיו V_1, V_2\in B כך ש-f(V_1)=f(V_2). נניח בשלילה ש-V_1\neq V_2, לכן קיים מקום בוקטורים בו ב-V_1 יש 1 וב-V_2 יש 0 או להיפך. נניח בלי הגבלת הכלליות שההבדל הוא כמו שכתבתי ומתרחש במקום ה-i של הוקטורים. על כן, לפי הבנייה שלנו מתקיים ש-i\in f(V_1) אך מצד שני i\neq f(V_2). לכן לפי שיוויון קבוצות אנו נוכל להגיד ש-f(V_1)\neq f(V_2) וזו כמובן סתירה לנתון איתו התחלנו. כלומר, f(V_1) = f(V_2) \implies V_1=V_2 ולכן היא גם חח"ע.
כבר כתבתי את הפתרון לפני כמה ימים אבל שכחתי לשלוח אז הינה השני סנט שלי לפתרון המעולה של @lambda.
נגדיר את שתי הקבוצות הבאות:
-
קבוצה A - מכילה את כל האפשרויות לבחור k מספרים מתוך \{1,...,n\} כך שלא נבחרו זוג מספרים עוקבים.
-
קבוצה B - מכילה את כל המילים הבינאריות באורך n בהן מופיעים k אחדים בדיוק ואין בהן שני אחדים רצופים.
נגדיר את הפונקציה:
תהי f\,:\,B\to A העתקה המוגדרת בצורה הבאה: אם הביט ה- 1\leq i\leq n דלוק אז הפונקציה תחזיר i, אחרת המספר i לא יוחזר.
נראה כי הפונקציה מוגדרת היטב:
קיום: יהי b\in B מילה בינארית באורך n בה מופיעים k אחדים בדיוק ואין בהן שני אחדים רצופים. מאחר ו-b מכילה k אחדים בדיוק, נוכל להסיק כי גם f(b) מכילה k מספרים בדיוק. כמו כן, מאחר וב-b אין שני אחדים רצופים, נובע כי גם ב-f(b) לא קיים זוג מספרים עוקבים.
יחידות: נניח בשלילה שקיימים a_{1},a_{2}\in A כך שהן מתקבלים מאותו b\in B ומקימיים a_{1}\neq a_{2}. מאחר ו-a_{1} שונה מ-a_{2}, נוכל להסיק כי קיים מספר i\in[1,n] אשר נמצא ב-a_{1} אבל לא ב-a_{2}. מאחר ו-i נמצא ב-a_{1}, נוכל להסיק ע"פ הגדרת הפונקציה כי במקום ה-i של המילה הבינארית b קיים 1, אולם מאחר ו-i לא נמצא ב-a_{2}, נוכל להסיק ע"פ הגדרת הפונקציה כי במקום ה-i של המילה הבינארית b קיים אפס, סתירה. לכן בהכרח מתקיים: a_{1}=a_{2}.
נראה כי הפונקציה בייקציה:
חחע: יהיו b_{1},b_{2}\in B אשר מקיימים b_{1}\neq b_{2}. נראה כי מתקיים: f(b_{1})\neq f(b_{2}).
מאחר ומתקיים b_{1}\neq b_{2}, נוכל להסיק כי המילים הבינאריות b_{1} ו-b_{2} שונות במקום ה-i כאשר 1\leq i\leq n. בלי הגבלת הכלליות, נניח כי במקום ה-i של המילה הבינארית b_{1} קיים 1 ואילו במקום ה-i של המילה הבינארית b_{2} קיים אפס. לכן ע"פ הגדרת הפונקציה, נוכל להסיק כי המספר i נמצא ב-f(b_{1}) ואילו ב-f(b_{2}) הוא אינו נמצא, לכן נקבל: f(b_{1})\neq f(b_{2}).
על: יהי a\in A. נניח כי קיים b\in B עבורו מתקיים: f(b)=a.
נגדיר את b להיות כך שעבור כל מספר אשר יבחר מתוך \{1,...n\} אל a, הערך במקום ה-i של b יהיה 1, אחרת יהיה 0. לפיכך נוכל להסיק כי b היא מילה בינארית באורך n עם k אחדים בדיוק ואין בה שני אחדים רצופים, כלומר b\in B ומהגדרת הפונקציה נקבל f(b)=a.
מסקנה:
עקב העובדה שמדובר בקבוצות סופיות ומאחר והפונקציה f היא חח"ע ועל, נוכל להסיק כי היא בייקציה בין שתי הקבוצות A ו- B, וכי שתיהן בעלות גדלים שווים. במילים אחרות, מספר האפשרויות לבחור k מספרים מתוך \{1,...,n\} כך שלא נבחרו זוג מספרים עוקבים שווה למספר המילים הבינאריות באורך n בהן מופיעים k אחדים בדיוק ואין בהן שני אחדים רצופים.