2 elementary number theory problems [closed]












0












$begingroup$


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 $xge 0 , yge 1, zge 2, wge 3$, and satisfies $x+y+z+w = 15.$



I would appreciate the indepth explanation to solving these problems










share|cite|improve this question











$endgroup$



closed as off-topic by Martin R, Brahadeesh, Rebellos, Saad, Cesareo Dec 14 '18 at 10:19


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Martin R, Brahadeesh, Rebellos, Saad, Cesareo

If this question can be reworded to fit the rules in the help center, please edit the question.
















  • $begingroup$
    Are these just finding one 3- or 4-tuple for each problem, all of them, or what? Finding any one solution seems easy enough: just choose 2 (for Q1) or 3 (for Q2) numbers that meet the necessary properties, find the remaining number, and, if it doesn't exist, tweak as necessary. Just glorified trial-and-error.
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:45












  • $begingroup$
    Also shouldn't Q2 be stated as $x+y+z+w=15$? (instead of $=w=15$)
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:46










  • $begingroup$
    It says find for 1. 3- tuple and for 2. 4- tuple. I will make the edit Thank you.
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:48












  • $begingroup$
    Actually it only says triplets and quadruplets not tuples unless they imply the same thing?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:50






  • 1




    $begingroup$
    "Triplet" and "3-tuple" basically mean the same thing; same for "quadruplet" and "4-tuple." Basically what I was asking, then, is "are you only tasked to find one such triplet/quadruplet". If so, the trial-and-error method I suggested is just as valid as any other. I could see something more "refined" being justified if it was finding all of the triplets/quadruplets, and I find it weird that you'd only be asked for one triplet/quadruplet in a textbook on number theory (but that might be a personal issue).
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:53
















0












$begingroup$


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 $xge 0 , yge 1, zge 2, wge 3$, and satisfies $x+y+z+w = 15.$



I would appreciate the indepth explanation to solving these problems










share|cite|improve this question











$endgroup$



closed as off-topic by Martin R, Brahadeesh, Rebellos, Saad, Cesareo Dec 14 '18 at 10:19


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Martin R, Brahadeesh, Rebellos, Saad, Cesareo

If this question can be reworded to fit the rules in the help center, please edit the question.
















  • $begingroup$
    Are these just finding one 3- or 4-tuple for each problem, all of them, or what? Finding any one solution seems easy enough: just choose 2 (for Q1) or 3 (for Q2) numbers that meet the necessary properties, find the remaining number, and, if it doesn't exist, tweak as necessary. Just glorified trial-and-error.
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:45












  • $begingroup$
    Also shouldn't Q2 be stated as $x+y+z+w=15$? (instead of $=w=15$)
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:46










  • $begingroup$
    It says find for 1. 3- tuple and for 2. 4- tuple. I will make the edit Thank you.
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:48












  • $begingroup$
    Actually it only says triplets and quadruplets not tuples unless they imply the same thing?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:50






  • 1




    $begingroup$
    "Triplet" and "3-tuple" basically mean the same thing; same for "quadruplet" and "4-tuple." Basically what I was asking, then, is "are you only tasked to find one such triplet/quadruplet". If so, the trial-and-error method I suggested is just as valid as any other. I could see something more "refined" being justified if it was finding all of the triplets/quadruplets, and I find it weird that you'd only be asked for one triplet/quadruplet in a textbook on number theory (but that might be a personal issue).
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:53














0












0








0





$begingroup$


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 $xge 0 , yge 1, zge 2, wge 3$, and satisfies $x+y+z+w = 15.$



I would appreciate the indepth explanation to solving these problems










share|cite|improve this question











$endgroup$




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 $xge 0 , yge 1, zge 2, wge 3$, and satisfies $x+y+z+w = 15.$



I would appreciate the indepth explanation to solving these problems







elementary-number-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 14 '18 at 4:50









user587054

48011




48011










asked Dec 14 '18 at 3:43









Aurora BorealisAurora Borealis

856414




856414




closed as off-topic by Martin R, Brahadeesh, Rebellos, Saad, Cesareo Dec 14 '18 at 10:19


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Martin R, Brahadeesh, Rebellos, Saad, Cesareo

If this question can be reworded to fit the rules in the help center, please edit the question.







closed as off-topic by Martin R, Brahadeesh, Rebellos, Saad, Cesareo Dec 14 '18 at 10:19


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Martin R, Brahadeesh, Rebellos, Saad, Cesareo

