Mixing
Splitting the natural numbers into sets $A$ and $B$ such that for distinct elements $m,nin A$ we have $m+nin...
$begingroup$
Why it is impossible to split the natural numbers into sets $A$ and $B$ such that for distinct elements $m, n in A$ we have $m + n in B$ and vice-versa.
Also, does vice-versa means that there are distinct elements such that $x + y in A$?
How do I show the proof?
combinatorics ramsey-theory
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
$endgroup$
add a comment |
$begingroup$
Why it is impossible to split the natural numbers into sets $A$ and $B$ such that for distinct elements $m, n in A$ we have $m + n in B$ and vice-versa.
Also, does vice-versa means that there are distinct elements such that $x + y in A$?
How do I show the proof?
combinatorics ramsey-theory
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
$endgroup$
add a comment |
$begingroup$
Why it is impossible to split the natural numbers into sets $A$ and $B$ such that for distinct elements $m, n in A$ we have $m + n in B$ and vice-versa.
Also, does vice-versa means that there are distinct elements such that $x + y in A$?
How do I show the proof?
combinatorics ramsey-theory
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
$endgroup$
Why it is impossible to split the natural numbers into sets $A$ and $B$ such that for distinct elements $m, n in A$ we have $m + n in B$ and vice-versa.
Also, does vice-versa means that there are distinct elements such that $x + y in A$?
How do I show the proof?
combinatorics ramsey-theory
combinatorics ramsey-theory
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
edited Jan 18 at 12:28
Andrés E. Caicedo
65.5k8159250
65.5k8159250
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
asked Jan 18 at 11:03
Leo ZhangLeo Zhang
61
61
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Vice versa means that for distinct $m,n in B$, $m+n in A$.
I guess you have to work through some cases.
For instance, suppose that $1 in A$ and $2 in A$. Then $3 in B$.
- If $4 in A$, we have $5, 6 in B$, i.e. $8, 9 in A$, which is a contradiction since $9=1+8$ and every summand is in $A$.
- If $4 in B$, we have $7 in A$, i.e. $8, 9 in B$, i.e. $11, 12, 13 in A$ which is a contradiction since $12=1+11$.
answered Jan 18 at 11:24
StockfishStockfish
62726
$endgroup$
add a comment |
$begingroup$
It is a famous fact of Ramsey theory that, if each edge of $K_6$ (a complete graph on $6$ vertices) is colored red or blue, there will be a triangle whose edges are all the same color.
Suppose the set $S={1,2,3,4,5,6,7,8,9,10}$ is partitioned into two sets $A$ and $B$. I claim that there are distinct numbers $m,n$ in one of those two sets such that $m+n$ is in the same set.
Consider the complete graph with vertex set $V={0,1,3,4,9,10}$. For $x,yin V$, color the edge $xy$ red if $|x-y|in A$, blue if $|x-y|in B$. Then there are three vertices $xlt ylt z$ in $V$ such that the edges $xy$, $yz$, $xz$ all have the same color. Let $m=y-x$ and $n=z-y$, so that $m+n=z-x$. Then $m,nin S$, and $mne n$ since the set $V$ does not contain $3$ numbers in arithmetic progression. If $xy$, $yz$, $xz$ are all red, then $m,n,m+nin A$; if they are all blue, then $m,n,m+nin B$.
answered Jan 18 at 11:57
bofbof
52.2k558121
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078097%2fsplitting-the-natural-numbers-into-sets-a-and-b-such-that-for-distinct-eleme%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Vice versa means that for distinct $m,n in B$, $m+n in A$.
I guess you have to work through some cases.
For instance, suppose that $1 in A$ and $2 in A$. Then $3 in B$.
- If $4 in A$, we have $5, 6 in B$, i.e. $8, 9 in A$, which is a contradiction since $9=1+8$ and every summand is in $A$.
- If $4 in B$, we have $7 in A$, i.e. $8, 9 in B$, i.e. $11, 12, 13 in A$ which is a contradiction since $12=1+11$.
answered Jan 18 at 11:24
StockfishStockfish
62726
$endgroup$
add a comment |
$begingroup$
Vice versa means that for distinct $m,n in B$, $m+n in A$.
I guess you have to work through some cases.
For instance, suppose that $1 in A$ and $2 in A$. Then $3 in B$.
- If $4 in A$, we have $5, 6 in B$, i.e. $8, 9 in A$, which is a contradiction since $9=1+8$ and every summand is in $A$.
- If $4 in B$, we have $7 in A$, i.e. $8, 9 in B$, i.e. $11, 12, 13 in A$ which is a contradiction since $12=1+11$.
answered Jan 18 at 11:24
StockfishStockfish
62726
$endgroup$
add a comment |
$begingroup$
Vice versa means that for distinct $m,n in B$, $m+n in A$.
I guess you have to work through some cases.
For instance, suppose that $1 in A$ and $2 in A$. Then $3 in B$.
- If $4 in A$, we have $5, 6 in B$, i.e. $8, 9 in A$, which is a contradiction since $9=1+8$ and every summand is in $A$.
- If $4 in B$, we have $7 in A$, i.e. $8, 9 in B$, i.e. $11, 12, 13 in A$ which is a contradiction since $12=1+11$.
answered Jan 18 at 11:24
StockfishStockfish
62726
$endgroup$
Vice versa means that for distinct $m,n in B$, $m+n in A$.
I guess you have to work through some cases.
For instance, suppose that $1 in A$ and $2 in A$. Then $3 in B$.
- If $4 in A$, we have $5, 6 in B$, i.e. $8, 9 in A$, which is a contradiction since $9=1+8$ and every summand is in $A$.
- If $4 in B$, we have $7 in A$, i.e. $8, 9 in B$, i.e. $11, 12, 13 in A$ which is a contradiction since $12=1+11$.
answered Jan 18 at 11:24
StockfishStockfish
62726
answered Jan 18 at 11:24
StockfishStockfish
62726
answered Jan 18 at 11:24
StockfishStockfish
62726
answered Jan 18 at 11:24
StockfishStockfish
62726
62726
add a comment |
add a comment |
$begingroup$
It is a famous fact of Ramsey theory that, if each edge of $K_6$ (a complete graph on $6$ vertices) is colored red or blue, there will be a triangle whose edges are all the same color.
Suppose the set $S={1,2,3,4,5,6,7,8,9,10}$ is partitioned into two sets $A$ and $B$. I claim that there are distinct numbers $m,n$ in one of those two sets such that $m+n$ is in the same set.
Consider the complete graph with vertex set $V={0,1,3,4,9,10}$. For $x,yin V$, color the edge $xy$ red if $|x-y|in A$, blue if $|x-y|in B$. Then there are three vertices $xlt ylt z$ in $V$ such that the edges $xy$, $yz$, $xz$ all have the same color. Let $m=y-x$ and $n=z-y$, so that $m+n=z-x$. Then $m,nin S$, and $mne n$ since the set $V$ does not contain $3$ numbers in arithmetic progression. If $xy$, $yz$, $xz$ are all red, then $m,n,m+nin A$; if they are all blue, then $m,n,m+nin B$.
answered Jan 18 at 11:57
bofbof
52.2k558121
$endgroup$
add a comment |
$begingroup$
It is a famous fact of Ramsey theory that, if each edge of $K_6$ (a complete graph on $6$ vertices) is colored red or blue, there will be a triangle whose edges are all the same color.
Suppose the set $S={1,2,3,4,5,6,7,8,9,10}$ is partitioned into two sets $A$ and $B$. I claim that there are distinct numbers $m,n$ in one of those two sets such that $m+n$ is in the same set.
Consider the complete graph with vertex set $V={0,1,3,4,9,10}$. For $x,yin V$, color the edge $xy$ red if $|x-y|in A$, blue if $|x-y|in B$. Then there are three vertices $xlt ylt z$ in $V$ such that the edges $xy$, $yz$, $xz$ all have the same color. Let $m=y-x$ and $n=z-y$, so that $m+n=z-x$. Then $m,nin S$, and $mne n$ since the set $V$ does not contain $3$ numbers in arithmetic progression. If $xy$, $yz$, $xz$ are all red, then $m,n,m+nin A$; if they are all blue, then $m,n,m+nin B$.
answered Jan 18 at 11:57
bofbof
52.2k558121
$endgroup$
add a comment |
$begingroup$
It is a famous fact of Ramsey theory that, if each edge of $K_6$ (a complete graph on $6$ vertices) is colored red or blue, there will be a triangle whose edges are all the same color.
Suppose the set $S={1,2,3,4,5,6,7,8,9,10}$ is partitioned into two sets $A$ and $B$. I claim that there are distinct numbers $m,n$ in one of those two sets such that $m+n$ is in the same set.
Consider the complete graph with vertex set $V={0,1,3,4,9,10}$. For $x,yin V$, color the edge $xy$ red if $|x-y|in A$, blue if $|x-y|in B$. Then there are three vertices $xlt ylt z$ in $V$ such that the edges $xy$, $yz$, $xz$ all have the same color. Let $m=y-x$ and $n=z-y$, so that $m+n=z-x$. Then $m,nin S$, and $mne n$ since the set $V$ does not contain $3$ numbers in arithmetic progression. If $xy$, $yz$, $xz$ are all red, then $m,n,m+nin A$; if they are all blue, then $m,n,m+nin B$.
answered Jan 18 at 11:57
bofbof
52.2k558121
$endgroup$
It is a famous fact of Ramsey theory that, if each edge of $K_6$ (a complete graph on $6$ vertices) is colored red or blue, there will be a triangle whose edges are all the same color.
Suppose the set $S={1,2,3,4,5,6,7,8,9,10}$ is partitioned into two sets $A$ and $B$. I claim that there are distinct numbers $m,n$ in one of those two sets such that $m+n$ is in the same set.
Consider the complete graph with vertex set $V={0,1,3,4,9,10}$. For $x,yin V$, color the edge $xy$ red if $|x-y|in A$, blue if $|x-y|in B$. Then there are three vertices $xlt ylt z$ in $V$ such that the edges $xy$, $yz$, $xz$ all have the same color. Let $m=y-x$ and $n=z-y$, so that $m+n=z-x$. Then $m,nin S$, and $mne n$ since the set $V$ does not contain $3$ numbers in arithmetic progression. If $xy$, $yz$, $xz$ are all red, then $m,n,m+nin A$; if they are all blue, then $m,n,m+nin B$.
answered Jan 18 at 11:57
bofbof
52.2k558121
edited Jan 18 at 12:25
answered Jan 18 at 11:57
bofbof
52.2k558121
answered Jan 18 at 11:57
bofbof
52.2k558121
answered Jan 18 at 11:57
bofbof
52.2k558121
52.2k558121
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078097%2fsplitting-the-natural-numbers-into-sets-a-and-b-such-that-for-distinct-eleme%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
