Please help me solve this problem!!

For students of class 6-8 (age 12 to 14)
M F Ruhan
Posts:13
Joined:Fri Apr 02, 2021 1:42 pm
Contact:
Please help me solve this problem!!

Unread post by M F Ruhan » Mon Apr 05, 2021 2:18 pm

a + b + c + d = 2021. How many possible solutions of (a, b ,c, d) are there if a , b , c , d are 4 different positive integers ? Position of (a , b, c , d) doesn't matter . Ex: (a ,c , b ,d) = (d, a, b, c).

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Please help me solve this problem!!

Unread post by Anindya Biswas » Tue Apr 06, 2021 12:54 am

Well, I first recognize that we can give an order on $a,b,c,d$
WLOG, let's assume $a\leq b-1\leq c-2 \leq d-3$
So, we've got $4a\leq a+(b-1)+(c-2)+(d-3)\leq 2015$
$\Rightarrow a\leq 503$.
Maybe we have to experiment a lot but this is not trivial at all.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Please help me solve this problem!!

Unread post by Anindya Biswas » Tue Apr 06, 2021 2:48 am

Well, here's the solution:
Number of tuples $(a,b,c,d)$ is $2020\choose 3$ [Stars and bars theorem maybe]
Remember, while doing this calculation, we have some tuples where they are not pairwise distinct and also here, the positions are important.
Now let's calculate the number of tuples where at least $2$ of them are equal.
Observe that since $2021$ is not divisible by $4$, we have no tuple for which $a=b=c=d$.
  1. Let's first focus on tuples where exactly $3$ of them are equal.
    WLOG, assume that $b=c=d=m$
    $\therefore 3m+a=2021$
    This has positive solutions when $1\leq m\leq 673$
    So, this equation has $673$ solutions.
    However, we have $4$ choices to choose $3$ numbers to be equal. And each of them gives $673$ non-intersecting tuples.
    So, number of tuples where exactly $3$ of the numbers are equal is $4\times673$. For convenience, we will call this tuples the $\text{3-tuples}$.
  2. Now let's count the number of tuples where $a=b=m$. That means, we have to count the number of tuples of the form $(m,m,c,d)$ or, equivalently, number of solutions to the equation $2m+c+d=2021$. We can substitute $m=1,2,3,\dots,1009$ and count each of them and take their sum. We get, $2+4+6+\dots+2018=1019090$.
    However, there are ${4\choose2}=6$ ways to choose $2$ variables to be equal.
    Another important thing to realize is the tuple $(m,m,m,d)$ is counted $3$ times while counting $(m,m,c,d), (m,b,m,d), (a,m,m,d)$. Thus each $\text{3-tuples}$ will be counted $3$ times. So, we have to subtract twice the number of $\text{3-tuples}$ to get the number of tuples where at least two of the variables are equal.
So, the number of tuples where at least two of the variables are equal is, $6\times1019090-2\times4\times673$
$\therefore$ The number of tuples where every variable is pairwise distinct is ${2020\choose3}-6\times1019090+2\times4\times673$.
Now since we don't care about permutation, we have to divide by $4!$ since every combination is counted $4!$ times.
Our final answer is, \[\boxed{\frac{{2020\choose3}-6\times1019090+2\times4\times673}{4!}=56899416}\]
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

M F Ruhan
Posts:13
Joined:Fri Apr 02, 2021 1:42 pm
Contact:

Re: Please help me solve this problem!!

Unread post by M F Ruhan » Tue Apr 06, 2021 10:33 am

Anindya Biswas wrote:
Tue Apr 06, 2021 2:48 am
Well, here's the solution:
Number of tuples $(a,b,c,d)$ is $2020\choose 3$ [Stars and bars theorem maybe]
Remember, while doing this calculation, we have some tuples where they are not pairwise distinct and also here, the positions are important.
Now let's calculate the number of tuples where at least $2$ of them are equal.
Observe that since $2021$ is not divisible by $4$, we have no tuple for which $a=b=c=d$.
  1. Let's first focus on tuples where exactly $3$ of them are equal.
    WLOG, assume that $b=c=d=m$
    $\therefore 3m+a=2021$
    This has positive solutions when $1\leq m\leq 673$
    So, this equation has $673$ solutions.
    However, we have $4$ choices to choose $3$ numbers to be equal. And each of them gives $673$ non-intersecting tuples.
    So, number of tuples where exactly $3$ of the numbers are equal is $4\times673$. For convenience, we will call this tuples the $\text{3-tuples}$.
  2. Now let's count the number of tuples where $a=b=m$. That means, we have to count the number of tuples of the form $(m,m,c,d)$ or, equivalently, number of solutions to the equation $2m+c+d=2021$. We can substitute $m=1,2,3,\dots,1009$ and count each of them and take their sum. We get, $2+4+6+\dots+2018=1019090$.
    However, there are ${4\choose2}=6$ ways to choose $2$ variables to be equal.
    Another important thing to realize is the tuple $(m,m,m,d)$ is counted $3$ times while counting $(m,m,c,d), (m,b,m,d), (a,m,m,d)$. Thus each $\text{3-tuples}$ will be counted $3$ times. So, we have to subtract twice the number of $\text{3-tuples}$ to get the number of tuples where at least two of the variables are equal.
