\documentclass[12pt]{article}
\usepackage{t1enc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[polish]{babel}

%                            ---------- o ----------

\newcommand{\set}[1]{\ensuremath{\left\{ #1 \right\}}}
\newcommand{\abs}[1]{\ensuremath{\left| #1 \right|}}
\newcommand{\coset}[1]{\ensuremath{\left[ #1 \right]}}
\newcommand{\floor}[1]{\ensuremath{\left\lfloor #1 \right\rfloor}}
\newcommand{\field}[1]{\ensuremath{\mathbb{#1}}}
\newcommand{\R}{\field{R}}
\newcommand{\T}{\field{T}}
\newcommand{\Z}{\field{Z}}
\newcommand{\Zp}{\Z^+}

%                            ---------- o ----------

\begin{document}
\sloppy

%                            ---------- o ----------

\author{Mateusz Kwaśnicki}
\title{Rozwiązanie zadania M-D}
\maketitle

%                            ---------- o ----------

\section{Zadanie}

Niech $p, q$ będą liczbami naturalnymi większymi od $1$. Określamy \emph{ciąg mnożąco-dzielący} $(a_n)$ dla mnożnika $p$ i dzielnika $q$ w następujący sposób. Rozpoczynamy od $a_1 = 1$. Wyraz $a_{n+1}$ jest równy $\floor{a_n / q}$, o ile ta liczba jest dodatnia i nie wystąpiła jeszcze w ciągu, bądź $p a_n$ w przeciwnym przypadku.

Na przykład gdy $p = 3$ oraz $q = 2$, to początkowymi wyrazami ciągu M-D są liczby $1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, 21, \dots$.

Zadanie polega na stwierdzeniu, czy ciąg M-D jest permutacją ciągu liczb naturalnych. Poniżej dowodzimy, że odpowiedź jest twierdząca wtedy i tylko wtedy, gdy $\log_q p$ jest niewymierny, czyli gdy $q^n = p^m$ tylko dla $n = m = 0$. Warunek ten jest spełniony między innymi przez każdą parę liczb względnie pierwszych.

Zadanie pojawiło się na łamach kanadyjskiego czasopisma \emph{Crux Mathematicorum}, w numerze 26 (2000), zadanie 2248.

Łatwo udowodnić implikację w jedną stronę. Niech bowiem $\log_q p$ będzie liczbą wymierną, czyli $q^n = p^m$ dla pewnych względnie pierwszych $n, m$. Wówczas $d = q^{1/m} = p^{1/n}$ jest liczbą całkowitą większą od $1$, a więc każdy wyraz ciągu M-D jest potęgą liczby $d$. W szczególności liczba $d+1$ nie pojawi się w ciągu M-D.

W dalszej części udowodnimy implikację w drugą stronę.

%                            ---------- o ----------

\section{Oznaczenia}

Zbiory liczb całkowitych, całkowitych dodatnich i rzeczywistych oznaczamy odpowiednio przez $\Z$, $\Zp$, $\R$. Grupę ilorazową topologicznych grup addytywnych $\R$ oraz $\Z$ (izomorficzną z odcinkiem $\left[ 0, 1 \right)$ z dodawaniem ,,modulo 1'') będziemy oznaczać przez $\T$. Elementami $\T$ są warstwy $\coset{a} = a + \Z = \set{a + n : n \in \Z}$, gdzie $a \in \R$. Niech $\kappa : \R \rightarrow \T$ będzie kanonicznym homomorfizmem danym wzorem $\kappa(a) = \coset{a}$. Przypomnijmy, że zbiór $U \subset \T$ jest otwarty wtedy i tylko wtedy, gdy $\kappa^{-1}(U)$ jest otwartym podzbiorem $\R$. Ponadto jeśli $V$ jest otwartym podzbiorem $\R$, to $\kappa(V)$ jest otwarty w $\T$, a więc $\kappa$ jest odwzorowaniem otwartym.

%                            ---------- o ----------

\section{Formalna definicja ciągu M-D}

Ustalmy $p, q > 1$ takie, że $\log_q p$ jest liczbą niewymierną. Definiujemy ciąg M-D wraz ze zbiorami $A_n$ równaniami:
\begin{equation*}
\begin{array}{ll}
a_1 = 1, \\
A_n = \set{0} \cup \set{a_m : m \le n}, \\
a_{n+1} = p a_n & \quad \text{jeśli } \floor{a_n / q} \in A_n, \\
a_{n+1} = \floor{a_n / q} & \quad \text{jeśli } \floor{a_n / q} \notin A_n.
\end{array}
\end{equation*}
Ponadto określamy:
\begin{equation*}
\begin{array}{l}
A = \set{a_m : m \in \Zp}, \\
B = \Zp \backslash A.
\end{array}
\end{equation*}
Musimy udowodnić dwa stwierdzenia:
\begin{gather}
a_n = a_m \text{ tylko jeśli } n = m, \label{eq:first} \\
B = \emptyset. \label{eq:second}
\end{gather}

%                            ---------- o ----------

\section{Dwie własności zbiorów $A_n$, $A$ oraz $B$}

Ustalmy $n \in \Zp$ i załóżmy, że $\floor{a_n / q^k} \in A_n$ dla pewnego $k \in \Zp$. Jeśli $\floor{a_n / q^k} = 0$, to $\floor{a_n / q^{k+1}} = 0 \in A_n$. Załóżmy więc, że $\floor{a_n / q^k} > 0$, czyli $\floor{a_n / q^k} = a_m$ dla pewnego $m \le n$. Ponieważ $\floor{a_n / q^k} < a_n$, więc $m < n$. Zatem albo $\floor{a_m / q} \in A_m \subset A_n$ (i wtedy $a_{m+1} = p a_m$), albo $\floor{a_m / q} = a_{m+1} \in A_n$. Tak czy inaczej $\floor{a_n / q^{k+1}} = \floor{a_m / q} \in A_n$. Stąd indukcyjnie:
\begin{equation} \label{eq:order}
\text{Jeśli } \floor{a_n / q} \in A_n, \text{ to } \floor{a_n / q^k} \in A_n \text{ dla wszystkich } k \ge 0.
\end{equation}

%                            ---------- o ----------

Weźmy teraz $a \in A$, czyli $a = a_n$ dla pewnego $n$. Wówczas albo $\floor{a_n / q} = a_{n+1} \in A$, albo $\floor{a_n / q} \in A_n \subset A \cup \set{0}$. Zatem $\floor{a / q} \in A \cup \set{0}$. Stąd indukcyjnie $\floor{a / q^k} \in A \cup \set{0}$. Innymi słowy, jeśli oznaczymy $b = \floor{a / q^k}$, to:
\begin{equation} \label{eq:tree}
\text{Jeśli } b \in B, \text{ to } q^k b + l \in B \text{ dla wszystkich } k \in \Zp, 0 \le l < q^k.
\end{equation}

%                            ---------- o ----------

\section{Prawo skracania pod podłogą}

Wykorzystamy następujące łatwe twierdzenie o podłodze. Załóżmy, że $p a = \floor{p x}$, gdzie $x \in \R$, $a \in \Z$ zaś $p \in \Zp$. Wówczas:
\begin{equation*}
a = \floor{\frac{p a}{p}} = \floor{\frac{\floor{p x}}{p}} = \floor{\frac{px}{p}} = \floor{x}.
\end{equation*}
Zatem:
\begin{equation} \label{eq:floorlaw}
p a = \floor{p x} \text{ implikuje } a = \floor{x},
\end{equation}
jeśli $x \in \R$, $a \in \Z$, $p \in \Zp$.

%                            ---------- o ----------

\section{Dowód stwierdzenia \eqref{eq:first}}

Załóżmy nie wprost, że $a_i = a_j$ dla pewnych $i \ne j$. Niech $n$ będzie najmniejszym indeksem takim, że $a_n = a_m$ dla pewnego $m$, $0 < m < n$. Oczywiście oznacza to, że $a_n \in A_{n-1}$, a więc $a_n = p a_{n-1}$. Niech $1 < i \le m$ będzie takim indeksem, że:
\begin{equation*}
a_m = \floor{a_{m - 1} / q},
a_{m - 1} = \floor{a_{m - 2} / q}, \dots,
a_{i + 1} = \floor{a_i / q},
a_i = p a_{i - 1}.
\end{equation*}
(Taki indeks istnieje, ponieważ $a_2 = p a_1$.) Wówczas:
\begin{equation*}
p a_{n - 1} = a_n = a_m = \floor{a_i / q^{m - i}} = \floor{p a_{i - 1} / q^{m - i}}.
\end{equation*}
Na mocy \eqref{eq:floorlaw} wnioskujemy, że $a_{n-1} = \floor{a_{i-1} / q^{m - i}}$. Ponieważ $a_i = p a_{i-1}$, więc $\floor{a_{i-1} / q} \in A_{i - 1}$. Z własności \eqref{eq:order} wynika więc, że:
\begin{equation*}
a_{n - 1} = \floor{a_{i - 1} / q^{m - i}} \in A_{i - 1}.
\end{equation*}
Innymi słowy $a_{n - 1} = a_j$ dla pewnego $j$ spełniającego nierówności $0 < j \le i - 1 \le m - 1 < n - 1$. Stanowi to sprzeczność z wyborem $n$. Założenie nie wprost musi być zatem fałszywe, czyli dowiedliśmy \eqref{eq:first}. Warto zauważyć, że nie skorzystaliśmy z założenia o niewymierności $\log_q p$.

%                            ---------- o ----------

\section{Dowód stwierdzenia \eqref{eq:second}}

Ponownie załóżmy nie wprost, że $B$ jest niepusty i niech $a \in B$. Dowiedziemy, że $q^t a + s \notin B$ dla pewnych $t, s \in \Zp$, $0 \le s < q^t$, co stoi w sprzeczności z własnością \eqref{eq:tree}. Kluczową obserwacją okaże się to, że różnica między $\log_q a$ oraz $\log_q (q^t a + s)$ jest bliska liczbie całkowitej. Oznacza to, że odległość między warstwami $\coset{\log_q a}$ i $\coset{\log_q (q^t a + s)}$ w $\T$ jest bardzo mała. Wystarczy więc pokazać, że zbiór warstw $\coset{\log_q a_n}$ nie może być oddzielony od $\coset{\log_q a}$ dla wszystkich $n$. To zaś wyniknie ze związku między ciągiem $\coset{\log_q a_n}$ i obrotami niewymiernymi na $\T$.

Z udowodnionego stwierdzenia \eqref{eq:first} wynika, że $\lim_{n \rightarrow \infty} a_n = \infty$. Oznacza to, że dla nieskończenie wielu indeksów $n$ zachodzi $a_{n+1} = p a_n$. Niech $k_1, k_2, \dots$ będzie ściśle rosnącym ciągiem wszystkich takich $n$. Zatem:
\begin{equation} \label{eq:subsequence}
a_{k_{n+1}} = \floor{\frac{a_{k_n+1}}{q^{k_{n+1} - k_n - 1}}}, \quad a_{k_n+1} = p a_{k_n}.
\end{equation}
Niech $b_n = \log_q a_n$, $\alpha = \log_q p$. Założyliśmy, że $\alpha$ jest liczbą niewymierną. Określamy:
\begin{equation*}
\epsilon_n = \log_q \left( \frac{a_{k_n+1}}{q^{k_{n+1} - k_n - 1}} \right) - \log_q a_{k_{n+1}} =
b_{k_n+1} - b_{k_{n+1}} - k_{n+1} + k_n + 1.
\end{equation*}
Własność \eqref{eq:subsequence} i nierówności $\floor{x} \le x < \floor{x}+1$ dla $x \in \R$ implikują:
\begin{equation} \label{eq:epsilon}
\begin{split}
0 \le \epsilon_n & < \log_q (a_{k_{n+1}} + 1) - \log_q a_{k_{n+1}} = \\
& =
\log_q \left( \frac{a_{k_{n+1}}+1}{a_{k_{n+1}}} \right) < \frac{1}{a_{k_{n+1}} \ln q}.
\end{split}
\end{equation}
Z definicji $\epsilon_n$ oraz z \eqref{eq:subsequence} wynika, że:
\begin{equation} \label{eq:cosets}
\begin{array}{l}
\coset{b_{k_{n+1}}} = \coset{b_{k_n+1} - \epsilon_n}, \\
\coset{b_{k_n+1}} = \coset{\log_q (p a_{k_n})} = \coset{b_{k_n} + \alpha}.
\end{array}
\end{equation}
Dokładnie tego oczekiwaliśmy: warstwa $\coset{b_{k_{n+1}}}$ jest bardzo bliska warstwie $\coset{b_{k_n+1}}$, która jest obrazem warstwy $\coset{b_{k_n}}$ przez niewymierny obrót. Zanim przystąpimy do szczegółów rozumowania, przypomnijmy, że szukamy wyrazu $a_m$ takiego, że $a_m = q^t a + s$ dla pewnych $t, s \in \Zp$, $0 \le s < q^t$, lub równoważnie $b_m = \log_q a_m \in [\log_q a + t, \log_q (a + 1) + t)$.

Określmy:
\begin{equation*}
\begin{array}{l}
\delta = \log_q (a + \frac{1}{2}) - \log_q a, \\
V = \left(\log_q (a + \frac{1}{2}), \log_q (a + 1)\right), \\
U = \kappa(V).
\end{array}
\end{equation*}
Ponieważ $U$ jest niepustym, otwartym podzbiorem $\T$, zaś $\alpha$ jest liczbą niewymierną, więc (wobec minimalności obrotu niewymiernego) istnieje $L \in \Zp$ taki, że dla wszystkich $x \in \R$ zachodzi $\coset{x + l \alpha} \in U$ dla pewnego $l$, $0 \le l \le L$.

Niech $M$ będzie tak duże, że $L < M \delta \ln q$. Ponieważ $\lim_{n \rightarrow \infty} a_n = \infty$, więc istnieje $N$ takie, że $a_n > M$ dla $n \ge N$. Ustalmy $n$ takie, że $k_n \ge N$. Dla pewnego $l$, $0 \le l \le L$, zachodzi $\coset{b_{k_n} + l \alpha} \in U$. Oznacza to, że dla pewnego $i \in \Z$:
\begin{equation*}
b_{k_n} + l \alpha + i \in V.
\end{equation*}
Z definicji $V$:
\begin{equation} \label{eq:partialestimate}
\begin{array}{l}
\log_q (a + \frac{1}{2}) < b_{k_n} + l \alpha + i < \log_q (a + 1)
\end{array}
\end{equation}
Niech $m = n + l$. Korzystając z własności \eqref{eq:cosets}, otrzymujemy:
\begin{equation*}
\coset{b_{k_m}} = \coset{b_{k_n} + l \alpha - \epsilon_n - \epsilon_{n+1} - \dots - \epsilon_{m-1}}
\end{equation*}
lub równoważnie:
\begin{equation*}
b_{k_m} = b_{k_n} + l \alpha - \epsilon_n - \epsilon_{n+1} - \dots - \epsilon_{m-1} + j
\end{equation*}
dla pewnego $j \in \Z$. Teraz jeśli $n \le \nu < m$, to $k_{\nu+1} > k_n \ge N$, a więc $a_{k_{\nu+1}} > M$. Wobec \eqref{eq:epsilon} oznacza to, że $0 \le \epsilon_\nu < (a_{k_{\nu+1}} \ln q)^{-1} < (M \ln q)^{-1}$. Zatem:
\begin{equation*}
b_{k_n} + l \alpha + j - \frac{l}{M \ln q} < b_{k_m} \le b_{k_n} + l \alpha + j.
\end{equation*}
Lecz $M$ było określone tak, aby $l / (M \ln q) \le L / (M \ln q) < \delta$. Stąd:
\begin{equation*}
b_{k_n} + l \alpha + j - \delta < b_{k_m} \le b_{k_n} + l \alpha + j.
\end{equation*}
Wraz z \eqref{eq:partialestimate} i definicją $\delta$ prowadzi to do:
\begin{equation*}
\begin{array}{l}
\log_q (a + \frac{1}{2}) - i + j - (\log_q(a + \frac{1}{2}) - \log_q a) < b_{k_m} < \log_q (a+1) - i + j.
\end{array}
\end{equation*}
Ostatecznie otrzymujemy:
\begin{equation*}
\log_q a + j - i < b_{k_m} < \log_q (a + 1) + j - i.
\end{equation*}
Wyrażając ten warunek za pomocą wyjściowego ciągu, otrzymujemy:
\begin{equation*}
q^{j - i} a < a_{k_m} < q^{j - i} (a + 1).
\end{equation*}
W szczególności $j - i$ musi być dodatnie. Stąd $a_{k_m} = q^t a + s$ dla $t = i - j$ i pewnego $s$ spełniającego warunek $0 < s < q^t$. Sprzeczność z \eqref{eq:tree}.

Dowiedliśmy zatem, że $B$ jest pusty. To kończy rozwiązanie.

%                            ---------- o ----------

\end{document}
