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).
Re: Please help me solve this problem!!
Posted: Tue Apr 06, 2021 12:54 am
by Anindya Biswas
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.
Re: Please help me solve this problem!!
Posted: Tue Apr 06, 2021 2:48 am
by Anindya Biswas
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$.
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.
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}\]
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$.
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.
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
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$.
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.
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.
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$.
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.
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.
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.
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.
