# Combination of a 4-digit number

How many 4-digit numbers ($0000-9999$; including $0000$ and $9999$) can be formed in which the sum of first two digits is equal to the sum of last two digits?

Assumption : every number is valid even if it starts with a zero.

For ex: $1230, 0211, 4233$ and so on...

-
any hint or suggestion will be helpful :) – user62947 Feb 22 '13 at 9:54

HINT: The possible sums of two digits are the integers from $0$ through $18$. There’s just one way to get a sum of $0$ or $18$. There are two ways to get a sum of $1$, $01$ and $10$, and two ways to get a sum of $17$, $89$ and $98$. It’s easy enough to work out the number of ways to get each possible sum:

$$\begin{array}{r|rr} \text{Sum}&0&1&2&3&4&5&6&7&8&9\\ \text{Sum}&18&17&16&15&14&13&12&11&10\\ \hline \text{Nr. of ways}&1&2&3&4&5&6&7&8&9&10 \end{array}$$

To get a number whose first two digits sum to $6$, say, and whose last two digits also sum to six, you must combine one of the $7$ possible pairs for the first two digits with one of the same $7$ possible pairs for the last two digits. You can do that in $7^2=49$ ways.

Can you finish the calculation from there?

-

I have to admit, that this is not really a hint. But in this case I am faster writing code, than thinking. Thus:

function howmany

ds = @(n) sum(arrayfun(@str2num, num2str(n)));
% ds = sum of digits of a number
counter = 0;
for n=0:9999
if  ds(floor(n/100)) == ds(n-floor(n/100)*100)
counter = counter+1;
end
end

disp(counter)

end


Written in Matlab, but that shouldn't be the problem. The results is the same you would get by the theoretical approach of Brian M. Scott.

-
As much as I love code, it's not as elegant as pure mathematics. – Ryan Amos Feb 22 '13 at 14:38
@RyanAmos I totally agree. But sometimes it's the only way. This is of course a little overkill. – k1next Feb 22 '13 at 14:41
Sometimes, for certain, but this is hardly one of those times, as Brian Scott's answer indicates. What's more, his method can relatively easily give you the answer for thousand-digit numbers too, which this algorithm might not have the time to do... – Steven Stadnicki Feb 22 '13 at 19:13
@StevenStadnicki yes correct. I just wanted to give a different approach, as this was my first idea. – k1next Feb 22 '13 at 20:36

The map $(a,b,c,d)\longleftrightarrow (a,b,9-c,9-d)$ puts the desired 4 digit numbers in a one-to-one correspondence with four digit numbers whose digits add up to 18. This set can be counted with "stars and bars" plus the inclusion-exclusion principle to give $${21\choose 3}-{4\choose 1}{11\choose 3}=670.$$

-

$$A_0=\{00\}$$ $$A_1=\{01,10\}$$ $$A_2=\{02,20,11\}$$ $$A_3=\{03,30,12,21\}$$ $$A_4=\{04,40,13,31,22\}$$ $$A_5=\{05,50,14,41,23,32\}$$ $$A_6=\{06,60,15,51,24,42,33\}$$ $$A_7=\{07,70,16,61,25,52,34,43\}$$ $$A_8=\{08,80,17,71,26,62,35,53,44\}$$ $$A_{9}=\{09,90,18,81,27,72,36,63,45,54\}$$ $$A_{10}=\{19,91,28,82,37,73,46,64,55\}$$ $$A_{11}=\{29,92,38,83,47,74,56,65\}$$ $$A_{12}=\{39,93,48,84,57,75,66\}$$ $$A_{13}=\{49,94,58,85,67,76\}$$ $$A_{14}=\{59,95,68,86,77\}$$ $$A_{15}=\{69,96,78,87\}$$ $$A_{16}=\{79,97,88\}$$ $$A_{17}=\{89,98\}$$ $$A_{18}=\{99\}$$ each such number is permutation with repetition of order 2 of set $A_i,i=0,1,2,...,18$ for example $$A_2=\{02,20,11\}\to 0202,0220,0211,2020,2002,2011,1102,1120,1111$$ so

$$\sum_{i=0}^{18}|A_i|^2=2(1^2+2^2+3^2+...+9^2)+10^2=$$ $$=2(1+4+9+16+25+36+49+64+81)+100=670$$

-