So going back to my old number theory book by I. Niven, An introduction to the theory on numbers, I saw these problems:
Question 1: Find the triplets of number $(x,y,z)$ such that $x+y+z=119,$ and none exceed $59?$
Question 2: Find four integers $(x,y,z,w)$, such that they have the property $x\ge 0 , y\ge 1, z\ge 2, w\ge 3$, and satisfies $x+y+z+w = 15.$
I would appreciate the indepth explanation to solving these problems
On
you can model such these equations like this:
first Q2)
suppose we have 15 identical balls and want to put them in 4 different baskets labeled as x, y, z, w such that basket y must has at least 1 ball inside it, basket z must has at least 2 balls inside it and basket w must has 3 balls inside it.
so we initially satisfy these criterias by just putting 1, 2 and 3 balls in baskets y, z and w respectively.
now we have 15-(1+2+3)=9 balls left with 3 basket which have no specific criterias: x + y' + z' + w' = 9
now if we put 3 delimiters between 9 balls to put them into 4 baskets equivalently: sections 1, 2, 3 and 4 corresponds to baskets x, y, z and w respectively.
one possible division is as follows: "{} | {OOO} | {} | {OOOOOO}" ("O" represents a ball and "|" represents a delimiter). its corresponding answer is (x, y', z', w') = (0, 3, 0, 6) that satisfies the equation x + y' + z' + w' = 9. so (x, y, z, w) = (0, 3+1, 0+2, 6+3) is a valid answer for main equation x + y + z + w = 15.
so the problem is to find all the linear permutations of 9 identical balls and 3 identical delimiters. and finally here is the number of valid (x, y, z, w) answers :
$\frac{(9+3)!}{9!3!} = \frac{{12}\times{11}\times{10}}{6} = 220$
Q1)
the problem is to find the number of (x, y, z) answers that satisfy the following equation:
$D \sim [{x + y + z = 119; {0}\leq{x}\leq{59}, {0}\leq{y}\leq{59}, {0}\leq{z}\leq{59}}]$
now let:
$I \sim [{x + y + z = 119; {0}\leq{x}, {0}\leq{y}, {0}\leq{z}}]$
$I_1 \sim [{x + y + z = 119; {60}\leq{x}, {0}\leq{y}, {0}\leq{z}}]$
$I_2 \sim [{x + y + z = 119; {0}\leq{x}, {60}\leq{y}, {0}\leq{z}}]$
$I_3 \sim [{x + y + z = 119; {0}\leq{x}, {0}\leq{y}, {60}\leq{z}}]$
by inclusion-exclusion-identity we have:
$D = {\bar{I_1}}\cap{\bar{I_2}}\cap{\bar{I_3}} = \overline{({I_1}\cup{I_2}\cup{I_3})} = I - (I_1 + I_2 + I_3 - {I_1} \cap{I_2} - {I_1}\cap{I_3} - {I_2}\cap{I_3} + {I_1}\cap{I_2}\cap{I_3})$
also:
${I_1}\cap{I_2} \sim [{x + y + z = 119; {60}\leq{x}, {60}\leq{y}, {0}\leq{z}}] \rightarrow unsatisfiable$
${I_1}\cap{I_3} \sim [{x + y + z = 119; {60}\leq{x}, {0}\leq{y}, {60}\leq{z}}] \rightarrow unsatisfiable$
${I_2}\cap{I_3} \sim [{x + y + z = 119; {0}\leq{x}, {60}\leq{y}, {60}\leq{z}}] \rightarrow unsatisfiable$
${I_1}\cap{I_2}\cap{I_3} \sim [{x + y + z = 119; {60}\leq{x}, {60}\leq{y}, {60}\leq{z}}] \rightarrow unsatisfiable$
so the answer is:
$D = \frac{(119+2)!}{119!2!} - {3}\times{\frac{(119-60+2)!}{(119-60)!2!}} + {3}\times{0} - 0 = \frac{{121}\times{120}}{2} - {3}\times{\frac{{61}\times{60}}{2}} = 1770$
These are linear equations for which there is an established algorithm to solve, in terms of paramatrisations. I'll do the first question; see if you can generalise the idea to the second. Recall that solving a linear equation in two variables over $\mathbb Z$ is done like this: if $ax+by=c$, then find a particular solution $(x_0,y_0)$. Then all the solutions are given by $x=x_0-bt$, $y=y_o+at$, where $t$ ranges over all integral values. (Can you prove this?) Now let's move on to the three-variable case.
Set $u+v=k$. We have the simultaneous equations $$\begin{cases}u+v=k,\\k+w=119.\end{cases}$$ If we treat $k$ like a constant in the first equation we obtain the paramatrisation $u=k-t_1$, $v=t_1$. Treating $k$ like a variable in the second, we have $k=119-t_2$, $w=t_2$. Now, $u=k-t_1=119-t_1-t_2$. Hence, all the possible integer solutions are given by $(u,v,w)=(119-t_1-t_2,t_1,t_2)$. But none of the three variables exceed $59$, so we have the bounds $119-t_1-t_2\leq59$, $t_1\leq 59$, $t_2\leq 59$. In other words, $t_1,t_2$ are any two integers so that each is not exceeding $59$ and their sum is at least $60$. This provides a complete paramatrisation and hence solution to the problem.