Maths Olympiad Prep

Library / Putnam /37 of 60

Putnam

Algebra Difficulty 7.9 National Olympiad, round 2 Find the answer

A base\emph{base} 1010 over-expansion} of a positive integer NN is an expression of the form N=dk10k+dk−110k−1+⋯+d0100 N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0 with dk≠0d_k \neq 0 and di∈{0,1,2,…,10}d_i \in \{0,1,2,\dots,10\} for all ii. Which positive integers have a unique base 10 over-expansion?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

These are the integers with no 00's in their usual base 1010 expansion. If the usual base 1010 expansion of NN is dk10k+⋯+d0100d_k 10^k + \cdots + d_0 10^0 and one of the digits is 00, then there exists an i≤k−1i \leq k-1 such that di=0d_i = 0 and di+1>0d_{i+1} > 0; then we can replace di+110i+1+(0)10id_{i+1} 10^{i+1} + (0) 10^i by (di+1−1)10i+1+(10)10i(d_{i+1}-1) 10^{i+1} + (10) 10^i to obtain a second base 1010 over-expansion. We claim conversely that if NN has no 00's in its usual base 1010 expansion, then this standard form is the unique base 1010 over-expansion for NN. This holds by induction on the number of digits of NN: if 1≤N≤91\leq N\leq 9, then the result is clear. Otherwise, any base 1010 over-expansion N=dk10k+⋯+d110+d0100N = d_k 10^k + \cdots + d_1 10 + d_0 10^0 must have d0≡N(mod10)d_0 \equiv N \pmod{10}, which uniquely determines d0d_0 since NN is not a multiple of 1010; then (N−d0)/10(N-d_0)/10 inherits the base 1010 over-expansion dk10k−1+⋯+d1100d_k 10^{k-1} + \cdots + d_1 10^0, which must be unique by the induction hypothesis.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.