# How many combinations can you find?

I got a interesting question from my boss today.

Imagine you have:

0 1 2 3 4 5 6 7 8 9

and beneath these numbers I have to place 10 numbers and if I place number 6 beneath 0 I must have six zeros placed out. Let me give an example for one combination that I have found.

0 1 2 3 4 5 6 7 8 9

6 2 1 0 0 0 1 0 0 0

I have six zeros and two ones and a number two.

I'm wondering if there is some way to find all combinations that satisfy these conditions. What I believe I have found is that:

A = [0 1 2 3 4 5 6 7 8 9]

I = [1 1 1 1 1 1 1 1 1 1]

X = [x0 x1 x2 x3 x4 x5 x6 x7 x8 x9]

X*A'= X*I'= 10

Any help would be appreciated as, evidently, my bonus depends on a solution :S.

-

You must have zeros under at least four of $5,6,7,8,9$, (otherwise the sum exceeds $10$) so the number under $0$ is at least $4$. Now the total of all the numbers below something besides zero is at most six, so you must have zeros below at least six of $3,4,5,6,7,8,9$. That means the number under zero is at least six. If there are six zeros, the other four must come from $2+1+1$ and that is the solution you have. If there are seven zeros, the other three must come from $2+1$, but you don't have two of anything. $8$ and $9$ zeros fail similarly. You have the only solution.
That's a very neat reasoning. I wonder if it can be generalised to other sizes. For example, all sizes up to $[0\, 1\, 2]$ don't have solutions at all. – TZakrevskiy Dec 10 '13 at 17:09
Your solution can be generalized. Given the range $[0,n]$ you would have $n-3\ 0$'s, $2\ 1$'s, $1\ 2$ and $1\ n-3$. This works for $n \gt 5$ I think this logic can show there are no more, but haven't checked it. For $[0,3]$ there is $2020$ as a special case. – Ross Millikan Dec 10 '13 at 17:16