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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a generalization of a subproblem from a past programming competition that I had trouble with.

Given input $6$ positive integers: $$r_1, r_2, r_3, x_1, x_2, x_3 \in \mathbb{Z^+}$$ Produce as output any $6$ non-negative integers: $$\theta_1, \theta_2, \theta_3, \theta_4, \theta_5, \theta_6$$ with a maximum sum, subject to the constraints: $$\theta_1x_1 + \theta_2x_1 + \theta_3x_2 + \theta_4x_2 + \theta_5x_3 + \theta_6x_3 \le r_1 \\ \theta_1x_2 + \theta_2x_3 + \theta_3x_1 + \theta_4x_3 + \theta_5x_1 + \theta_6x_2 \le r_2 \\ \theta_1x_3 + \theta_2x_2 + \theta_3x_3 + \theta_4x_1 + \theta_5x_2 + \theta_6x_1 \le r_3. $$

share|cite|improve this question
Isn't this just a standard linear program of the form: minimize $\mathbf{1}^{T}\Theta$ subject to $X \Theta \le \mathbf{r}$ and $\Theta \ge \mathbf{0}$? (edit: why is \mathbf is so ugly in MathJax?) – user2468 Aug 17 '12 at 3:13
As the xs are constant you can generalize it to that, but is there a way to take advantage of the fact that the xs repeat in all six permutations to give a simpler solution? – Andrew Tomazos Aug 17 '12 at 3:25
I've changed algebra tag to algebra-precalculus, since we don't use algebra tag anymore, see meta for details. – Martin Sleziak Aug 17 '12 at 7:32
$r_1+r_2+r_3 \geq (x_1+x_2+x_3)(\theta_1+\theta_2+\theta_3+\theta_4+\theta_5+\theta_6)$ – Angela Richardson Aug 17 '12 at 17:20
@AngelaRichardson: Information is lost. Your equation is implied by the triple equation, however the reverse is not true. – Andrew Tomazos Aug 17 '12 at 17:32

Your Answer


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

Browse other questions tagged or ask your own question.