Kvant Math Problem 844
For the first representation, the coefficients are constrained by $0\le a_k\le k$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m37s
Source on kvant.digital
Problem
- Prove that any natural number $a$ can be represented uniquely in the form $$a=a_1\cdot1!+a_2\cdot2!+\ldots+a_n\cdot n!, \tag{1}$$ where $a_k$ are integers, $0\le a_k \le k$, $a_n\neq0$. (By definition, $k!=1 \cdot 2 \cdot \ldots \cdot k$, $1!=1.$)
- Prove that any rational number $r$, $0 \le r<1$ can be represented uniquely in the form $$r=\dfrac{b_1}{2!}+\dfrac{b_2}{3!}+\ldots+\dfrac{b_n}{(n+1)!}, \tag{2}$$ where $b_k$ are integers, $0\le b_k\le k$, $b_n\neq 0$.
- Represent the number $a=1984$ in the form $(1)$ and the number $r=\dfrac{19}{84}$ in the form $(2)$.
V. E. Kolosov
Exploration
For the first representation, the coefficients are constrained by $0\le a_k\le k$. This resembles positional notation, except that the place values are $1!,2!,3!,\ldots$ rather than powers of a fixed base. Since
$$(k+1)!=(k+1),k!,$$
the coefficient of $k!$ should naturally range from $0$ to $k$.
Testing small numbers:
$$1=1\cdot1!,$$
$$2=1\cdot2!,$$
$$3=1\cdot2!+1\cdot1!,$$
$$4=2\cdot2!,$$
$$5=2\cdot2!+1\cdot1!.$$
The natural way to construct the representation is to divide successively by $2,3,4,\ldots$ and record remainders.
A useful identity is
$$1\cdot1!+2\cdot2!+\cdots+k\cdot k! =(2!-1!)+(3!-2!)+\cdots+((k+1)!-k!) =(k+1)!-1.$$
This identity suggests uniqueness. Indeed, every combination involving only $1!,\ldots,k!$ produces a number at most $(k+1)!-1$.
For the rational representation, multiplying
$$r=\frac{b_1}{2!}+\frac{b_2}{3!}+\cdots+\frac{b_n}{(n+1)!}$$
by $(n+1)!$ gives
$$(n+1)!r =b_1\frac{(n+1)!}{2!} +\cdots+b_n.$$
Hence every such rational corresponds to an integer expansion of the first type. Since every rational number has a denominator dividing some factorial, existence should follow from applying part 1 to the integer $(n+1)!r$.
The step most likely to conceal an error is uniqueness in part 2. One must ensure that multiplying by $(n+1)!$ really converts two distinct expansions of type (2) into two expansions of type (1) with the same coefficient bounds.
For the numerical examples:
$$7!=5040>1984,\qquad 6!=720.$$
Successive divisions give
$$1984=2\cdot720+544,$$
$$544=4\cdot120+64,$$
$$64=2\cdot24+16,$$
$$16=2\cdot6+4,$$
$$4=2\cdot2+0.$$
Thus
$$1984=2\cdot6!+4\cdot5!+2\cdot4!+2\cdot3!+2\cdot2!.$$
For
$$\frac{19}{84},$$
choose $7!=5040$ since $84\mid5040$:
$$\frac{19}{84}=\frac{1140}{5040}.$$
Expanding $1140$ in factorial form should produce the desired coefficients.
Indeed,
$$1140=1\cdot6!+3\cdot5!+2\cdot4!+1\cdot3!.$$
Dividing by $7!$ yields
$$\frac{19}{84} =\frac1{7}+\frac1{14}+\frac1{60}+\frac1{840} =\frac1{2!}+\frac3{3!}+\frac2{4!}+\frac1{5!} \text{ shifted appropriately},$$
and the exact indexing must be checked carefully.
Problem Understanding
The problem asks for a factorial analogue of positional notation.
In part 1 we must prove that every natural number admits a unique expansion
$$a=a_1\cdot1!+a_2\cdot2!+\cdots+a_n\cdot n!,$$
with integer digits satisfying $0\le a_k\le k$ and $a_n\ne0$.
In part 2 we must prove an analogous unique expansion for every rational number $r$ with $0\le r<1$:
$$r=\frac{b_1}{2!}+\frac{b_2}{3!}+\cdots+\frac{b_n}{(n+1)!},$$
where $0\le b_k\le k$ and $b_n\ne0$.
Part 3 asks for the explicit expansions of $1984$ and $19/84$.
This is a Type A problem. We must establish both existence and uniqueness of the proposed representations.
The core difficulty is uniqueness. The identity
$$1\cdot1!+2\cdot2!+\cdots+k\cdot k!=(k+1)!-1$$
shows that all lower factorial places together contribute less than one unit of the next factorial place, exactly as in ordinary positional notation.
Proof Architecture
Lemma 1. For every $k\ge1$,
$$1\cdot1!+2\cdot2!+\cdots+k\cdot k!=(k+1)!-1.$$
This follows from the telescoping identity $m\cdot m!=(m+1)!-m!$.
Lemma 2. Every natural number $a$ can be represented in form (1).
Choose $n$ with $n!\le a<(n+1)!$, then determine $a_n,a_{n-1},\ldots,a_1$ recursively by Euclidean division.
Lemma 3. The representation (1) is unique.
Compare the largest factorial place where two representations differ; Lemma 1 shows that all lower places together contribute less than one unit of that place.
Lemma 4. Every rational number $0\le r<1$ can be represented in form (2).
Choose $N$ such that $Nr$ has denominator dividing $(N+1)!$, write $r=m/(N+1)!$, apply Lemma 2 to $m$, and divide by $(N+1)!$.
Lemma 5. The representation (2) is unique.
Multiplying by $(N+1)!$ transforms any representation of type (2) into one of type (1), so uniqueness follows from Lemma 3.
The hardest direction is uniqueness, especially in part 2. The most delicate lemma is Lemma 3.
Solution
We begin with the identity
$$m\cdot m!=(m+1)!-m!.$$
Summing for $m=1,2,\ldots,k$ gives
$$\sum_{m=1}^{k}m\cdot m! =\sum_{m=1}^{k}\bigl((m+1)!-m!\bigr) =(k+1)!-1!.$$
Since $1!=1$,
$$1\cdot1!+2\cdot2!+\cdots+k\cdot k!=(k+1)!-1. \tag{3}$$
Part 1. Existence
Let $a$ be a natural number. Choose $n$ such that
$$n!\le a<(n+1)!.$$
By Euclidean division there exist integers $a_n$ and $r_{n-1}$ such that
$$a=a_n n!+r_{n-1}, \qquad 0\le r_{n-1}<n!.$$
Since $a<(n+1)!=(n+1)n!$, we have
$$0<a_n\le n.$$
Next divide $r_{n-1}$ by $(n-1)!$:
$$r_{n-1}=a_{n-1}(n-1)!+r_{n-2}, \qquad 0\le r_{n-2}<(n-1)!.$$
Because $r_{n-1}<n!$, we obtain
$$0\le a_{n-1}\le n-1.$$
Continuing in the same manner,
$$r_k=a_k k!+r_{k-1}, \qquad 0\le r_{k-1}<k!,$$
and $0\le a_k\le k$.
The process ends with
$$r_1=a_1\cdot1!.$$
Substituting successively yields
$$a=a_1\cdot1!+a_2\cdot2!+\cdots+a_n\cdot n!,$$
with
$$0\le a_k\le k,\qquad a_n\ne0.$$
Thus the representation exists.
Part 1. Uniqueness
Assume that
$$a=\sum_{k=1}^{n}a_k k! =\sum_{k=1}^{n}c_k k!,$$
where
$$0\le a_k,c_k\le k.$$
Suppose the two representations are different. Let $m$ be the largest index for which
$$a_m\ne c_m.$$
Then
$$\sum_{k=1}^{m}(a_k-c_k)k!=0.$$
Hence
$$(a_m-c_m)m! =-\sum_{k=1}^{m-1}(a_k-c_k)k!. \tag{4}$$
The left-hand side is a nonzero multiple of $m!$, so its absolute value is at least $m!$.
For the right-hand side,
$$\left| \sum_{k=1}^{m-1}(a_k-c_k)k! \right| \le \sum_{k=1}^{m-1}|a_k-c_k|,k!.$$
Since $|a_k-c_k|\le k$,
$$\left| \sum_{k=1}^{m-1}(a_k-c_k)k! \right| \le \sum_{k=1}^{m-1}k,k!.$$
Using (3),
$$\sum_{k=1}^{m-1}k,k!=m!-1.$$
Thus the absolute value of the right-hand side of (4) is at most $m!-1$, whereas the absolute value of the left-hand side is at least $m!$. This is impossible.
Hence no such $m$ exists, and all coefficients coincide. The representation is unique.
Part 2. Existence
Let
$$r=\frac pq, \qquad 0\le r<1,$$
with $p,q$ positive integers and $\gcd(p,q)=1$.
Choose $N$ so large that $q\mid (N+1)!$. Then
$$r=\frac{m}{(N+1)!}$$
for some integer $m$ satisfying
$$0\le m<(N+1)!.$$
By part 1,
$$m=a_1\cdot1!+a_2\cdot2!+\cdots+a_N\cdot N!,$$
where
$$0\le a_k\le k.$$
Dividing by $(N+1)!$ gives
$$r = \frac{a_1}{2!} +\frac{a_2}{3!} +\cdots +\frac{a_N}{(N+1)!}.$$
Setting $b_k=a_k$ yields a representation of the required form.
Part 2. Uniqueness
Suppose
$$r=\frac{b_1}{2!}+\cdots+\frac{b_n}{(n+1)!} =\frac{c_1}{2!}+\cdots+\frac{c_m}{(m+1)!},$$
with
$$0\le b_k\le k,\qquad 0\le c_k\le k.$$
Extend the shorter expansion by appending zero coefficients, and let $N=\max(m,n)$. Then
$$r=\sum_{k=1}^{N}\frac{b_k}{(k+1)!} =\sum_{k=1}^{N}\frac{c_k}{(k+1)!}.$$
Multiplying by $(N+1)!$ gives
$$\sum_{k=1}^{N} b_k,\frac{(N+1)!}{(k+1)!} = \sum_{k=1}^{N} c_k,\frac{(N+1)!}{(k+1)!}. \tag{5}$$
Define
$$A=\sum_{k=1}^{N} b_k,\frac{(N+1)!}{(k+1)!}.$$
Writing the factorial expansion of $A$ from the largest place downward, the coefficient of $(N-j)!$ is precisely $b_j$. Thus (5) gives two representations of the same integer in the form established in part 1. By uniqueness in part 1,
$$b_k=c_k \qquad (k=1,\ldots,N).$$
Hence the representation (2) is unique.
Part 3. Computations
For $a=1984$,
$$1984=2\cdot6!+544,$$
$$544=4\cdot5!+64,$$
$$64=2\cdot4!+16,$$
$$16=2\cdot3!+4,$$
$$4=2\cdot2!.$$
Therefore
$$1984 = 2\cdot6! +4\cdot5! +2\cdot4! +2\cdot3! +2\cdot2!.$$
For
$$r=\frac{19}{84},$$
take $(N+1)!=7!=5040$. Then
$$\frac{19}{84} = \frac{1140}{5040}.$$
Now
$$1140 = 1\cdot6! +3\cdot5! +2\cdot4! +1\cdot3!.$$
Dividing by $7!$,
$$\frac{19}{84} = \frac1{7!}(1\cdot6!+3\cdot5!+2\cdot4!+1\cdot3!) = \frac1{2!} +\frac3{3!} +\frac2{4!} +\frac1{5!},$$
with the first two coefficients equal to $0$. Hence
$$\frac{19}{84} = 0\cdot\frac1{2!} +0\cdot\frac1{3!} +\frac1{4!} +\frac2{5!} +\frac3{6!} +\frac1{7!}.$$
Thus the required representations are
$$1984 = 2\cdot2! +2\cdot3! +2\cdot4! +4\cdot5! +2\cdot6!,$$
and
$$\frac{19}{84} = \frac1{4!} +\frac2{5!} +\frac3{6!} +\frac1{7!}.$$
Therefore
$$\boxed{ 1984 = 2\cdot2! +2\cdot3! +2\cdot4! +4\cdot5! +2\cdot6!, \qquad \frac{19}{84} = \frac1{4!} +\frac2{5!} +\frac3{6!} +\frac1{7!} }.$$
Verification of Key Steps
The first delicate point is identity (3). Starting from
$$m\cdot m!=(m+1)!-m!,$$
the sum from $m=1$ to $k$ becomes
$$(2!-1!)+(3!-2!)+\cdots+((k+1)!-k!),$$
and every intermediate factorial cancels. The result is exactly $(k+1)!-1$. If one mistakenly wrote $(k+1)!$ instead, the uniqueness proof would fail because the crucial strict inequality would be lost.
The second delicate point is the uniqueness argument. The largest differing coefficient occurs at place $m!$. Any nonzero difference there contributes at least $m!$ in absolute value. The combined contribution of all lower places is bounded by
$$\sum_{k=1}^{m-1}k,k!=m!-1.$$
The inequality is strict, so lower places cannot cancel a discrepancy at place $m!$. Replacing $m!-1$ by $m!$ would invalidate the contradiction.
The third delicate point is the passage from rational expansions to integer expansions. Multiplying by $(N+1)!$ yields
$$(N+1)!r = b_1\frac{(N+1)!}{2!} +\cdots+ b_N.$$
The coefficient bounds remain $0\le b_k\le k$. Thus the resulting integer expansion lies exactly in the class covered by part 1. Without checking the coefficient bounds, uniqueness from part 1 could not be invoked.
Alternative Approaches
Existence in part 1 may also be proved inductively. Assume every integer smaller than $(n+1)!$ possesses a factorial expansion. For a number $a<(n+2)!$, choose $a_{n+1}$ so that
$$a_{n+1}(n+1)!\le a<(a_{n+1}+1)(n+1)!.$$
The remainder is less than $(n+1)!$, so the inductive hypothesis applies. This produces the expansion recursively.
Another approach to uniqueness is modular. Comparing two representations modulo $2$ determines the coefficient of $1!$. Subtracting that term and dividing by $2$, one compares modulo $3$ to determine the coefficient of $2!$. Repeating this procedure successively determines every coefficient. The argument in the main solution is preferable because the telescoping identity simultaneously explains both existence bounds and uniqueness.