88-341 תשעג סמסטר א/יחידות ההצגה של שיטות ספירה מבוססות מיקום
נדון כאן בשאלה מתי למספר [math]\displaystyle{ x\in[0,1) }[/math] יש הצגה יחידה בפיתוח לפי בסיס [math]\displaystyle{ b\ge 2 }[/math] כלשהו (למשל בינארי או טרינארי). הקבוצה הרלוונטית לשאלה היא קבוצת הסדרות [math]\displaystyle{ X:=\big\{0,1,\ldots,b-1\big\}^\N }[/math] . והפונקציה הרלוונטית היא [math]\displaystyle{ f:(x_n)_{n=1}^\infty\mapsto\sum\limits_{n=1}^\infty\frac{x_n}{b^n} }[/math]
משפט[עריכה]
למספר [math]\displaystyle{ x\in[0,1) }[/math] אין הצגה [math]\displaystyle{ b }[/math]-ארית יחידה או"א ישנו [math]\displaystyle{ N\in\N }[/math] ומספר [math]\displaystyle{ 0\lt k\lt b^N }[/math] כך ש- [math]\displaystyle{ x=\frac{k}{b^N} }[/math] וגם [math]\displaystyle{ k\not\equiv 0\pmod{b} }[/math]
הוכחה[עריכה]
נניח כי [math]\displaystyle{ (x_n)_{n=1}^\infty\ne(y_n)_{n=1}^\infty\in X }[/math] סדרות שונות של ספרות בבסיס [math]\displaystyle{ b }[/math] המייצגות את אותו מספר [math]\displaystyle{ x }[/math] (ז"א [math]\displaystyle{ x=\sum\limits_{n=1}^\infty\frac{x_n}{b^n}=\sum_{n=1}^\infty\frac{y_n}{b^n} }[/math]).
יהי [math]\displaystyle{ N\in\N }[/math] מיקומה של הספרה הראשונה בה הסדרות שונות זו מזו (ז"א [math]\displaystyle{ x_1=y_1,x_2=y_2,\ldots,x_{N-1}=y_{N-1},x_N\ne y_N }[/math]) נניח בה"כ כי [math]\displaystyle{ x_N\lt y_N }[/math] . אם כן:
[math]\displaystyle{ 0=f(y)-f(x)=\sum_{n=1}^\infty\frac{y_n-x_n}{b^n}=\sum_{n=1}^{N-1}0+\frac{y_N-x_N}{b^N}+\sum_{n=N+1}^\infty\frac{y_n-x_n}{b^n}=\frac{y_N-x_N}{b^N}+\sum_{n=N+1}^\infty\frac{y_n-x_n}{b^n} }[/math]
נשים לב כי הביטוי [math]\displaystyle{ \frac{y_N-x_N}{b^N} }[/math] הוא לכל הפחות [math]\displaystyle{ \frac{1}{b^N} }[/math] (זה קורה כאשר [math]\displaystyle{ y_N=x_N+1 }[/math]).
כדי לאפס את אגף ימין במשוואה הגדולה, נשאלת השאלה עד כמה שלילי יכול זנב הטור, [math]\displaystyle{ \sum\limits_{n=N+1}^\infty\frac{y_n-x_n}{b^n} }[/math] להיות?
את התשובה נקבל אם נדרוש כי לכל [math]\displaystyle{ n\ge N+1 }[/math] יתקיים [math]\displaystyle{ y_n=0,x_n=b-1 }[/math] , ואז זנב הטור הוא [math]\displaystyle{ \sum\limits_{n=N+1}^\infty\frac{0-(b-1)}{b^n}=-\frac{1}{b^N} }[/math] .
מכאן רואים שאסור שההפרש [math]\displaystyle{ y_N-x_N }[/math] יהיה גדול ממש מ-1, כי אז לא נוכל לאפס את אגף ימין בעזרת זנב הטור.
בסה"כ יש לנו שתי הצגות עבור [math]\displaystyle{ x }[/math] :
[math]\displaystyle{ x=0.x_1x_2x_3\dots x_N(b-1)(b-1)(b-1)\dots_b }[/math] וגם [math]\displaystyle{ x=0.y_1y_2y_3\dots(x_N+1)000\dots_b }[/math]
ההצגה השנייה נותנת [math]\displaystyle{ x=\sum\limits_{n=1}^N\frac{y_n}{b^n}=\sum\limits_{n=1}^N\frac{y_nb^{N-n}}{b^N}=\frac{\sum\limits_{n=1}^N y_nb^{N-n}}{b^N}=\frac{k}{b^N} }[/math]
שימו לב שזה לא למבחן, פשוט נשאלה השאלה בתרגול ורציתי לתת תשובה מסודרת. אם יש טעויות או שאלות אפשר לשלוח לי מייל. --Michael 21:13, 9 בדצמבר 2012 (IST)