Mixing
Any partition of $1,2,ldots,100$ into seven subsets yields a subset with numbers $a,b,c,d$ such that $a+b=c+d$.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
A set $M = 1,2,ldots,100$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r,?$$
I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.
combinatorics functions elementary-set-theory problem-solving pigeonhole-principle
edited Jul 28 at 17:15
Batominovski
23k22777
asked Jul 28 at 7:35
Tom Allen
195
add a comment |Â
up vote
1
down vote
favorite
A set $M = 1,2,ldots,100$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r,?$$
I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.
combinatorics functions elementary-set-theory problem-solving pigeonhole-principle
edited Jul 28 at 17:15
Batominovski
23k22777
asked Jul 28 at 7:35
Tom Allen
195
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
A set $M = 1,2,ldots,100$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r,?$$
I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.
combinatorics functions elementary-set-theory problem-solving pigeonhole-principle
edited Jul 28 at 17:15
Batominovski
23k22777
asked Jul 28 at 7:35
Tom Allen
195
A set $M = 1,2,ldots,100$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r,?$$
I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.
combinatorics functions elementary-set-theory problem-solving pigeonhole-principle
edited Jul 28 at 17:15
Batominovski
23k22777
asked Jul 28 at 7:35
Tom Allen
195
edited Jul 28 at 17:15
Batominovski
23k22777
edited Jul 28 at 17:15
Batominovski
23k22777
edited Jul 28 at 17:15
Batominovski
23k22777
23k22777
asked Jul 28 at 7:35
Tom Allen
195
asked Jul 28 at 7:35
Tom Allen
195
asked Jul 28 at 7:35
Tom Allen
195
195
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
6
down vote
By pigeonhole principle some subset $S$ must have at least $15$ members, say $$S=a_1,a_2,....a_k$$
where $kgeq 15.$
Let $$A:=(x,y),;x,yin S, x<y$$
Now observe a function $$f:Alongrightarrow 1,2,...,99$$ which is (well) defined with $$f(x,y) = y-x$$
Clearly, since $|A|= kchoose 2 geq 15choose 2 = 105$ this function is not injective. So there are $a,b,c,d$ such that $$f(a,b)= f(c,d)implies b-a=d-cimplies b+c=a+d$$
answered Jul 28 at 7:52
greedoid
26.1k93473
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
By pigeonhole principle some subset $S$ must have at least $15$ members, say $$S=a_1,a_2,....a_k$$
where $kgeq 15.$
Let $$A:=(x,y),;x,yin S, x<y$$
Now observe a function $$f:Alongrightarrow 1,2,...,99$$ which is (well) defined with $$f(x,y) = y-x$$
Clearly, since $|A|= kchoose 2 geq 15choose 2 = 105$ this function is not injective. So there are $a,b,c,d$ such that $$f(a,b)= f(c,d)implies b-a=d-cimplies b+c=a+d$$
answered Jul 28 at 7:52
greedoid
26.1k93473
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
add a comment |Â
up vote
6
down vote
By pigeonhole principle some subset $S$ must have at least $15$ members, say $$S=a_1,a_2,....a_k$$
where $kgeq 15.$
Let $$A:=(x,y),;x,yin S, x<y$$
Now observe a function $$f:Alongrightarrow 1,2,...,99$$ which is (well) defined with $$f(x,y) = y-x$$
Clearly, since $|A|= kchoose 2 geq 15choose 2 = 105$ this function is not injective. So there are $a,b,c,d$ such that $$f(a,b)= f(c,d)implies b-a=d-cimplies b+c=a+d$$
answered Jul 28 at 7:52
greedoid
26.1k93473
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
add a comment |Â
up vote
6
down vote
up vote
6
down vote
By pigeonhole principle some subset $S$ must have at least $15$ members, say $$S=a_1,a_2,....a_k$$
where $kgeq 15.$
Let $$A:=(x,y),;x,yin S, x<y$$
Now observe a function $$f:Alongrightarrow 1,2,...,99$$ which is (well) defined with $$f(x,y) = y-x$$
Clearly, since $|A|= kchoose 2 geq 15choose 2 = 105$ this function is not injective. So there are $a,b,c,d$ such that $$f(a,b)= f(c,d)implies b-a=d-cimplies b+c=a+d$$
answered Jul 28 at 7:52
greedoid
26.1k93473
By pigeonhole principle some subset $S$ must have at least $15$ members, say $$S=a_1,a_2,....a_k$$
where $kgeq 15.$
Let $$A:=(x,y),;x,yin S, x<y$$
Now observe a function $$f:Alongrightarrow 1,2,...,99$$ which is (well) defined with $$f(x,y) = y-x$$
Clearly, since $|A|= kchoose 2 geq 15choose 2 = 105$ this function is not injective. So there are $a,b,c,d$ such that $$f(a,b)= f(c,d)implies b-a=d-cimplies b+c=a+d$$
answered Jul 28 at 7:52
greedoid
26.1k93473
edited Aug 4 at 10:08
answered Jul 28 at 7:52
greedoid
26.1k93473
answered Jul 28 at 7:52
greedoid
26.1k93473
answered Jul 28 at 7:52
greedoid
26.1k93473
26.1k93473
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
add a comment |Â
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
'So we are done' is fairly rude and impertinent, but ignoring that you clearly haven't answered my question.
– Tom Allen
Aug 1 at 10:09
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer.
– greedoid
Aug 1 at 10:52
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%2f2865068%2fany-partition-of-1-2-ldots-100-into-seven-subsets-yields-a-subset-with-nu%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