4
$\begingroup$

What kind of approach can be used to solve this specific problem? An easy one if possible.

I thought about the Inclusion-Exclusion Principle; I think using generating functions will be more difficult.

Given that the variables $x_i$ are natural numbers.

Find how many solutions exist for the equation:

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 24$$

when given

$$x_1 + x_2 + x_3 > x_4 + x_5 + x_6$$

$\endgroup$
  • $\begingroup$ I think this needs clarification. Are you assuming the $x_i$ are in some particular order? Non-ascending, maybe, or non-descending? Have you looked at the same problem for, smaller numbers than 24? $\endgroup$ – lulu Jul 7 '15 at 18:45
  • $\begingroup$ Also, are they positive integers or nonnegative integers? $\endgroup$ – Ashkay Jul 7 '15 at 18:46
  • $\begingroup$ True. I assumed they were nonnegative integers but I frequently assume things incorrectly. $\endgroup$ – lulu Jul 7 '15 at 18:46
  • $\begingroup$ I edited. non-negative $\endgroup$ – idan di Jul 7 '15 at 18:56
13
$\begingroup$

Outline: Let $A$ be the number of solutions (in non-negative integers) with $x_1+x_2+x_3\gt x_4+x_5+x_6$. Let $B$ be the number of solutions with $x_1+x_2+x_3\lt x_4+x_5+x_6$. And let $T$ be the number of solutions with equality.

By symmetry $A=B$. We know the total number $N$ of solutions with no restriction. So $2A+T=N$ and therefore $A=\frac{N-T}{2}$.

Now we only need $T$. This is $W^2$, where $W$ is the number of solutions of $y_1+y_2+y_3=12$.

$\endgroup$
  • $\begingroup$ wow, thanks. the speed you answered it . I thought its a very hard question. maybe my foundations not that strong $\endgroup$ – idan di Jul 7 '15 at 19:01
  • 2
    $\begingroup$ You are welcome. Symmetry is our friend. $\endgroup$ – André Nicolas Jul 7 '15 at 19:35
  • $\begingroup$ (Should C be T?) $\endgroup$ – user84413 Jul 7 '15 at 22:30
  • $\begingroup$ Yes, thank you, fixed. $\endgroup$ – André Nicolas Jul 7 '15 at 22:48
5
$\begingroup$

Assuming that they are nonnegative integers:

The number of solutions to $x_1 + x_2 + x_3 = k$ is $\dbinom{k+2}{2}$ by the Stars and Bars approach.

Therefore, we can add up the number of ways for every combination of $k$ that works - if the first three add to $k$, the second three add to $24-k$. In addition, we let $k$ go from $13$ to $24$, so that the inequality holds.

Thus, the answer is $$ \sum_{k=13}^{24} \dbinom{k+2}{2} \cdot \dbinom{26 - k}{2} $$

EDIT: The other answer is much better! But I'll leave this here.

$\endgroup$
  • 1
    $\begingroup$ I do not agree that the other answer (mine) is better. They are different. Your procedure can be easily generalized, with sum of the first $k$ less than the sum of the last $l$.. Mine only deals with sum of first $k$ greater than the sum of the last $k$. $\endgroup$ – André Nicolas Jul 7 '15 at 20:02
  • 1
    $\begingroup$ Haha, I come from a math contest background, so I always try to find ways to make the calculations as simple as possible. With problems like this, it's always best to exploit any symmetries. $\endgroup$ – Ashkay Jul 7 '15 at 20:06
  • 1
    $\begingroup$ I also have a contest background, but for the last many years on the other side of the game, making up problems, marking. $\endgroup$ – André Nicolas Jul 7 '15 at 20:12
  • $\begingroup$ Ooh, that's awesome. What contests do you write for? $\endgroup$ – Ashkay Jul 7 '15 at 20:15
  • $\begingroup$ I should avoid specifics. Never IMO, but a national contest, an international one, and a regional much lower level one. $\endgroup$ – André Nicolas Jul 7 '15 at 20:20

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.