Maths Olympiad Prep

Library / /39 of 64

Algebra Difficulty 7.9 National olympiad, round 2 Find the answer

A \emph{base 1010 over-expansion} of a positive integer NN is an expression of the form N=dk10k+dk110k1++d0100 N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0 with dk0d_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. Spacing and $ signs are ignored.

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 ik1i \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+11)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 1N91\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 d0N(mod10)d_0 \equiv N \pmod{10}, which uniquely determines d0d_0 since NN is not a multiple of 1010; then (Nd0)/10(N-d_0)/10 inherits the base 1010 over-expansion dk10k1++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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.