Product of $k$ distinct positive integers is divisible by its sum
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?
It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.
combinatorics number-theory elementary-number-theory
 |Â
show 6 more comments
up vote
2
down vote
favorite
Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?
It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.
combinatorics number-theory elementary-number-theory
Where did you find this problem?
â Jam
Aug 26 at 11:14
@Jam I don't know. Was it already asked in this community?
â Mathwriter
Aug 26 at 11:18
1
@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
â Jam
Aug 26 at 13:02
1
$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
â Gerry Myerson
Aug 26 at 13:07
1
Another one for $(k,n)=(2,3)$ is $15,30,60$.
â quasi
Aug 26 at 13:09
 |Â
show 6 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?
It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.
combinatorics number-theory elementary-number-theory
Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?
It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.
combinatorics number-theory elementary-number-theory
combinatorics number-theory elementary-number-theory
edited Aug 26 at 14:31
Asaf Karagilaâ¦
295k32410738
295k32410738
asked Aug 26 at 11:12
Mathwriter
395
395
Where did you find this problem?
â Jam
Aug 26 at 11:14
@Jam I don't know. Was it already asked in this community?
â Mathwriter
Aug 26 at 11:18
1
@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
â Jam
Aug 26 at 13:02
1
$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
â Gerry Myerson
Aug 26 at 13:07
1
Another one for $(k,n)=(2,3)$ is $15,30,60$.
â quasi
Aug 26 at 13:09
 |Â
show 6 more comments
Where did you find this problem?
â Jam
Aug 26 at 11:14
@Jam I don't know. Was it already asked in this community?
â Mathwriter
Aug 26 at 11:18
1
@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
â Jam
Aug 26 at 13:02
1
$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
â Gerry Myerson
Aug 26 at 13:07
1
Another one for $(k,n)=(2,3)$ is $15,30,60$.
â quasi
Aug 26 at 13:09
Where did you find this problem?
â Jam
Aug 26 at 11:14
Where did you find this problem?
â Jam
Aug 26 at 11:14
@Jam I don't know. Was it already asked in this community?
â Mathwriter
Aug 26 at 11:18
@Jam I don't know. Was it already asked in this community?
â Mathwriter
Aug 26 at 11:18
1
1
@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
â Jam
Aug 26 at 13:02
@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
â Jam
Aug 26 at 13:02
1
1
$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
â Gerry Myerson
Aug 26 at 13:07
$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
â Gerry Myerson
Aug 26 at 13:07
1
1
Another one for $(k,n)=(2,3)$ is $15,30,60$.
â quasi
Aug 26 at 13:09
Another one for $(k,n)=(2,3)$ is $15,30,60$.
â quasi
Aug 26 at 13:09
 |Â
show 6 more comments
2 Answers
2
active
oldest
votes
up vote
5
down vote
Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.
1
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
add a comment |Â
up vote
4
down vote
Fix positive integers $k,n$ with $2le k le n$.
Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.
Define $y_1,...,y_n$ by $y_i=ax_i$.
Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.
1
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
add a comment |Â
up vote
5
down vote
Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.
1
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.
Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.
answered Aug 26 at 13:14
Gerry Myerson
144k8145296
144k8145296
1
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
add a comment |Â
1
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
1
1
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
(+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
â Jam
Aug 26 at 14:03
add a comment |Â
up vote
4
down vote
Fix positive integers $k,n$ with $2le k le n$.
Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.
Define $y_1,...,y_n$ by $y_i=ax_i$.
Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.
add a comment |Â
up vote
4
down vote
Fix positive integers $k,n$ with $2le k le n$.
Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.
Define $y_1,...,y_n$ by $y_i=ax_i$.
Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Fix positive integers $k,n$ with $2le k le n$.
Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.
Define $y_1,...,y_n$ by $y_i=ax_i$.
Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.
Fix positive integers $k,n$ with $2le k le n$.
Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.
Define $y_1,...,y_n$ by $y_i=ax_i$.
Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.
answered Aug 26 at 13:21
quasi
34k22461
34k22461
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2894928%2fproduct-of-k-distinct-positive-integers-is-divisible-by-its-sum%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Where did you find this problem?
â Jam
Aug 26 at 11:14
@Jam I don't know. Was it already asked in this community?
â Mathwriter
Aug 26 at 11:18
1
@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
â Jam
Aug 26 at 13:02
1
$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
â Gerry Myerson
Aug 26 at 13:07
1
Another one for $(k,n)=(2,3)$ is $15,30,60$.
â quasi
Aug 26 at 13:09