Problem: Let $n$ and $y$ be two positive integers such that $y\leq n!$.Then prove that there exist unique integers $x_1,x_2,...,x_{n-1}$ such that $0\leq x_i\leq n-i$ for $i=1,2,3,...,n-1$ and $y=1+ \sum_{i=1}^{n-1} x_i(n-i)!$.

My Proof: Let $(x_1,x_2,...,x_{n-1})$ be such a tuple ,then the number of all possible tuples satisfying $0\leq x_j\leq n-j$ for $j=1,2,...n-1$ is $n!$ and the number of all possible values of $y$ is also $n!$. The tuple corresponding to $y=1$ is $(0,0,...,0)$ and tuple corresponding to $y=n!$ is $(n-1,n-2,...,[n-(n-1)])$. All other tuples will correspond to some integer $1<y<n!$. I claim that each such tuple will correspond to a different value of $y$. Let's assume that $(d_1,d_2,...,d_{n-1})$ and $(r_1,r_2,...,r_{n-1})$ are two distinct tuples which correspond to the same value of $y$. Let $k$ be the max positive integer such that $d_k\neq r_k$ ,then our assumption implies that $d_1(n-1)!+d_2(n-2)!+...+d_k(n-k)!=r_1(n-1)!+r_2(n-2)!+...+r_k(n-k)!$. Which implies that $d_k=r_k mod (n-k+1)$, as$0\leq d_k\leq n-k$ and $0\leq r_k\leq n-k$ $|d_k-r_k|\leq n-k<n-k+1$ so the only possibility that remains is $d_k-r_k=0$ $→$ $d_k=r_k$ which contradicts our assumption that $d_k≠r_k$. $$QED$$ Is my proof correct?(I have not written some steps as they were cubersome to write) Please suggest any other approach. Is this a famous problem?

  • $\begingroup$ The proof seems correct to me. It is surely not a famous problem. $\endgroup$ – k99731 Jan 3 '17 at 7:58

Another proof will be picking the minimum $k$.

Assuming $d_k > r_k$. Since $k$ is minimum, $n-k$ is maximum.

Also note that $\sum_{i=1}^{n-1} i*i! = n!-1$.

Therefore $(d_k-r_k) (n-k)! =\sum_{i=k+1}^{n-1} (r_i-d_i) (n-i)! \geq (n-k)!$.

However, $\sum_{i=k+1}^{n-1} (r_i-d_i) (n-i)! \leq \sum_{i=1}^{n-k-1} (i) (i)! = (n-k)!-1$. Contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.