So, the number of tuples where at least two of the variables are equal is, $6\times1019090-2\times4\times673$
$\therefore$ The number of tuples where every variable is pairwise distinct is ${2020\choose3}-6\times1019090+2\times4\times673$.
Now since we don't care about permutation, we have to divide by $4!$ since every combination is counted $4!$ times.
Our final answer is, \[\boxed{\frac{{2020\choose3}-6\times1019090+2\times4\times673}{4!}=56899416}\]
In the following question it has been asked that a,b,c,d are four different integers . So I'm not very sure about counting tuples like {a,m,m,m} or {a,m,m,d} . I think it would be better to assume {a,b,c,d} is a set. But anyway, the solution you have shown is a very interesting one. So thank you very much for replying :)

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Please help me solve this problem!!

Unread post by Mehrab4226 » Tue Apr 06, 2021 11:10 am

M F Ruhan wrote:
Tue Apr 06, 2021 10:33 am
Anindya Biswas wrote:
Tue Apr 06, 2021 2:48 am
Well, here's the solution:
Number of tuples $(a,b,c,d)$ is $2020\choose 3$ [Stars and bars theorem maybe]
Remember, while doing this calculation, we have some tuples where they are not pairwise distinct and also here, the positions are important.
Now let's calculate the number of tuples where at least $2$ of them are equal.
Observe that since $2021$ is not divisible by $4$, we have no tuple for which $a=b=c=d$.
  1. Let's first focus on tuples where exactly $3$ of them are equal.
    WLOG, assume that $b=c=d=m$
    $\therefore 3m+a=2021$
    This has positive solutions when $1\leq m\leq 673$
    So, this equation has $673$ solutions.
    However, we have $4$ choices to choose $3$ numbers to be equal. And each of them gives $673$ non-intersecting tuples.
    So, number of tuples where exactly $3$ of the numbers are equal is $4\times673$. For convenience, we will call this tuples the $\text{3-tuples}$.
  2. Now let's count the number of tuples where $a=b=m$. That means, we have to count the number of tuples of the form $(m,m,c,d)$ or, equivalently, number of solutions to the equation $2m+c+d=2021$. We can substitute $m=1,2,3,\dots,1009$ and count each of them and take their sum. We get, $2+4+6+\dots+2018=1019090$.
    However, there are ${4\choose2}=6$ ways to choose $2$ variables to be equal.
    Another important thing to realize is the tuple $(m,m,m,d)$ is counted $3$ times while counting $(m,m,c,d), (m,b,m,d), (a,m,m,d)$. Thus each $\text{3-tuples}$ will be counted $3$ times. So, we have to subtract twice the number of $\text{3-tuples}$ to get the number of tuples where at least two of the variables are equal.
So, the number of tuples where at least two of the variables are equal is, $6\times1019090-2\times4\times673$
$\therefore$ The number of tuples where every variable is pairwise distinct is ${2020\choose3}-6\times1019090+2\times4\times673$.
Now since we don't care about permutation, we have to divide by $4!$ since every combination is counted $4!$ times.
Our final answer is, \[\boxed{\frac{{2020\choose3}-6\times1019090+2\times4\times673}{4!}=56899416}\]
In the following question it has been asked that a,b,c,d are four different integers . So I'm not very sure about counting tuples like {a,m,m,m} or {a,m,m,d} . I think it would be better to assume {a,b,c,d} is a set. But anyway, the solution you have shown is a very interesting one. So thank you very much for replying :)
There might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

M F Ruhan
Posts:13
Joined:Fri Apr 02, 2021 1:42 pm
Contact:

Re: Please help me solve this problem!!

Unread post by M F Ruhan » Tue Apr 06, 2021 11:31 am

Mehrab4226 wrote:
Tue Apr 06, 2021 11:10 am
M F Ruhan wrote:
Tue Apr 06, 2021 10:33 am
Anindya Biswas wrote:
Tue Apr 06, 2021 2:48 am
Well, here's the solution:
Number of tuples $(a,b,c,d)$ is $2020\choose 3$ [Stars and bars theorem maybe]
Remember, while doing this calculation, we have some tuples where they are not pairwise distinct and also here, the positions are important.
Now let's calculate the number of tuples where at least $2$ of them are equal.
Observe that since $2021$ is not divisible by $4$, we have no tuple for which $a=b=c=d$.
  1. Let's first focus on tuples where exactly $3$ of them are equal.
    WLOG, assume that $b=c=d=m$
    $\therefore 3m+a=2021$
    This has positive solutions when $1\leq m\leq 673$
    So, this equation has $673$ solutions.
    However, we have $4$ choices to choose $3$ numbers to be equal. And each of them gives $673$ non-intersecting tuples.
    So, number of tuples where exactly $3$ of the numbers are equal is $4\times673$. For convenience, we will call this tuples the $\text{3-tuples}$.
  2. Now let's count the number of tuples where $a=b=m$. That means, we have to count the number of tuples of the form $(m,m,c,d)$ or, equivalently, number of solutions to the equation $2m+c+d=2021$. We can substitute $m=1,2,3,\dots,1009$ and count each of them and take their sum. We get, $2+4+6+\dots+2018=1019090$.
    However, there are ${4\choose2}=6$ ways to choose $2$ variables to be equal.
    Another important thing to realize is the tuple $(m,m,m,d)$ is counted $3$ times while counting $(m,m,c,d), (m,b,m,d), (a,m,m,d)$. Thus each $\text{3-tuples}$ will be counted $3$ times. So, we have to subtract twice the number of $\text{3-tuples}$ to get the number of tuples where at least two of the variables are equal.
