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.

  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 23, 2013 at 14:34
  • $\begingroup$ @MichaelJoyce How should I go about it if I want to use generating functions? $\endgroup$
    – Sapphire
    Oct 23, 2013 at 14:40

1 Answer 1


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.)


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.