Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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