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

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

משפט

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

הוכחה

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

יהי $N \in \mathbb{N}$ מיקומה של הספרה הראשונה בה הסדרות שונות זו מזו (ז"א $x_1=y_1,x_2=y_2, \dots, x_{N-1}=y_{N-1},x_N \neq 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_{n=N+1}^\infty \frac{y_n-x_n}{b^n}$ להיות?

את התשובה נקבל אם נדרוש כי לכל $n \ge N+1$ יתקיים $y_n=0,x_n=b-1$, ואז זנב הטור הוא $\sum_{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_{n=1}^N \frac{y_n}{b^n}=\sum_{n=1}^N \frac{y_n b^{N-n}}{b^N}=\frac{\sum_{n=1}^N y_n b^{N-n}}{b^N}=\frac{k}{b^N}$

---

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