Sum of freely chosen subset of $n$-tuple is divisible by $n$.












2












$begingroup$


I am struggling with the following task:



Be $n in N$ and $(a_1, a_2, ldots, a_n) in mathbb{Z}^n$. Prove that there is always $i, j in underline{n}$, with $i≤j$, so that $sum_{k=i}^j a_k$ is divisible by n.



My first idea was to use a distinction of cases. In the first case a multiple of n is an element of $mathbb{Z}^n$ so you could select the sum to be just this element so it would obviously be divisible.



In the second case, all elements of the tuple are the same, so that adding them all up will result in a multiple of $n$ once more, making it divisible.



I am lost however on what to do in the third case, where the two above are not true. I would truly appreciate your input.










share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    I am struggling with the following task:



    Be $n in N$ and $(a_1, a_2, ldots, a_n) in mathbb{Z}^n$. Prove that there is always $i, j in underline{n}$, with $i≤j$, so that $sum_{k=i}^j a_k$ is divisible by n.



    My first idea was to use a distinction of cases. In the first case a multiple of n is an element of $mathbb{Z}^n$ so you could select the sum to be just this element so it would obviously be divisible.



    In the second case, all elements of the tuple are the same, so that adding them all up will result in a multiple of $n$ once more, making it divisible.



    I am lost however on what to do in the third case, where the two above are not true. I would truly appreciate your input.










    share|cite|improve this question











    $endgroup$















      2












      2








      2


      0



      $begingroup$


      I am struggling with the following task:



      Be $n in N$ and $(a_1, a_2, ldots, a_n) in mathbb{Z}^n$. Prove that there is always $i, j in underline{n}$, with $i≤j$, so that $sum_{k=i}^j a_k$ is divisible by n.



      My first idea was to use a distinction of cases. In the first case a multiple of n is an element of $mathbb{Z}^n$ so you could select the sum to be just this element so it would obviously be divisible.



      In the second case, all elements of the tuple are the same, so that adding them all up will result in a multiple of $n$ once more, making it divisible.



      I am lost however on what to do in the third case, where the two above are not true. I would truly appreciate your input.










      share|cite|improve this question











      $endgroup$




      I am struggling with the following task:



      Be $n in N$ and $(a_1, a_2, ldots, a_n) in mathbb{Z}^n$. Prove that there is always $i, j in underline{n}$, with $i≤j$, so that $sum_{k=i}^j a_k$ is divisible by n.



      My first idea was to use a distinction of cases. In the first case a multiple of n is an element of $mathbb{Z}^n$ so you could select the sum to be just this element so it would obviously be divisible.



      In the second case, all elements of the tuple are the same, so that adding them all up will result in a multiple of $n$ once more, making it divisible.



      I am lost however on what to do in the third case, where the two above are not true. I would truly appreciate your input.







      elementary-number-theory discrete-mathematics divisibility






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 13 '18 at 14:12









      rtybase

      10.9k21533




      10.9k21533










      asked Dec 13 '18 at 12:11









      JulianGiJulianGi

      111




      111






















          2 Answers
          2






          active

          oldest

          votes


















          3












          $begingroup$

          Some elements of $(a_1, a_2, ldots, a_n)$ may be different and it need not contain a multiple of $n$ of course. (it is chosen just randomly from $mathbb{Z}^n$.)



          You need a little trick to solve this problem in an easy way. Consider $n$ values
          $$
          a_1, a_1+a_2, a_1+a_2+a_3, ldots , a_1+a_2 +cdots a_n.
          $$
          If at least one of them is a multiple of $n$, it's okay. If not, what can be said about their remainders divided by $n$?






          share|cite|improve this answer











          $endgroup$









          • 1




            $begingroup$
            I think we have almost identical answers (+1).
            $endgroup$
            – rtybase
            Dec 13 '18 at 12:31



















          2












          $begingroup$

          Using pigeonhole principle, let's look at all the remainders of
          $$a_1 pmod{n}$$
          $$a_1+a_2pmod{n}$$
          $$a_1+a_2+a_3pmod{n}$$
          $$...$$
          $$a_1+a_2+a_3+...+a_npmod{n}$$
          If at least one is $0$, we are done.



          If none is $0$, then at least $2$ will have the same value (there will be $n$ remainders, taking $n-1$ possible values within ${1,...,n-1}$, pigeonhole principle). E.g.
          $$a_1+a_2+a_3+...+a_j equiv a_1+a_2+a_3+...+a_i pmod{n}$$
          The remaining part is to subtract, assume $i<j$



          $$(a_1+a_2+a_3+...+a_j)- (a_1+a_2+a_3+...+a_i)equiv 0 pmod{n}$$
          or
          $$a_{j+1}+a_{j+2}+a_{j+3}+...+a_iequiv 0 pmod{n}$$






          share|cite|improve this answer











          $endgroup$









          • 1




            $begingroup$
            This is very extensive and well written. Thanks!
            $endgroup$
            – Empty2k12
            Dec 13 '18 at 12:59










          • $begingroup$
            Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 13:46








          • 1




            $begingroup$
            @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
            $endgroup$
            – rtybase
            Dec 13 '18 at 14:01








          • 1




            $begingroup$
            @rtybase That makes a lot of sense. Thank you very much.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 14:07













          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%2f3037922%2fsum-of-freely-chosen-subset-of-n-tuple-is-divisible-by-n%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









          3












          $begingroup$

          Some elements of $(a_1, a_2, ldots, a_n)$ may be different and it need not contain a multiple of $n$ of course. (it is chosen just randomly from $mathbb{Z}^n$.)



          You need a little trick to solve this problem in an easy way. Consider $n$ values
          $$
          a_1, a_1+a_2, a_1+a_2+a_3, ldots , a_1+a_2 +cdots a_n.
          $$
          If at least one of them is a multiple of $n$, it's okay. If not, what can be said about their remainders divided by $n$?






          share|cite|improve this answer











          $endgroup$









          • 1




            $begingroup$
            I think we have almost identical answers (+1).
            $endgroup$
            – rtybase
            Dec 13 '18 at 12:31
















          3












          $begingroup$

          Some elements of $(a_1, a_2, ldots, a_n)$ may be different and it need not contain a multiple of $n$ of course. (it is chosen just randomly from $mathbb{Z}^n$.)



          You need a little trick to solve this problem in an easy way. Consider $n$ values
          $$
          a_1, a_1+a_2, a_1+a_2+a_3, ldots , a_1+a_2 +cdots a_n.
          $$
          If at least one of them is a multiple of $n$, it's okay. If not, what can be said about their remainders divided by $n$?






          share|cite|improve this answer











          $endgroup$









          • 1




            $begingroup$
            I think we have almost identical answers (+1).
            $endgroup$
            – rtybase
            Dec 13 '18 at 12:31














          3












          3








          3





          $begingroup$

          Some elements of $(a_1, a_2, ldots, a_n)$ may be different and it need not contain a multiple of $n$ of course. (it is chosen just randomly from $mathbb{Z}^n$.)



          You need a little trick to solve this problem in an easy way. Consider $n$ values
          $$
          a_1, a_1+a_2, a_1+a_2+a_3, ldots , a_1+a_2 +cdots a_n.
          $$
          If at least one of them is a multiple of $n$, it's okay. If not, what can be said about their remainders divided by $n$?






          share|cite|improve this answer











          $endgroup$



          Some elements of $(a_1, a_2, ldots, a_n)$ may be different and it need not contain a multiple of $n$ of course. (it is chosen just randomly from $mathbb{Z}^n$.)



          You need a little trick to solve this problem in an easy way. Consider $n$ values
          $$
          a_1, a_1+a_2, a_1+a_2+a_3, ldots , a_1+a_2 +cdots a_n.
          $$
          If at least one of them is a multiple of $n$, it's okay. If not, what can be said about their remainders divided by $n$?







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 13 '18 at 12:24

























          answered Dec 13 '18 at 12:16









          SongSong

          12.2k630




          12.2k630








          • 1




            $begingroup$
            I think we have almost identical answers (+1).
            $endgroup$
            – rtybase
            Dec 13 '18 at 12:31














          • 1




            $begingroup$
            I think we have almost identical answers (+1).
            $endgroup$
            – rtybase
            Dec 13 '18 at 12:31








          1




          1




          $begingroup$
          I think we have almost identical answers (+1).
          $endgroup$
          – rtybase
          Dec 13 '18 at 12:31




          $begingroup$
          I think we have almost identical answers (+1).
          $endgroup$
          – rtybase
          Dec 13 '18 at 12:31











          2












          $begingroup$

          Using pigeonhole principle, let's look at all the remainders of
          $$a_1 pmod{n}$$
          $$a_1+a_2pmod{n}$$
          $$a_1+a_2+a_3pmod{n}$$
          $$...$$
          $$a_1+a_2+a_3+...+a_npmod{n}$$
          If at least one is $0$, we are done.



          If none is $0$, then at least $2$ will have the same value (there will be $n$ remainders, taking $n-1$ possible values within ${1,...,n-1}$, pigeonhole principle). E.g.
          $$a_1+a_2+a_3+...+a_j equiv a_1+a_2+a_3+...+a_i pmod{n}$$
          The remaining part is to subtract, assume $i<j$



          $$(a_1+a_2+a_3+...+a_j)- (a_1+a_2+a_3+...+a_i)equiv 0 pmod{n}$$
          or
          $$a_{j+1}+a_{j+2}+a_{j+3}+...+a_iequiv 0 pmod{n}$$






          share|cite|improve this answer











          $endgroup$









          • 1




            $begingroup$
            This is very extensive and well written. Thanks!
            $endgroup$
            – Empty2k12
            Dec 13 '18 at 12:59










          • $begingroup$
            Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 13:46








          • 1




            $begingroup$
            @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
            $endgroup$
            – rtybase
            Dec 13 '18 at 14:01








          • 1




            $begingroup$
            @rtybase That makes a lot of sense. Thank you very much.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 14:07


















          2












          $begingroup$

          Using pigeonhole principle, let's look at all the remainders of
          $$a_1 pmod{n}$$
          $$a_1+a_2pmod{n}$$
          $$a_1+a_2+a_3pmod{n}$$
          $$...$$
          $$a_1+a_2+a_3+...+a_npmod{n}$$
          If at least one is $0$, we are done.



          If none is $0$, then at least $2$ will have the same value (there will be $n$ remainders, taking $n-1$ possible values within ${1,...,n-1}$, pigeonhole principle). E.g.
          $$a_1+a_2+a_3+...+a_j equiv a_1+a_2+a_3+...+a_i pmod{n}$$
          The remaining part is to subtract, assume $i<j$



          $$(a_1+a_2+a_3+...+a_j)- (a_1+a_2+a_3+...+a_i)equiv 0 pmod{n}$$
          or
          $$a_{j+1}+a_{j+2}+a_{j+3}+...+a_iequiv 0 pmod{n}$$






          share|cite|improve this answer











          $endgroup$









          • 1




            $begingroup$
            This is very extensive and well written. Thanks!
            $endgroup$
            – Empty2k12
            Dec 13 '18 at 12:59










          • $begingroup$
            Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 13:46








          • 1




            $begingroup$
            @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
            $endgroup$
            – rtybase
            Dec 13 '18 at 14:01








          • 1




            $begingroup$
            @rtybase That makes a lot of sense. Thank you very much.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 14:07
















          2












          2








          2





          $begingroup$

          Using pigeonhole principle, let's look at all the remainders of
          $$a_1 pmod{n}$$
          $$a_1+a_2pmod{n}$$
          $$a_1+a_2+a_3pmod{n}$$
          $$...$$
          $$a_1+a_2+a_3+...+a_npmod{n}$$
          If at least one is $0$, we are done.



          If none is $0$, then at least $2$ will have the same value (there will be $n$ remainders, taking $n-1$ possible values within ${1,...,n-1}$, pigeonhole principle). E.g.
          $$a_1+a_2+a_3+...+a_j equiv a_1+a_2+a_3+...+a_i pmod{n}$$
          The remaining part is to subtract, assume $i<j$



          $$(a_1+a_2+a_3+...+a_j)- (a_1+a_2+a_3+...+a_i)equiv 0 pmod{n}$$
          or
          $$a_{j+1}+a_{j+2}+a_{j+3}+...+a_iequiv 0 pmod{n}$$






          share|cite|improve this answer











          $endgroup$



          Using pigeonhole principle, let's look at all the remainders of
          $$a_1 pmod{n}$$
          $$a_1+a_2pmod{n}$$
          $$a_1+a_2+a_3pmod{n}$$
          $$...$$
          $$a_1+a_2+a_3+...+a_npmod{n}$$
          If at least one is $0$, we are done.



          If none is $0$, then at least $2$ will have the same value (there will be $n$ remainders, taking $n-1$ possible values within ${1,...,n-1}$, pigeonhole principle). E.g.
          $$a_1+a_2+a_3+...+a_j equiv a_1+a_2+a_3+...+a_i pmod{n}$$
          The remaining part is to subtract, assume $i<j$



          $$(a_1+a_2+a_3+...+a_j)- (a_1+a_2+a_3+...+a_i)equiv 0 pmod{n}$$
          or
          $$a_{j+1}+a_{j+2}+a_{j+3}+...+a_iequiv 0 pmod{n}$$







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 13 '18 at 14:07

























          answered Dec 13 '18 at 12:21









          rtybasertybase

          10.9k21533




          10.9k21533








          • 1




            $begingroup$
            This is very extensive and well written. Thanks!
            $endgroup$
            – Empty2k12
            Dec 13 '18 at 12:59










          • $begingroup$
            Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 13:46








          • 1




            $begingroup$
            @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
            $endgroup$
            – rtybase
            Dec 13 '18 at 14:01








          • 1




            $begingroup$
            @rtybase That makes a lot of sense. Thank you very much.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 14:07
















          • 1




            $begingroup$
            This is very extensive and well written. Thanks!
            $endgroup$
            – Empty2k12
            Dec 13 '18 at 12:59










          • $begingroup$
            Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 13:46








          • 1




            $begingroup$
            @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
            $endgroup$
            – rtybase
            Dec 13 '18 at 14:01








          • 1




            $begingroup$
            @rtybase That makes a lot of sense. Thank you very much.
            $endgroup$
            – JulianGi
            Dec 13 '18 at 14:07










          1




          1




          $begingroup$
          This is very extensive and well written. Thanks!
          $endgroup$
          – Empty2k12
          Dec 13 '18 at 12:59




          $begingroup$
          This is very extensive and well written. Thanks!
          $endgroup$
          – Empty2k12
          Dec 13 '18 at 12:59












          $begingroup$
          Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
          $endgroup$
          – JulianGi
          Dec 13 '18 at 13:46






          $begingroup$
          Thanks for your answer. Now I understand how this works. However I have trouble to understand how you reach the conclusion, that "If none is 0, then at least 2 will have the same value". If this would be given the rest of your calculations fall into place.
          $endgroup$
          – JulianGi
          Dec 13 '18 at 13:46






          1




          1




          $begingroup$
          @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
          $endgroup$
          – rtybase
          Dec 13 '18 at 14:01






          $begingroup$
          @JulianGi recall divisibility, remainder is $0leq r <n$. We excluded $0$ so $1leq r <n$ or we have $n-1$ possible values from $1$ to $n-1$. The sequence constructed $a_1, a_1+a_2,...,a_1+a_2+...+a_n$ contains $n$ elements, taking the remainder of $pmod{n}$ yields $n$ remainders, taking values from $1$ to $n-1$. There is no one to one mapping between $n$ remainders taking values from ${1,2,...n-1}$ and ${1,2,...n-1}$, so "at least 2 (remainders) will have the same value ...".
          $endgroup$
          – rtybase
          Dec 13 '18 at 14:01






          1




          1




          $begingroup$
          @rtybase That makes a lot of sense. Thank you very much.
          $endgroup$
          – JulianGi
          Dec 13 '18 at 14:07






          $begingroup$
          @rtybase That makes a lot of sense. Thank you very much.
          $endgroup$
          – JulianGi
          Dec 13 '18 at 14:07




















          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%2f3037922%2fsum-of-freely-chosen-subset-of-n-tuple-is-divisible-by-n%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

          Wiesbaden

          Marschland

          Dieringhausen