4
$\begingroup$

Can we find the number of ordered triples $(x,y,z)$ of non-negative integers satisfying (i) $x \leq y \leq z$ (ii) $x + y + z \leq 100$? Source:Regional Mathematics Olympiad India (2003) Thank you.I have an ugly solution.But I am hoping for some insightful/elegant solutions.

  • 1
    A solution would involve [these numbers](http://oeis.org/A001399), I reckon.2011-11-07
  • 0
    I do not have any background in graph theory.I'd imagine the solution to my question does not involve programming as it is taken from a mathematical olympiad.2011-11-07
  • 0
    It's more combinatorics proper than graph theory, I'd say...2011-11-07

2 Answers 2

4

Note that $0 \leq x \leq 33$, since $3x \leq x+y+z \leq 100$.

Now fix an $0 \leq x \leq 33$.

Subtract $3x$ then we get

$$(y-x)+(z-x) \leq 100-3x \,.$$

Denote $a:= y-x ,\;, b := z-x$. The $0 \leq a \leq b$ and $a+b \leq 100-3x$.

Do the same again, but split it in two:

If $x$ even then $0 \leq a \leq \frac{100-3x}{2}$ and $0 \leq (b-a) \leq 100-3x-2a$.

In this case we have $0 \leq x \leq 33, x$ even ; $0 \leq a \leq \frac{100-3x}{2}$ and $0 \leq (b-a) \leq 100-3x-2a$.

If $x$ odd then $0 \leq a \leq \frac{99-3x}{2}$ and $0 \leq (b-a) \leq 100-3x-2a$.

In this case we have $0 \leq x \leq 33, x$ even ; $0 \leq a \leq \frac{99-3x}{2}$ and $0 \leq (b-a) \leq 100-3x-2a$.

Note that in both cases, the tripple $a,b-a,x$ uniquely determines $x \leq y \leq z$.

Thus we have:

$$ \left[ \sum_{k=0}^{16} \sum_{a=0}^{\frac{100-6k}{2}} 100-6k-2a+1 \right]+\left[\sum_{k=0}^{16} \sum_{a=0}^{\frac{99-3(2k+1)}{2}} 100-6k-3-2a+1 \right] \,.$$

Edit The $+1$ was originary missing in the bracket, there are $100-3x-2a+1$ choices $0 \leq (b-a) \leq 100-3x-2a$.

Now each sum can be calculated.

*Second edit: * Here is a formal part calculation for the formula:

$$\left[ \sum_{k=0}^{16} \sum_{a=0}^{\frac{100-6k}{2}} 100-6k-2a+1 \right]= \sum_{k=0}^{16} \frac{100-6k}{2}\cdot (100-6k+1) - 2 \cdot\frac{\frac{100-6k}{2}(\frac{100-6k}{2})}{2} \,$$

$$\sum_{k=0}^{16} \frac{100-6k}{2}\cdot (100-6k+1 -(\frac{100-6k}{2}+1))=\frac{1}{4}\sum_{k=0}^{16}(100-6k)^2 $$

This can easely be calculated, and the second term leads to a similar calculation.

  • 0
    Wolfram says this is the answer: http://www.wolframalpha.com/input/?i=%5B%5Csum_%7Bk%3D0%7D%5E%7B16%7D+%5Csum_%7Ba%3D0%7D%5E%7B%5Cfrac%7B100-6k%7D%7B2%7D%7D+%28100-6k-2a%29%5D+%2B%5B%5Csum_%7Bk%3D0%7D%5E%7B16%7D+%5Csum_%7Ba%3D0%7D%5E%7B%5Cfrac%7B99-3%282k%2B1%29%7D%7B2%7D%7D+%28100-6k-3-2a%29+%5D which is different from the official one.2011-11-07
  • 0
    And the official answer 30,787 is correct -- my computer just counted them all.2011-11-07
  • 0
    I did a silly mistake, will fix it in a moment... Forgot that my counting starts at $0$ not at $1$ :)... Now the formula leads to the right answer ;)2011-11-07
  • 0
    Thank you very much.Your approach seemed quite nice.2011-11-07
  • 0
    Well the calculation at the end can clearly be done, but it is too messy to really do by hand....2011-11-07
3

Take $y$ as "outermost" variable; its range is $0\leq y\leq50$. Given $y$ we have to count the number of lattice points in the set $$S:=\bigl\{(x,z)\ \bigm|\ x\leq y,\ z\geq y,\ x+z\leq 100-y\bigr\}\ .$$

When $3y<100$ this set is a trapezoid containing $y+1$ lattice points on its lower horizontal edge. Its left vertical edge contains $101-2y$ lattice points and its right vertical edge contains $101-3y$ lattice points. Therefore in this case we have a total of $(101-{5\over2}y)(y+1)$ lattice points in $S$.

When $3y>100$ then $S$ is a triangle with $101-2y$ lattice points on its lower horizontal edge and $101-2y$ lattice points on its left vertical edge. Therefore in this case we have a total of $(51-y)(101-2y)$ lattice points in $S$.

It follows that the overall total $N$ of triples of the described kind is given by $$N\ =\sum_{y=0}^{33} (101-{5\over2}y)(y+1)\ +\ \sum_{y=34}^{50} (51-y)(101-2y)\ ,$$ which Mathematica computes to $30 787$.

  • 0
    I think you mean $(101-{5\over2}y)(y+1)$, not $(101-{5\over2})(y+1)$ (and this occurs twice).2011-11-08
  • 0
    @TonyK: Thank you. I have corrected this.2011-11-10