Sum of freely chosen subset of $n$-tuple is divisible by $n$.
$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.
elementary-number-theory discrete-mathematics divisibility
$endgroup$
add a comment |
$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.
elementary-number-theory discrete-mathematics divisibility
$endgroup$
add a comment |
$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.
elementary-number-theory discrete-mathematics divisibility
$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
elementary-number-theory discrete-mathematics divisibility
edited Dec 13 '18 at 14:12
rtybase
11.1k21533
11.1k21533
asked Dec 13 '18 at 12:11
JulianGiJulianGi
111
111
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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$?
$endgroup$
1
$begingroup$
I think we have almost identical answers (+1).
$endgroup$
– rtybase
Dec 13 '18 at 12:31
add a comment |
$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}$$
$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
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%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
$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$?
$endgroup$
1
$begingroup$
I think we have almost identical answers (+1).
$endgroup$
– rtybase
Dec 13 '18 at 12:31
add a comment |
$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$?
$endgroup$
1
$begingroup$
I think we have almost identical answers (+1).
$endgroup$
– rtybase
Dec 13 '18 at 12:31
add a comment |
$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$?
$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$?
edited Dec 13 '18 at 12:24
answered Dec 13 '18 at 12:16
SongSong
16.2k1739
16.2k1739
1
$begingroup$
I think we have almost identical answers (+1).
$endgroup$
– rtybase
Dec 13 '18 at 12:31
add a comment |
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
add a comment |
$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}$$
$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
add a comment |
$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}$$
$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
add a comment |
$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}$$
$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}$$
edited Dec 13 '18 at 14:07
answered Dec 13 '18 at 12:21
rtybasertybase
11.1k21533
11.1k21533
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
add a comment |
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
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%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
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