88-341 תשעג סמסטר א/יחידות ההצגה של שיטות ספירה מבוססות מיקום

נדון כאן בשאלה מתי למספר $x\in[0,1)$ יש הצגה יחידה בפיתוח לפי בסיס $b\ge 2$ כלשהו (למשל בינארי או טרינארי). הקבוצה הרלוונטית לשאלה היא קבוצת הסדרות $X:=\big\{0,1,\ldots,b-1\big\}^\N$ . והפונקציה הרלוונטית היא $f:(x_n)_{n=1}^\infty\mapsto\sum\limits_{n=1}^\infty\frac{x_n}{b^n}$

משפט

למספר $x\in[0,1)$ אין הצגה $b$-ארית יחידה או"א ישנו $N\in\N$ ומספר $0<k<b^N$ כך ש- $x=\frac{k}{b^N}$ וגם $k\not\equiv 0\pmod{b}$

הוכחה

נניח כי $(x_n)_{n=1}^\infty\ne(y_n)_{n=1}^\infty\in X$ סדרות שונות של ספרות בבסיס $b$ המייצגות את אותו מספר $x$ (ז"א $x=\sum\limits_{n=1}^\infty\frac{x_n}{b^n}=\sum_{n=1}^\infty\frac{y_n}{b^n}$).

יהי $N\in\N$ מיקומה של הספרה הראשונה בה הסדרות שונות זו מזו (ז"א $x_1=y_1,x_2=y_2,\ldots,x_{N-1}=y_{N-1},x_N\ne y_N$) נניח בה"כ כי $x_N<y_N$ . אם כן:

$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}$

נשים לב כי הביטוי $\frac{y_N-x_N}{b^N}$ הוא לכל הפחות $\frac{1}{b^N}$ (זה קורה כאשר $y_N=x_N+1$).

כדי לאפס את אגף ימין במשוואה הגדולה, נשאלת השאלה עד כמה שלילי יכול זנב הטור, $\sum\limits_{n=N+1}^\infty\frac{y_n-x_n}{b^n}$ להיות?

את התשובה נקבל אם נדרוש כי לכל $n\ge N+1$ יתקיים $y_n=0,x_n=b-1$ , ואז זנב הטור הוא $\sum\limits_{n=N+1}^\infty\frac{0-(b-1)}{b^n}=-\frac{1}{b^N}$ .

מכאן רואים שאסור שההפרש $y_N-x_N$ יהיה גדול ממש מ-1, כי אז לא נוכל לאפס את אגף ימין בעזרת זנב הטור.

בסה"כ יש לנו שתי הצגות עבור $x$ :

$x=0.x_1x_2x_3\dots x_N(b-1)(b-1)(b-1)\dots_b$ וגם $x=0.y_1y_2y_3\dots(x_N+1)000\dots_b$

ההצגה השנייה נותנת $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}$

---

שימו לב שזה לא למבחן, פשוט נשאלה השאלה בתרגול ורציתי לתת תשובה מסודרת. אם יש טעויות או שאלות אפשר לשלוח לי מייל. --Michael 21:13, 9 בדצמבר 2012 (IST)