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.

Let $a_1\le a_2\le\cdots\le a_6$ and $b_1\le b_2\le\cdots\le b_6$ be positive integers, not necessarily distinct, such that $a_1+a_2+\cdots+a_6<b_1+b_2+\cdots+b_6$. When the $36$ sums $a_i+b_j$ are computed, it turns out that $k$ appears $k-1$ times for $k=2,3,\cdots,7$ and $13-k$ times for $k=8,9,\cdots,12$. Find the possible values of $a_1,\cdots,a_6,b_1,\cdots,b_6$.

I'm totally clueless on how to approach this question and how to come up with the generating function. Any help is appreciated.

share|improve this question
1  
To get started on a direct approach, the smallest possible sum is $2$ that occurs once, so that forces $a_1 = b_1 = 1$. Then the sum $3$ appears twice, so either $a_2 = b_2 = 2$ or $a_2 = a_3 = 2$ or $b_2 = b_3 = 2$. –  Michael Joyce Oct 23 '13 at 14:34
    
@MichaelJoyce How should I go about it if I want to use generating functions? –  Sapphire Oct 23 '13 at 14:40
add comment

1 Answer 1

up vote 1 down vote accepted

To get you started with the generating function approach, construct generating functions for your sequences, which will be polynomials since your sequences have only finitely many terms: $$ f(z) = a_1 z + a_2 z^2 + \cdots + a_6 z^6 \\ g(z) = b_1 z + b_2 z^2 + \cdots + b_6 z^6 $$ Now you must figure out how to translate the condition on the sums $a_i + b_j$ into some condition on $f(z)g(z)$. You should be able to explicitly write down $f(z)g(z)$ as a specific polynomial with positive integer coefficients.

Now factor this polynomial into irreducibles. Any solution to your problem must correspond to a factorization into a product of two degree 6 polynomials. Use your irreducible decomposition of $f(z) g(z)$ to determine how many such factorizations are possible. Then for each one, check whether the coefficients are positive integers, (weakly) increasing, and have different total sum of all coefficients. For each such factorization, you'll be able to read off a solution to your problem. (Hint: there's no guarantee that even one such factorization is possible.)

share|improve this answer
add comment

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.