The Pigeonhole Principle and Leading Digits

One of the most enchanting aspects of the Extension 2 syllabus is how the humble Pigeonhole Principle can be paired with logarithms to answer questions that feel almost magical—like proving a power of 2 must someday begin with the digits 2025. In this problem we’ll journey through fractional parts, irrational rotations, and a continuous pigeonhole argument to build a rigorous proof from the ground up.

Problem Statement

For any real number $x$, the fractional part of $x$ is denoted by $\{x\}$ and is defined as $\{x\} = x - \lfloor x \rfloor$, where $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$. Note that $0 \le \{x\} < 1$.

For example, $\{3.14\} = 0.14$, $\{2026\} = 0$.

(i) Show that for any positive integer $M$, the ordinary decimal representation of $2^M$ begins with the digits $2025$ (i.e., $2^M = 2025\dots$) if and only if:

$$\log_{10} 2.025 \le \{M \log_{10} 2\} < \log_{10} 2.026$$

(ii) Let $\alpha$ be an irrational number. Prove that for any two distinct integers $m$ and $n$, the fractional parts $\{m\alpha\}$ and $\{n\alpha\}$ must be strictly distinct.

(iii) Let $N$ be a positive integer. By dividing the interval $[0,1)$ into $N$ equal subintervals, use the Pigeonhole Principle to prove that there exists a positive integer $k \le N$ such that:

$$0 < \{k\alpha\} < \frac{1}{N}$$

(iv) Given that $\alpha = \log_{10} 2$ is an irrational number, let

$$\delta = \log_{10} 2.026 - \log_{10} 2.025.$$

By choosing an integer $N$ such that $\frac{1}{N} < \delta$, or otherwise, deduce that there exists at least one positive integer $M$ such that $2^M$ begins with the digits $2025$.

---

Hints

• (i) Write $2^M$ in scientific notation: $2^M = c \times 10^K$. If the number starts with 2025, what is $c$ bounded between? Take the base-10 logarithm.
• (ii) Proof by contradiction. Assume $\{m\alpha\} = \{n\alpha\}$. Expand using the definition $\{x\} = x - \lfloor x \rfloor$ and isolate $\alpha$.
• (iii) Consider the $N+1$ fractional parts $\{0\}, \{\alpha\}, \{2\alpha\}, \dots, \{N\alpha\}$. Place these "pigeons" into the $N$ "holes" (subintervals).
• (iv) Think of the interval as a target of width $\delta$. Part (iii) guarantees a "step size" $\{k\alpha\}$ strictly smaller than $\delta$. Can consecutive steps jump over the target without landing inside it?

---

Solutions

• Part (i): We begin by writing $2^M$ in scientific notation. Because the number starts with the digits 2025, its significant part $c$ must satisfy $2.025 \le c < 2.026$. So $2^M = c \times 10^K$ for some integer $K \ge 0$ and $2.025 \le c < 2.026$. Taking base‑10 logarithms of both sides yields $M \log_{10} 2 = K + \log_{10} c$. Since $0 \le \log_{10} c < 1$, we must have $K = \lfloor M \log_{10} 2 \rfloor$ and $\log_{10} c = \{M \log_{10} 2\}$. Substituting this into the inequality for $c$ yields the required result.

• Part (ii): We prove this by contradiction, a natural tool when a statement about irrationality is involved. Assume $\{m\alpha\} = \{n\alpha\}$ for integers $m \ne n$. Then $m\alpha - \lfloor m\alpha \rfloor = n\alpha - \lfloor n\alpha \rfloor$, which implies

  $$\alpha = \frac{\lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor}{m - n}.$$

  The numerator is an integer and the denominator is a non‑zero integer, so this forces $\alpha$ to be rational—contradicting the premise. Thus, the fractional parts must be distinct.

• Part (iii): We now partition the continuous interval $[0,1)$ into $N$ equal subintervals of width $1/N$. From part (ii), the $N+1$ values $\{0\}, \{\alpha\}, \dots, \{N\alpha\}$ are strictly distinct. By the Pigeonhole Principle, with $N+1$ pigeons and $N$ holes, at least two of these fractional parts, say $\{i\alpha\}$ and $\{j\alpha\}$ with $i>j$, must fall in the same subinterval. Hence $0 < \{i\alpha\} - \{j\alpha\} < 1/N$. Now observe that

  $$\{i\alpha\} - \{j\alpha\} = (i-j)\alpha - (\lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor)$$

  lies in $(0,1)$, so it is exactly the fractional part $\{(i-j)\alpha\}$. Setting $k = i-j$ (where $0 < k \le N$) gives $0 < \{k\alpha\} < 1/N$.

• Part (iv): We now bring all the earlier pieces together. Since $\delta = \log_{10} 2.026 - \log_{10} 2.025$ is a positive number, we can choose an integer $N$ large enough that $1/N < \delta$. From part (iii) we obtain a positive integer $k \le N$ such that the “step size” $s = \{k\alpha\}$ satisfies $0 < s < \delta$. Consider the multiples of this step: $s, 2s, 3s, \dots$. Because $s$ is strictly smaller than the width $\delta$ of the target interval $[\log_{10} 2.025, \,\log_{10} 2.026)$, some multiple $ps$ must eventually fall inside that interval. Consequently $\{pk\alpha\} = ps$ satisfies the bounds required by part (i). Letting $M = pk$ proves the existence of a power of $2$ starting with $2025$.

---

Takeaways

• Kronecker's Theorem: This problem is a guided proof demonstrating that the orbit of an irrational rotation is dense. It guarantees that by doubling a number enough times, you can eventually generate a power of 2 that starts with any sequence of digits you desire.
• The Continuous Pigeonhole: By dividing a continuous number line into physical subintervals, we can force infinite irrational sequences to behave predictably.