Sizes of a pair of sequences with identical sums of pairs
$begingroup$
I am currently collecting various problems for an exam for my students. While looking through old homework assignments of my colleagues I came upon the following problem (marked as difficult):
Given two sequences of natural numbers ${a_k}$ and ${b_k}$, $k=1,ldots,n$ (with non-identical sets of elements) such that the sets of their pairwise sums $${a_1+a_2,a_1 + a_3,ldots, a_{n-1}+a_n}$$ and $${b_1+b_2,b_1 + b_3,ldots, b_{n-1}+b_n}$$ coincide, show that $n=2^m, minmathbb{N}.$
Of course, I am not going to assign a problem I couldn't solve myself to the students, but I would like to see a solution to this. This problem was accompanied with the following tip:
"Use the fact that if for two polynomials $F(x)$ and $G(x)$ if $F(1)=G(1)$, then $F(x)-G(x)=(x-1)^kH(x)$, where $H(1)neq 0$".
combinatorics discrete-mathematics
$endgroup$
add a comment |
$begingroup$
I am currently collecting various problems for an exam for my students. While looking through old homework assignments of my colleagues I came upon the following problem (marked as difficult):
Given two sequences of natural numbers ${a_k}$ and ${b_k}$, $k=1,ldots,n$ (with non-identical sets of elements) such that the sets of their pairwise sums $${a_1+a_2,a_1 + a_3,ldots, a_{n-1}+a_n}$$ and $${b_1+b_2,b_1 + b_3,ldots, b_{n-1}+b_n}$$ coincide, show that $n=2^m, minmathbb{N}.$
Of course, I am not going to assign a problem I couldn't solve myself to the students, but I would like to see a solution to this. This problem was accompanied with the following tip:
"Use the fact that if for two polynomials $F(x)$ and $G(x)$ if $F(1)=G(1)$, then $F(x)-G(x)=(x-1)^kH(x)$, where $H(1)neq 0$".
combinatorics discrete-mathematics
$endgroup$
$begingroup$
What course was the homework for?
$endgroup$
– Peter Taylor
Dec 8 '18 at 21:14
$begingroup$
@PeterTaylor It is called "Boolean algebra, combinatorics and graph theory", it is an introductory course for first year students.
$endgroup$
– Serg
Dec 8 '18 at 21:32
$begingroup$
Can you give an example of such $a_k,b_k$ with say $n=4$? I realize it's just to show it can't happen for $n$ not a power of 2, but was wondering what kind of examples might be for small powers of $2.$
$endgroup$
– coffeemath
Dec 8 '18 at 21:47
add a comment |
$begingroup$
I am currently collecting various problems for an exam for my students. While looking through old homework assignments of my colleagues I came upon the following problem (marked as difficult):
Given two sequences of natural numbers ${a_k}$ and ${b_k}$, $k=1,ldots,n$ (with non-identical sets of elements) such that the sets of their pairwise sums $${a_1+a_2,a_1 + a_3,ldots, a_{n-1}+a_n}$$ and $${b_1+b_2,b_1 + b_3,ldots, b_{n-1}+b_n}$$ coincide, show that $n=2^m, minmathbb{N}.$
Of course, I am not going to assign a problem I couldn't solve myself to the students, but I would like to see a solution to this. This problem was accompanied with the following tip:
"Use the fact that if for two polynomials $F(x)$ and $G(x)$ if $F(1)=G(1)$, then $F(x)-G(x)=(x-1)^kH(x)$, where $H(1)neq 0$".
combinatorics discrete-mathematics
$endgroup$
I am currently collecting various problems for an exam for my students. While looking through old homework assignments of my colleagues I came upon the following problem (marked as difficult):
Given two sequences of natural numbers ${a_k}$ and ${b_k}$, $k=1,ldots,n$ (with non-identical sets of elements) such that the sets of their pairwise sums $${a_1+a_2,a_1 + a_3,ldots, a_{n-1}+a_n}$$ and $${b_1+b_2,b_1 + b_3,ldots, b_{n-1}+b_n}$$ coincide, show that $n=2^m, minmathbb{N}.$
Of course, I am not going to assign a problem I couldn't solve myself to the students, but I would like to see a solution to this. This problem was accompanied with the following tip:
"Use the fact that if for two polynomials $F(x)$ and $G(x)$ if $F(1)=G(1)$, then $F(x)-G(x)=(x-1)^kH(x)$, where $H(1)neq 0$".
combinatorics discrete-mathematics
combinatorics discrete-mathematics
asked Dec 8 '18 at 20:37
SergSerg
611415
611415
$begingroup$
What course was the homework for?
$endgroup$
– Peter Taylor
Dec 8 '18 at 21:14
$begingroup$
@PeterTaylor It is called "Boolean algebra, combinatorics and graph theory", it is an introductory course for first year students.
$endgroup$
– Serg
Dec 8 '18 at 21:32
$begingroup$
Can you give an example of such $a_k,b_k$ with say $n=4$? I realize it's just to show it can't happen for $n$ not a power of 2, but was wondering what kind of examples might be for small powers of $2.$
$endgroup$
– coffeemath
Dec 8 '18 at 21:47
add a comment |
$begingroup$
What course was the homework for?
$endgroup$
– Peter Taylor
Dec 8 '18 at 21:14
$begingroup$
@PeterTaylor It is called "Boolean algebra, combinatorics and graph theory", it is an introductory course for first year students.
$endgroup$
– Serg
Dec 8 '18 at 21:32
$begingroup$
Can you give an example of such $a_k,b_k$ with say $n=4$? I realize it's just to show it can't happen for $n$ not a power of 2, but was wondering what kind of examples might be for small powers of $2.$
$endgroup$
– coffeemath
Dec 8 '18 at 21:47
$begingroup$
What course was the homework for?
$endgroup$
– Peter Taylor
Dec 8 '18 at 21:14
$begingroup$
What course was the homework for?
$endgroup$
– Peter Taylor
Dec 8 '18 at 21:14
$begingroup$
@PeterTaylor It is called "Boolean algebra, combinatorics and graph theory", it is an introductory course for first year students.
$endgroup$
– Serg
Dec 8 '18 at 21:32
$begingroup$
@PeterTaylor It is called "Boolean algebra, combinatorics and graph theory", it is an introductory course for first year students.
$endgroup$
– Serg
Dec 8 '18 at 21:32
$begingroup$
Can you give an example of such $a_k,b_k$ with say $n=4$? I realize it's just to show it can't happen for $n$ not a power of 2, but was wondering what kind of examples might be for small powers of $2.$
$endgroup$
– coffeemath
Dec 8 '18 at 21:47
$begingroup$
Can you give an example of such $a_k,b_k$ with say $n=4$? I realize it's just to show it can't happen for $n$ not a power of 2, but was wondering what kind of examples might be for small powers of $2.$
$endgroup$
– coffeemath
Dec 8 '18 at 21:47
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I will show that the statement is true with the condition that
The two multisets $A={a_i+a_j:1 le i<jle n}$ and
$B={b_i+b_j:1 le i<jle n}$ are the same
(i.e. if $x in A$ appears $k$ times in $A$ then
$x$ appears $k$ times in $B$).Two sets ${a_i}$ and ${b_i}$ are not the same.
Let $A(x)=sum_{i=1}^n x^{a_i}$ and $B(x)=sum_{i=1}^n x^{b_i}$
then we have $A^2(x)=A(x^2)+2sum_{iin A} x^i$ and similarly,
$B^2(x)=B(x^2)+2sum_{iin B} x^i$. Therefore,
$$A(x^2)-B(x^2)=A^2(x)-B^2(x)=[A(x)+B(x)][A(x)-B(x)].$$
Since $A(1)=B(1)=n$ so $A(x)-B(x)=(x-1)^kG(x)$ where $G(1)ne 0,
k ge 1$.This follows
$$(x^2-1)^k G(x^2)=A(x^2)-B(x^2)=[A(x)+B(x)]cdot (x-1)^k G(x).$$
Therefore, $(x+1)^k G(x^2)=[A(x)+B(x)]G(x)$. Substituting $x=1$ into this
and note that $A(1)+B(1)=2n$ and $G(1)ne 0$,
we obtain $n=2^{k-1}$, as desired.
$endgroup$
add a comment |
$begingroup$
Consider the sequence $(a_k)=(2,4,4)$ and the sequence $(b_k)=(3,3,5)$. Then the two sequences have non-identical sets of elements, but the sets of their pairwise sums are as follows:
$$
A={2+4,2+4,4+4}={6,8}
$$
$$
B={3+3,3+5,3+5}={6,8}
$$
It would then seem that we need to alter the language to make the statement true... maybe it should be a multiset? Maybe the sequences can't have repeated values?
EDIT: Some quick and dirty coding indicates the following question rewrite has a better chance of being true:
Given two sets of natural numbers $A$ and $B$ where $Aneq B$ and $|A|=|B|=n$ such that the restricted sumsets $2^wedge A$ and $2^wedge B$ are equal, show that $n=2^m$ for some natural number $m$.
To answer @coffeemath's comment in the OP, you can take $A={1,4,5,6}$ and $B={2,3,4,7}$ as examples of the case $n=4$.
$endgroup$
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
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%2f3031612%2fsizes-of-a-pair-of-sequences-with-identical-sums-of-pairs%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$
I will show that the statement is true with the condition that
The two multisets $A={a_i+a_j:1 le i<jle n}$ and
$B={b_i+b_j:1 le i<jle n}$ are the same
(i.e. if $x in A$ appears $k$ times in $A$ then
$x$ appears $k$ times in $B$).Two sets ${a_i}$ and ${b_i}$ are not the same.
Let $A(x)=sum_{i=1}^n x^{a_i}$ and $B(x)=sum_{i=1}^n x^{b_i}$
then we have $A^2(x)=A(x^2)+2sum_{iin A} x^i$ and similarly,
$B^2(x)=B(x^2)+2sum_{iin B} x^i$. Therefore,
$$A(x^2)-B(x^2)=A^2(x)-B^2(x)=[A(x)+B(x)][A(x)-B(x)].$$
Since $A(1)=B(1)=n$ so $A(x)-B(x)=(x-1)^kG(x)$ where $G(1)ne 0,
k ge 1$.This follows
$$(x^2-1)^k G(x^2)=A(x^2)-B(x^2)=[A(x)+B(x)]cdot (x-1)^k G(x).$$
Therefore, $(x+1)^k G(x^2)=[A(x)+B(x)]G(x)$. Substituting $x=1$ into this
and note that $A(1)+B(1)=2n$ and $G(1)ne 0$,
we obtain $n=2^{k-1}$, as desired.
$endgroup$
add a comment |
$begingroup$
I will show that the statement is true with the condition that
The two multisets $A={a_i+a_j:1 le i<jle n}$ and
$B={b_i+b_j:1 le i<jle n}$ are the same
(i.e. if $x in A$ appears $k$ times in $A$ then
$x$ appears $k$ times in $B$).Two sets ${a_i}$ and ${b_i}$ are not the same.
Let $A(x)=sum_{i=1}^n x^{a_i}$ and $B(x)=sum_{i=1}^n x^{b_i}$
then we have $A^2(x)=A(x^2)+2sum_{iin A} x^i$ and similarly,
$B^2(x)=B(x^2)+2sum_{iin B} x^i$. Therefore,
$$A(x^2)-B(x^2)=A^2(x)-B^2(x)=[A(x)+B(x)][A(x)-B(x)].$$
Since $A(1)=B(1)=n$ so $A(x)-B(x)=(x-1)^kG(x)$ where $G(1)ne 0,
k ge 1$.This follows
$$(x^2-1)^k G(x^2)=A(x^2)-B(x^2)=[A(x)+B(x)]cdot (x-1)^k G(x).$$
Therefore, $(x+1)^k G(x^2)=[A(x)+B(x)]G(x)$. Substituting $x=1$ into this
and note that $A(1)+B(1)=2n$ and $G(1)ne 0$,
we obtain $n=2^{k-1}$, as desired.
$endgroup$
add a comment |
$begingroup$
I will show that the statement is true with the condition that
The two multisets $A={a_i+a_j:1 le i<jle n}$ and
$B={b_i+b_j:1 le i<jle n}$ are the same
(i.e. if $x in A$ appears $k$ times in $A$ then
$x$ appears $k$ times in $B$).Two sets ${a_i}$ and ${b_i}$ are not the same.
Let $A(x)=sum_{i=1}^n x^{a_i}$ and $B(x)=sum_{i=1}^n x^{b_i}$
then we have $A^2(x)=A(x^2)+2sum_{iin A} x^i$ and similarly,
$B^2(x)=B(x^2)+2sum_{iin B} x^i$. Therefore,
$$A(x^2)-B(x^2)=A^2(x)-B^2(x)=[A(x)+B(x)][A(x)-B(x)].$$
Since $A(1)=B(1)=n$ so $A(x)-B(x)=(x-1)^kG(x)$ where $G(1)ne 0,
k ge 1$.This follows
$$(x^2-1)^k G(x^2)=A(x^2)-B(x^2)=[A(x)+B(x)]cdot (x-1)^k G(x).$$
Therefore, $(x+1)^k G(x^2)=[A(x)+B(x)]G(x)$. Substituting $x=1$ into this
and note that $A(1)+B(1)=2n$ and $G(1)ne 0$,
we obtain $n=2^{k-1}$, as desired.
$endgroup$
I will show that the statement is true with the condition that
The two multisets $A={a_i+a_j:1 le i<jle n}$ and
$B={b_i+b_j:1 le i<jle n}$ are the same
(i.e. if $x in A$ appears $k$ times in $A$ then
$x$ appears $k$ times in $B$).Two sets ${a_i}$ and ${b_i}$ are not the same.
Let $A(x)=sum_{i=1}^n x^{a_i}$ and $B(x)=sum_{i=1}^n x^{b_i}$
then we have $A^2(x)=A(x^2)+2sum_{iin A} x^i$ and similarly,
$B^2(x)=B(x^2)+2sum_{iin B} x^i$. Therefore,
$$A(x^2)-B(x^2)=A^2(x)-B^2(x)=[A(x)+B(x)][A(x)-B(x)].$$
Since $A(1)=B(1)=n$ so $A(x)-B(x)=(x-1)^kG(x)$ where $G(1)ne 0,
k ge 1$.This follows
$$(x^2-1)^k G(x^2)=A(x^2)-B(x^2)=[A(x)+B(x)]cdot (x-1)^k G(x).$$
Therefore, $(x+1)^k G(x^2)=[A(x)+B(x)]G(x)$. Substituting $x=1$ into this
and note that $A(1)+B(1)=2n$ and $G(1)ne 0$,
we obtain $n=2^{k-1}$, as desired.
answered Dec 9 '18 at 4:04
TenguTengu
2,66411021
2,66411021
add a comment |
add a comment |
$begingroup$
Consider the sequence $(a_k)=(2,4,4)$ and the sequence $(b_k)=(3,3,5)$. Then the two sequences have non-identical sets of elements, but the sets of their pairwise sums are as follows:
$$
A={2+4,2+4,4+4}={6,8}
$$
$$
B={3+3,3+5,3+5}={6,8}
$$
It would then seem that we need to alter the language to make the statement true... maybe it should be a multiset? Maybe the sequences can't have repeated values?
EDIT: Some quick and dirty coding indicates the following question rewrite has a better chance of being true:
Given two sets of natural numbers $A$ and $B$ where $Aneq B$ and $|A|=|B|=n$ such that the restricted sumsets $2^wedge A$ and $2^wedge B$ are equal, show that $n=2^m$ for some natural number $m$.
To answer @coffeemath's comment in the OP, you can take $A={1,4,5,6}$ and $B={2,3,4,7}$ as examples of the case $n=4$.
$endgroup$
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
add a comment |
$begingroup$
Consider the sequence $(a_k)=(2,4,4)$ and the sequence $(b_k)=(3,3,5)$. Then the two sequences have non-identical sets of elements, but the sets of their pairwise sums are as follows:
$$
A={2+4,2+4,4+4}={6,8}
$$
$$
B={3+3,3+5,3+5}={6,8}
$$
It would then seem that we need to alter the language to make the statement true... maybe it should be a multiset? Maybe the sequences can't have repeated values?
EDIT: Some quick and dirty coding indicates the following question rewrite has a better chance of being true:
Given two sets of natural numbers $A$ and $B$ where $Aneq B$ and $|A|=|B|=n$ such that the restricted sumsets $2^wedge A$ and $2^wedge B$ are equal, show that $n=2^m$ for some natural number $m$.
To answer @coffeemath's comment in the OP, you can take $A={1,4,5,6}$ and $B={2,3,4,7}$ as examples of the case $n=4$.
$endgroup$
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
add a comment |
$begingroup$
Consider the sequence $(a_k)=(2,4,4)$ and the sequence $(b_k)=(3,3,5)$. Then the two sequences have non-identical sets of elements, but the sets of their pairwise sums are as follows:
$$
A={2+4,2+4,4+4}={6,8}
$$
$$
B={3+3,3+5,3+5}={6,8}
$$
It would then seem that we need to alter the language to make the statement true... maybe it should be a multiset? Maybe the sequences can't have repeated values?
EDIT: Some quick and dirty coding indicates the following question rewrite has a better chance of being true:
Given two sets of natural numbers $A$ and $B$ where $Aneq B$ and $|A|=|B|=n$ such that the restricted sumsets $2^wedge A$ and $2^wedge B$ are equal, show that $n=2^m$ for some natural number $m$.
To answer @coffeemath's comment in the OP, you can take $A={1,4,5,6}$ and $B={2,3,4,7}$ as examples of the case $n=4$.
$endgroup$
Consider the sequence $(a_k)=(2,4,4)$ and the sequence $(b_k)=(3,3,5)$. Then the two sequences have non-identical sets of elements, but the sets of their pairwise sums are as follows:
$$
A={2+4,2+4,4+4}={6,8}
$$
$$
B={3+3,3+5,3+5}={6,8}
$$
It would then seem that we need to alter the language to make the statement true... maybe it should be a multiset? Maybe the sequences can't have repeated values?
EDIT: Some quick and dirty coding indicates the following question rewrite has a better chance of being true:
Given two sets of natural numbers $A$ and $B$ where $Aneq B$ and $|A|=|B|=n$ such that the restricted sumsets $2^wedge A$ and $2^wedge B$ are equal, show that $n=2^m$ for some natural number $m$.
To answer @coffeemath's comment in the OP, you can take $A={1,4,5,6}$ and $B={2,3,4,7}$ as examples of the case $n=4$.
edited Dec 9 '18 at 3:29
answered Dec 9 '18 at 2:44
RandomMathGuyRandomMathGuy
212
212
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
add a comment |
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
$begingroup$
RandomMathGuy--- Thanks for the $n=4$example!
$endgroup$
– coffeemath
Dec 10 '18 at 0:14
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%2f3031612%2fsizes-of-a-pair-of-sequences-with-identical-sums-of-pairs%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
$begingroup$
What course was the homework for?
$endgroup$
– Peter Taylor
Dec 8 '18 at 21:14
$begingroup$
@PeterTaylor It is called "Boolean algebra, combinatorics and graph theory", it is an introductory course for first year students.
$endgroup$
– Serg
Dec 8 '18 at 21:32
$begingroup$
Can you give an example of such $a_k,b_k$ with say $n=4$? I realize it's just to show it can't happen for $n$ not a power of 2, but was wondering what kind of examples might be for small powers of $2.$
$endgroup$
– coffeemath
Dec 8 '18 at 21:47