5
$\begingroup$

Let $ N$ be the number of ways to write $ 2010$ in the form $ 2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $ a_i$'s are integers, and $ 0 \le a_i \le 99$. An example of such a representation is $ 1\cdot10^3 + 3\cdot10^2 + 67\cdot10^1 + 40\cdot10^0$. Find $ N$.

I picked the biggest $a_1$ so: $a_1 = 2$, there are only two ways to form $2010$.

Take $a_1 = 1$ now. This opens up to a lot of possibilities.

Specific Casework should work:

Cases 1-1: $a_2 = 10$, then possibilities are: $a_1 = 1, a_0 = 0$ or $a_1 = 0, a_0 = 10$

Actually, I think a number-theoretic way is easier.

But still.

Case 1: $a_1 = 1$ then we must solve:

$100x + 10y + z = 1010$.

Since $0 \le x \le 10$, we can casework $x$ so that:

Case 1-1:$x = 0$. So that:

$10y + z = 1010 \implies z \equiv 0 \pmod{10}, z = 10k$ and $y = 101 - k$.

Hence, $(0, 101 - k, 10k)$. $\min{k} = 0 $ and we need to find the max of $k$. We must have, $101 - k \le 99$ and $10k \le 99$. This suggests, $k \le 9$.

Cases 1-2: $x=1$. So that:

$10y + z = 910 \implies z \equiv 0 \pmod{10}$ Again, $z = 10k$ and $y = 91 - k$. Giving a set of $(1, 91 - k, 10k)$.Here again, $\min{k} = 0$ and $10k \le 99$ so $k \le 9$.

I am conjecturing that since we are always increasing $x$ values, the value on the RHS will always be divisible by $10$.

$x = 9$ so that:

$10y + z = 110 \implies z = 10k$ and $y = 11 - k$, which again there are $9$ values.

Except if $x=10$ then there is: $10y + z = 10$ then $z = 10k$ and $y = 1 - k$. Then $k$ must be $1$.

So there are: $10(9) + 1 + 2 = 93$ solutions total.

This is just an attempt!

Bump: anybody have anything?

$\endgroup$
5
$\begingroup$

The generating function for these representations is

$$ \frac{x^{100\cdot1000}-1}{x^{1000}-1}\cdot\frac{x^{100\cdot100}-1}{x^{100}-1}\cdot\frac{x^{100\cdot10}-1}{x^{10}-1}\cdot\frac{x^{100}-1}{x-1}=\frac{x^{100000}-1}{x^{10}-1}\cdot\frac{x^{10000}-1}{x-1}\;, $$

which is also the generating function for representations of the form $b_1\cdot10+b_0$ with $0\le b_i\le9999$. Since this latter restriction is irrelevant for representations of $2010$, we are simply looking for the number of ways to represent $2010$ by tens and ones. We can have anything from $0$ to $201$ tens, so the number of such representations is $202$.

In response to Calvin Lin's answer: The cancellation in the generating functions corresponds to a bijection between the two forms of representation, with $b_1=100a_3+a_1$ and $b_0=100a_2+a_0$.

$\endgroup$
11
  • 1
    $\begingroup$ Interesting approach! $\endgroup$
    – Brian Tung
    Sep 2 '15 at 20:33
  • $\begingroup$ (+1) I am particularly interested here, how did you find that generating function? $\endgroup$
    – Amad27
    Sep 3 '15 at 16:13
  • $\begingroup$ @Amad27: The generating function for representations by thousands is $$1+x^{1000}+x^{2\cdot1000}+\cdots=\frac1{1-x^{1000}}\;.$$ If there is a limitation that we can only use up to $99$ thousands, we have to truncate the generating function: $$1+x^{1000}+x^{2\cdot1000}+\cdots+x^{99\cdot1000}=\frac{1-x^{100\cdot1000}}{1-x^{1000}}\;.$$ See e.g. en.wikipedia.org/wiki/Geometric_progression#Derivation. $\endgroup$
    – joriki
    Sep 3 '15 at 16:18
  • $\begingroup$ Yes, but why are we using the "thousands?" $\endgroup$
    – Amad27
    Sep 3 '15 at 16:32
  • $\begingroup$ @Amad27: Because the problem says so: "write $2010$ in the form $2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$" -- i.e., represent $2010$ in terms of thousands, hundreds, tens and ones. $\endgroup$
    – joriki
    Sep 3 '15 at 16:34
2
$\begingroup$

It's easier to start from the other end. We observe first that $a_0$ can be any multiple of $10$ from $0$ through $90$. There are, of course, ten such values.

Then $a_1$ can be any one- or two-digit value equivalent to $11-(a_0/10) \bmod 10$. Again, there are ten such values.

The choices of $a_2$ are much more limited by the fact that the target sum is only $2010$. In which cases are there two different values? In which cases are there three?

Once $a_0, a_1, a_2$ have been decided, there is only one usable value of $a_3$.

$\endgroup$
2
$\begingroup$

Here's the bijection approach, which is hinted at by Joriki's solution.

Let $a_i = 10 b_i + c_i$, where $ 0 \leq c_i \leq 9$, $ 0 \leq b_i \leq 9$.

Then, we have

$$2010 = 10 (1000b_3 + 100 b_2 + 10b_1 + b_0) + ( 1000 c_3 + 100 c_2 + 10 c_1 + c_0)$$

