# How many ways are there to represent the number $N$?

I was given a task that doesn't require any special knowledge of math, but got stuck with it. Here it is:

1. How many ways are there to represent the number $N$ in the following way: $$N = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1\cdot10+a_0 \ \ \ (1)$$ $$a \in \mathbb{Z_{\geq0}}, \ \ \ \ 0\leq a_i\leq99, \ \ i=0;1;2;3$$ for $N=1091$?

2. Do 10 different numbers $N$ that are representable exactly in 110 ways as in the $(1)$ exist?
3. How many numbers $N$ that are representable as in the $(1)$ are representable exactly in 110 ways?

I've written a program and found out that the answer for the first question is 110. But I have no any more ideas unfortunately.

Any ideas or hints leading to an analytical solution are greatly appreciated!

-
Wait a minute. You are saying ai belongs to n but ai can also be 0? – Rohinb97 Jun 3 '13 at 10:43
Ouch, that was a mistake. Fixed it. – Max Malysh Jun 3 '13 at 21:09
I do not know whether this site tells you about the edits i made, but i think i answered your 2nd and 3rd part too. – Rohinb97 Jun 8 '13 at 20:47
@Rohinb97, as long as the empty set is finite, $0$ will be a natural number ;) – Carsten S Jan 22 '14 at 20:57

Hint: write each $a_i$ as $10b_i+c_i$ with $b_i,c_i\in \{0,1,...,9\}$ (and use the uniqueness of decimal representation).

Elaboration: if you write it out like this, then you can do the following analysis for $N=10^4d_4+10^3d_3+10^2d_2+10d_1+d_0$.

1. Write $N=10^4b_3+10^3(c_3+b_2)+10^2(c_2+b_1)+10(c_1+b_0)+c_0$.
2. Notice that you can possibly have carry-overs from $10$ to $10^2$, from $10^2$ to $10^3$ and from $10^3$ to $10^4$.
3. There are exactly $(d_1+1)(d_2+1)(d_3+1)$ ways to represent $N$ with no carry-overs.
4. With a carry-over from $10$ to $10^2$ (and no other carry-overs), there are $(9-d_1)(d_2)(d_3+1)$ ways.
5. And so on.

For $1091$, the only carryover that can occur is from $10^2$ to $10^3$. So we have in total $10\cdot 1\cdot 2+10\cdot9\cdot1=110$ ways.

I don't think there's any smarter way to work out second and third point than either writing a program or writing out the formula behind "And so on." and doing some more or less rough estimates.

-
Well, that's what I got: rewrote equation $(1)$ in this way: $1091=10(100a_3+a_1)+(100a_2+a_0)$. $x=100a_3+a_1$, $y=100a_2+a_0$. Thus, $1091 = 10x+y. \ \ 0 \leq x \leq 109$. For every $x$ there is only one $y$, so we get $110$ ways to represent $N$. – Max Malysh Jun 3 '13 at 0:06
But what about the 2nd or the 3rd part? I can try to reformulate these questions(if needed). – Max Malysh Jun 3 '13 at 0:13
@Shemhamforasch: I elaborated a little. I hope that helps. – tomasz Jun 3 '13 at 21:30

For the first part I think we can work out analytically...

A3 can only be 1 or 0.

Case 1: a3 is 1

If a3 is 1, then necessarily a2 is 0 which leaves 10a1+a0=91. A1 can be anything from 0 to 9 which leaves a0 to be from 91,81,71.....21,11,1

10 possible results.

Case 2:a3 is 0

If a3 is 0, a2 can be anything from 1 to 10. It cannot be 0. And if you Calculate it out,( by of course keeping a1 a constant and then checking a0) if you keep a2 say 1, then 10a1+a0=991. Now a0 can never exceed 99, or actually 91, so a1 can never be smaller than 90. Similarly if you work for the rest out (actually you will find it out in the middle of the calculation only), each and every case from 1 to 10 will have 10 cases each. (first think and read patiently and visualize it and then proceed). So no. Of cases here are 100.

So total no. Of cases are 110.

I think for the second part, the answer might lie in my method above.

If here i assumed 10 cases for a1 and a0, it is only possible if 10a1 +a0 was a two digit no. (100 cases here only). Basically i mean that if n is two digit there are 100 cases which only include a1 and a0 b/w 0 and 99 and a3 and a2 0.

So if N is greater than any two digit no. then no. of cases must exceed 100.

So if the no. is just 1092, i think it probably would have same no. of cases. Proceeding like this only, you can easily tell 10 nos. like that. (1090,1091....1099). And for the second part, by my reasoning above, there are only 10 such cases.

-
If $a_1$ can be anything from $0$ to $9$, then there are $10$ possible results... I suspect your analysis of the second case has a similar flaw. – tomasz Jun 3 '13 at 17:53
Sorry and thanks @tomasz. Making the edits.... – Rohinb97 Jun 8 '13 at 20:32
Nice...@Rohinb97 – Saurabh Raje Jul 8 '13 at 14:30