If this question can be reworded to fit the rules in the help center, please edit the question.












  • $begingroup$
    Are these just finding one 3- or 4-tuple for each problem, all of them, or what? Finding any one solution seems easy enough: just choose 2 (for Q1) or 3 (for Q2) numbers that meet the necessary properties, find the remaining number, and, if it doesn't exist, tweak as necessary. Just glorified trial-and-error.
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:45












  • $begingroup$
    Also shouldn't Q2 be stated as $x+y+z+w=15$? (instead of $=w=15$)
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:46










  • $begingroup$
    It says find for 1. 3- tuple and for 2. 4- tuple. I will make the edit Thank you.
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:48












  • $begingroup$
    Actually it only says triplets and quadruplets not tuples unless they imply the same thing?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:50






  • 1




    $begingroup$
    "Triplet" and "3-tuple" basically mean the same thing; same for "quadruplet" and "4-tuple." Basically what I was asking, then, is "are you only tasked to find one such triplet/quadruplet". If so, the trial-and-error method I suggested is just as valid as any other. I could see something more "refined" being justified if it was finding all of the triplets/quadruplets, and I find it weird that you'd only be asked for one triplet/quadruplet in a textbook on number theory (but that might be a personal issue).
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:53


















  • $begingroup$
    Are these just finding one 3- or 4-tuple for each problem, all of them, or what? Finding any one solution seems easy enough: just choose 2 (for Q1) or 3 (for Q2) numbers that meet the necessary properties, find the remaining number, and, if it doesn't exist, tweak as necessary. Just glorified trial-and-error.
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:45












  • $begingroup$
    Also shouldn't Q2 be stated as $x+y+z+w=15$? (instead of $=w=15$)
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:46










  • $begingroup$
    It says find for 1. 3- tuple and for 2. 4- tuple. I will make the edit Thank you.
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:48












  • $begingroup$
    Actually it only says triplets and quadruplets not tuples unless they imply the same thing?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 3:50






  • 1




    $begingroup$
    "Triplet" and "3-tuple" basically mean the same thing; same for "quadruplet" and "4-tuple." Basically what I was asking, then, is "are you only tasked to find one such triplet/quadruplet". If so, the trial-and-error method I suggested is just as valid as any other. I could see something more "refined" being justified if it was finding all of the triplets/quadruplets, and I find it weird that you'd only be asked for one triplet/quadruplet in a textbook on number theory (but that might be a personal issue).
    $endgroup$
    – Eevee Trainer
    Dec 14 '18 at 3:53
















$begingroup$
Are these just finding one 3- or 4-tuple for each problem, all of them, or what? Finding any one solution seems easy enough: just choose 2 (for Q1) or 3 (for Q2) numbers that meet the necessary properties, find the remaining number, and, if it doesn't exist, tweak as necessary. Just glorified trial-and-error.
$endgroup$
– Eevee Trainer
Dec 14 '18 at 3:45






$begingroup$
Are these just finding one 3- or 4-tuple for each problem, all of them, or what? Finding any one solution seems easy enough: just choose 2 (for Q1) or 3 (for Q2) numbers that meet the necessary properties, find the remaining number, and, if it doesn't exist, tweak as necessary. Just glorified trial-and-error.
$endgroup$
– Eevee Trainer
Dec 14 '18 at 3:45














$begingroup$
Also shouldn't Q2 be stated as $x+y+z+w=15$? (instead of $=w=15$)
$endgroup$
– Eevee Trainer
Dec 14 '18 at 3:46




$begingroup$
Also shouldn't Q2 be stated as $x+y+z+w=15$? (instead of $=w=15$)
$endgroup$
– Eevee Trainer
Dec 14 '18 at 3:46












$begingroup$
It says find for 1. 3- tuple and for 2. 4- tuple. I will make the edit Thank you.
$endgroup$
– Aurora Borealis
Dec 14 '18 at 3:48






$begingroup$
It says find for 1. 3- tuple and for 2. 4- tuple. I will make the edit Thank you.
$endgroup$
– Aurora Borealis
Dec 14 '18 at 3:48














$begingroup$
Actually it only says triplets and quadruplets not tuples unless they imply the same thing?
$endgroup$
– Aurora Borealis
Dec 14 '18 at 3:50




$begingroup$
Actually it only says triplets and quadruplets not tuples unless they imply the same thing?
$endgroup$
– Aurora Borealis
Dec 14 '18 at 3:50




1




1




$begingroup$
"Triplet" and "3-tuple" basically mean the same thing; same for "quadruplet" and "4-tuple." Basically what I was asking, then, is "are you only tasked to find one such triplet/quadruplet". If so, the trial-and-error method I suggested is just as valid as any other. I could see something more "refined" being justified if it was finding all of the triplets/quadruplets, and I find it weird that you'd only be asked for one triplet/quadruplet in a textbook on number theory (but that might be a personal issue).
$endgroup$
– Eevee Trainer
Dec 14 '18 at 3:53




$begingroup$
"Triplet" and "3-tuple" basically mean the same thing; same for "quadruplet" and "4-tuple." Basically what I was asking, then, is "are you only tasked to find one such triplet/quadruplet". If so, the trial-and-error method I suggested is just as valid as any other. I could see something more "refined" being justified if it was finding all of the triplets/quadruplets, and I find it weird that you'd only be asked for one triplet/quadruplet in a textbook on number theory (but that might be a personal issue).
$endgroup$
– Eevee Trainer
Dec 14 '18 at 3:53










2 Answers
2






active

oldest

