Sizes of a pair of sequences with identical sums of pairs












4












$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$".










share|cite|improve this question









$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
















4












$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$".










share|cite|improve this question









$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














4












4








4


2



$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$".










share|cite|improve this question









$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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










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


















  • $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










2 Answers
2






active

oldest

votes


















5












$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.






share|cite|improve this answer









$endgroup$





















    2












    $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$.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      RandomMathGuy--- Thanks for the $n=4$example!
      $endgroup$
      – coffeemath
      Dec 10 '18 at 0:14











    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    5












    $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.






    share|cite|improve this answer









    $endgroup$


















      5












      $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.






      share|cite|improve this answer









      $endgroup$
















        5












        5








        5





        $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.






        share|cite|improve this answer









        $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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 9 '18 at 4:04









        TenguTengu

        2,66411021




        2,66411021























            2












            $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$.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              RandomMathGuy--- Thanks for the $n=4$example!
              $endgroup$
              – coffeemath
              Dec 10 '18 at 0:14
















            2












            $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$.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              RandomMathGuy--- Thanks for the $n=4$example!
              $endgroup$
              – coffeemath
              Dec 10 '18 at 0:14














            2












            2








            2





            $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$.






            share|cite|improve this answer











            $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$.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            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


















            • $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


















            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            How to change which sound is reproduced for terminal bell?

            Can I use Tabulator js library in my java Spring + Thymeleaf project?

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents