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.

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.

share|improve this question
1  
A solution would involve these numbers, I reckon. –  J. M. Nov 7 '11 at 12:41
    
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. –  Eisen Nov 7 '11 at 13:04
    
It's more combinatorics proper than graph theory, I'd say... –  J. M. Nov 7 '11 at 13:10

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Wolfram says this is the answer: wolframalpha.com/input/… which is different from the official one. –  Eisen Nov 7 '11 at 14:43
    
And the official answer 30,787 is correct -- my computer just counted them all. –  TonyK Nov 7 '11 at 14:51
    
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 ;) –  N. S. Nov 7 '11 at 14:56
    
Thank you very much.Your approach seemed quite nice. –  Eisen Nov 7 '11 at 15:23
    
Well the calculation at the end can clearly be done, but it is too messy to really do by hand.... –  N. S. Nov 7 '11 at 15:37

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

share|improve this answer
    
I think you mean $(101-{5\over2}y)(y+1)$, not $(101-{5\over2})(y+1)$ (and this occurs twice). –  TonyK Nov 8 '11 at 10:08
    
@TonyK: Thank you. I have corrected this. –  Christian Blatter Nov 10 '11 at 20:01

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.