votes


















2












$begingroup$

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_2leq59$, $t_1leq 59$, $t_2leq 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.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    You talking about the simplex algorithm?
    $endgroup$
    – AmbretteOrrisey
    Dec 14 '18 at 13:18












  • $begingroup$
    Can we solve 2) in a similar way?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 14:07










  • $begingroup$
    @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
    $endgroup$
    – YiFan
    Dec 14 '18 at 14:25










  • $begingroup$
    @AuroraBorealis Yes, you can.
    $endgroup$
    – YiFan
    Dec 14 '18 at 14:25










  • $begingroup$
    @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
    $endgroup$
    – AmbretteOrrisey
    Dec 14 '18 at 14:32





















1












$begingroup$

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$







share|cite|improve this answer











$endgroup$




















    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    2












    $begingroup$

    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_2leq59$, $t_1leq 59$, $t_2leq 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.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      You talking about the simplex algorithm?
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 13:18












    • $begingroup$
      Can we solve 2) in a similar way?
      $endgroup$
      – Aurora Borealis
      Dec 14 '18 at 14:07










    • $begingroup$
      @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @AuroraBorealis Yes, you can.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 14:32


















    2












    $begingroup$

    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_2leq59$, $t_1leq 59$, $t_2leq 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.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      You talking about the simplex algorithm?
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 13:18












    • $begingroup$
      Can we solve 2) in a similar way?
      $endgroup$
      – Aurora Borealis
      Dec 14 '18 at 14:07










    • $begingroup$
      @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @AuroraBorealis Yes, you can.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 14:32
















    2












    2








    2





    $begingroup$

    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_2leq59$, $t_1leq 59$, $t_2leq 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.






    share|cite|improve this answer









    $endgroup$



    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_2leq59$, $t_1leq 59$, $t_2leq 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.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Dec 14 '18 at 9:02









    YiFanYiFan

    3,4541425




    3,4541425












    • $begingroup$
      You talking about the simplex algorithm?
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 13:18












    • $begingroup$
      Can we solve 2) in a similar way?
      $endgroup$
      – Aurora Borealis
      Dec 14 '18 at 14:07










    • $begingroup$
      @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @AuroraBorealis Yes, you can.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 14:32




















    • $begingroup$
      You talking about the simplex algorithm?
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 13:18












    • $begingroup$
      Can we solve 2) in a similar way?
      $endgroup$
      – Aurora Borealis
      Dec 14 '18 at 14:07










    • $begingroup$
      @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @AuroraBorealis Yes, you can.
      $endgroup$
      – YiFan
      Dec 14 '18 at 14:25










    • $begingroup$
      @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
      $endgroup$
      – AmbretteOrrisey
      Dec 14 '18 at 14:32


















    $begingroup$
    You talking about the simplex algorithm?
    $endgroup$
    – AmbretteOrrisey
    Dec 14 '18 at 13:18






    $begingroup$
    You talking about the simplex algorithm?
    $endgroup$
    – AmbretteOrrisey
    Dec 14 '18 at 13:18














    $begingroup$
    Can we solve 2) in a similar way?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 14:07




    $begingroup$
    Can we solve 2) in a similar way?
    $endgroup$
    – Aurora Borealis
    Dec 14 '18 at 14:07












    $begingroup$
    @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
    $endgroup$
    – YiFan
    Dec 14 '18 at 14:25




    $begingroup$
    @AmbretteOrrisey I've never heard of that name, so maybe. I never thought this algorithm was complicated enough to deserve a name of its own.
    $endgroup$
    – YiFan
    Dec 14 '18 at 14:25












    $begingroup$
    @AuroraBorealis Yes, you can.
    $endgroup$
    – YiFan
    Dec 14 '18 at 14:25




    $begingroup$
    @AuroraBorealis Yes, you can.
    $endgroup$
    – YiFan
    Dec 14 '18 at 14:25












    $begingroup$
    @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
    $endgroup$
    – AmbretteOrrisey
    Dec 14 '18 at 14:32






    $begingroup$
    @YiFan -- actually ... no it's not the simplex algorithm - that's about optimising problems comprising inequalities of this kind by finding the point at which a hyperplane touches a simplex. I was just browsing & responding a tad over-hastily. I'm not recommending particularly that you go & study the algorithm if it's not in your way anyway ... but if you were to do so you would see the connection.
    $endgroup$
    – AmbretteOrrisey
    Dec 14 '18 at 14:32













    1












    $begingroup$

    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$







    share|cite|improve this answer











    $endgroup$


















      1












      $begingroup$

      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$







      share|cite|improve this answer











      $endgroup$
















        1












        1








        1





        $begingroup$

        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$







        share|cite|improve this answer











        $endgroup$



        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$








        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 14 '18 at 14:00

























        answered Dec 14 '18 at 13:14









        SAEED_ABBSAEED_ABB

        112




        112















            Popular posts from this blog

            Ellipse (mathématiques)

            Quarter-circle Tiles

            Mont Emei