Please help me solve this problem!!
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).
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Please help me solve this problem!!
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.
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
— John von Neumann
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Please help me solve this problem!!
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$.
$\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}\]
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$.
- 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}$. - 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.
$\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
— John von Neumann
Re: Please help me solve this problem!!
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 replyingAnindya Biswas wrote: ↑Tue Apr 06, 2021 2:48 amWell, 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$.So, the number of tuples where at least two of the variables are equal is, $6\times1019090-2\times4\times673$
- 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}$.- 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.
$\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}\]
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Please help me solve this problem!!
There might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.M F Ruhan wrote: ↑Tue Apr 06, 2021 10:33 amIn 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
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é
-Henri Poincaré
Re: Please help me solve this problem!!
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.Mehrab4226 wrote: ↑Tue Apr 06, 2021 11:10 amThere might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.M F Ruhan wrote: ↑Tue Apr 06, 2021 10:33 amIn 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
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Please help me solve this problem!!
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.M F Ruhan wrote: ↑Tue Apr 06, 2021 11:31 amYes, 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.Mehrab4226 wrote: ↑Tue Apr 06, 2021 11:10 amThere might be a straightforward approach to the problem. But counting the tuples is an important part of the solution which is given.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
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
Re: Please help me solve this problem!!
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.Anindya Biswas wrote: ↑Tue Apr 06, 2021 12:56 pmI 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.M F Ruhan wrote: ↑Tue Apr 06, 2021 11:31 amYes, 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.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.