So, the number of tuples where at least two of the variables are equal is, $6\times1019090-2\times4\times673$
$\therefore$ The number of tuples where every variable is pairwise distinct is ${2020\choose3}-6\times1019090+2\times4\times673$.
Now since we don't care about permutation, we have to divide by $4!$ since every combination is counted $4!$ times.
Our final answer is, \[\boxed{\frac{{2020\choose3}-6\times1019090+2\times4\times673}{4!}=56899416}\]
In the following question it has been asked that a,b,c,d are four different integers . So I'm not very sure about counting tuples like {a,m,m,m} or {a,m,m,d} . I think it would be better to assume {a,b,c,d} is a set. But anyway, the solution you have shown is a very interesting one. So thank you very much for replying :)
There might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.
Yes, obviously it is . By not counting tuples like {a,m,m,m} , I have meant tuples where a=b=c=d, a=b=c, b=c=d, a=b , c= d etc. Because the question says that a,b,c,d are 4 different positive integers, but if a=b, then they can't remain different. So, for my solution I have counted by at first keeping a md b constant and counting all possible values of c,d . But in my method repetitions like {a,b,c,d} {a,c,b,d} are being counted as 2 different ways and if I divide the number by 4!, there is a remainder. Currently I'm very confused and I don't think my answer is correct, so I haven't submitted it in the forum.

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Please help me solve this problem!!

Unread post by Anindya Biswas » Tue Apr 06, 2021 12:56 pm

M F Ruhan wrote:
Tue Apr 06, 2021 11:31 am
Mehrab4226 wrote:
Tue Apr 06, 2021 11:10 am
M F Ruhan wrote:
Tue Apr 06, 2021 10:33 am

In the following question it has been asked that a,b,c,d are four different integers . So I'm not very sure about counting tuples like {a,m,m,m} or {a,m,m,d} . I think it would be better to assume {a,b,c,d} is a set. But anyway, the solution you have shown is a very interesting one. So thank you very much for replying :)
There might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.
Yes, obviously it is . By not counting tuples like {a,m,m,m} , I have meant tuples where a=b=c=d, a=b=c, b=c=d, a=b , c= d etc. Because the question says that a,b,c,d are 4 different positive integers, but if a=b, then they can't remain different. So, for my solution I have counted by at first keeping a md b constant and counting all possible values of c,d . But in my method repetitions like {a,b,c,d} {a,c,b,d} are being counted as 2 different ways and if I divide the number by 4!, there is a remainder. Currently I'm very confused and I don't think my answer is correct, so I haven't submitted it in the forum.
I counted the number of tuples where at least $2$ variables are equal, then subtracted that result from the number of all the tuples. Thus, we are only left with tuples where none of the variables are equal.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

M F Ruhan
Posts:13
Joined:Fri Apr 02, 2021 1:42 pm
Contact:

Re: Please help me solve this problem!!

Unread post by M F Ruhan » Tue Apr 06, 2021 2:18 pm

Anindya Biswas wrote:
Tue Apr 06, 2021 12:56 pm
M F Ruhan wrote:
Tue Apr 06, 2021 11:31 am
Mehrab4226 wrote:
Tue Apr 06, 2021 11:10 am

There might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.
Yes, obviously it is . By not counting tuples like {a,m,m,m} , I have meant tuples where a=b=c=d, a=b=c, b=c=d, a=b , c= d etc. Because the question says that a,b,c,d are 4 different positive integers, but if a=b, then they can't remain different. So, for my solution I have counted by at first keeping a md b constant and counting all possible values of c,d . But in my method repetitions like {a,b,c,d} {a,c,b,d} are being counted as 2 different ways and if I divide the number by 4!, there is a remainder. Currently I'm very confused and I don't think my answer is correct, so I haven't submitted it in the forum.
I counted the number of tuples where at least $2$ variables are equal, then subtracted that result from the number of all the tuples. Thus, we are only left with tuples where none of the variables are equal.
Yes, you are correct . There were a few problems in my approach to the problem. I have got the same answer as you after fixing the problems. Your solution was a great help. Thank you again. :D

Post Reply