Thus, given any representation of $2010 = 10 B + C $, there is a unique corresponding $b_i, c_i$ (clearly the digits of B and C) that we can create, and vice versa. This establishes the bijection. Hence, the answer is 202.

$\endgroup$
8
  • $\begingroup$ Nice interpretatino of Joriki's approach! $\endgroup$
    – simonzack
    Sep 6 '15 at 21:42
  • $\begingroup$ The bijection that I had in mind was $2010=10(100a_3+a_1)+(100a_2+a_0)$. I think that corresponds more closely with the cancellation of factors in the generating functions? $\endgroup$
    – joriki
    Sep 7 '15 at 6:16
  • $\begingroup$ @joriki, the coefficient $A(k)$ is the number of ways. So if for example I am finding how many ways to use the $1000$ it would be $A(1000)x^{1000} = 3x^{1000}$ right ? But you have something way different? $\endgroup$
    – Amad27
    Sep 7 '15 at 9:26
  • $\begingroup$ @Amad27: Again, unfortunately I don't understand your question. Generally speaking, you've been asking a lot of questions in comments recently. Questions in comments are OK, but should usually only be asked if it seems likely that others might have the same question and thus the comment is likely to help clarify the answer. Most of your comments, as far as I could tell, seemed to be based on a misunderstanding or lack of understanding on your part and should preferably have been asked as separate questions so as not to clutter the comments. $\endgroup$
    – joriki
    Sep 7 '15 at 10:27
  • $\begingroup$ @joriki, I know how to use generating functions, but I just don't understand what you were doing $\endgroup$
    – Amad27
    Sep 7 '15 at 11:57
1
$\begingroup$

In short we have to calculate the number of integer solutions of the Diophantine equation $$1000x+100y+10z+w=2010$$ with the conditions $0\leq x,y,z,w \leq 99$. We have $0\leq x\leq 2$ which gives the three equations $$(1)……100y+10z+w=2010$$ $$(2)……100y+10z+w=1010$$ $$(3)……100y+10z+w=10$$ The equation (3) gives just two solutions $(2,0,1,0)$ and $(2,0,0,10)$.

It remains to compute solutions of (1) and (2). We have for $w$ only ten possible values $w=0,10,20,30,40,50,60,70,80,90$ which gives for (1) the ten equations $ (1’)……100y+10z=2010,2000,1990,1980,1970,1960,1950,1940,1930,1920$ that is $$(1’)……10y+z=201,200,199,198,197,196,195,194,193,192$$ And for (2) the ten equations $(2’)……100y+10z=1010,1000,990,980,970,960,950,940,930,920$ that is $$(2’)………10y+z=101,100,99,98,97,96,95,94,93,92$$

The first equation of (1’), $10y+z=201$, gives for $z$ only the ten possible values $1,11,21,31,41,51,61,71,81,91$ with corresponding unique values of y respectively equal to $20,19,18,17,16,15,14,13,12,11$ so ten solutions.

The second one,$10y+z=200$ makes $z=0,10,20,30,40,50,60,70,80,90$ which gives for $y$ the values $20,19,18,17,16,15,14,13,12,11$ so ten solutions.

Pursuing, $10y+z=199$ makes $z=9,19,29,……….,99$ which give ten solutions and so are for the remaining values $198,197,196,195,194,193,192$.

Thus the ten equations (1’) give one hundred solutions. The same procedure goes for ten equations (2’) which give then one hundred solutions.

Finally we have $2+100+100=202$ solutions.

$\endgroup$
0
0
$\begingroup$

Here's a solution that's not particularly elegant but gives the right answer (checked by brute force).

First express each coefficient uniquely as $b_i\cdot 10 + a_i$.

$2010 = b_3 \cdot 10^4 + a_3 \cdot 10^3 + b_2 \cdot 10^3 + a_2 \cdot 10^2 + b_1 \cdot 10^2 + a_1 \cdot 10 + b_0 \cdot 10 + a_0$.

We must have $b_3 = 0, a_0 = 0$, so

$201 = (a_3 + b_2) \cdot 10^2 + (a_2 + b_1) \cdot 10^1 + (a_1 + b_0)$.

Each coefficient is in $0, \ldots, 18$.

If $a_3 + b_2 = 1$, then $101 = (a_2 + b_1) \cdot 10^1 + (a_1 + b_0)$. We have $a_2 + b_1 = 9, a_1 + b_0 = 11$ or $a_2 + b_1 = 10, a_1 + b_0 = 1$, this gives $2 \cdot (10 \cdot 8 + 9 \cdot 2) = 196$ solutions.

If $a_3 + b_2 = 2$, then $1 = (a_2 + b_1) \cdot 10^1 + (a_1 + b_0)$. We have $a_2 + b_1 = 0, a_1 + b_0 = 1$, this gives $3 \cdot 2 = 6$ solutions.

So together we have 202 solutions.

$\endgroup$
3
  • $\begingroup$ I get the same result that you do, so I think we're on the right track! $\endgroup$
    – Brian Tung
    Sep 2 '15 at 20:25
  • $\begingroup$ Good to know you got the same result! $\endgroup$
    – simonzack
    Sep 2 '15 at 20:28
  • $\begingroup$ On the right track at the start, but your cases become complicated. See my solution. $\endgroup$
    – Calvin Lin
    Sep 6 '15 at 18:02

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.