Given any 2n-1 integers, prove that there are always n of them which add up to a multiple of n Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Use Pigeonhole to show of any set of $2^n+1-1$ positive integers is possible choose $2^n$ elements such that their sum is divisible by $2^n$.How many integers less than $300$ is such that the sum of any two of them is not divisible by $3$?Prove that the product of primes in some subset of $n+1$ integers is a perfect square.Solve $x^2=b mod m$ congruence equationsFrom any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect squareProve there are k consecutive non-squarefree integersUse Pigeonhole to show of any set of $2^n+1-1$ positive integers is possible choose $2^n$ elements such that their sum is divisible by $2^n$.Prove or disprove there exists a set of four numbers out of the $48$ positive integers of which product is a perfect squareGiven 7 arbitrary integers,sum of 4 of them is divisible by 4Integer pick with pigeon hole principleGiven any $n+2$ integers, show that there exist two of them whose sum, or else whose difference, is divisible by $2n$.
Does any scripture mention that forms of God or Goddess are symbolic?
Tips to organize LaTeX presentations for a semester
Special flights
Does the Mueller report show a conspiracy between Russia and the Trump Campaign?
Flight departed from the gate 5 min before scheduled departure time. Refund options
Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted?
Is CEO the "profession" with the most psychopaths?
How does the math work when buying airline miles?
Moving a wrapfig vertically to encroach partially on a subsection title
Printing attributes of selection in ArcPy?
Google .dev domain strangely redirects to https
GDP with Intermediate Production
A term for a woman complaining about things/begging in a cute/childish way
How to force a browser when connecting to a specific domain to be https only using only the client machine?
New Order #6: Easter Egg
In musical terms, what properties are varied by the human voice to produce different words / syllables?
Did any compiler fully use 80-bit floating point?
Random body shuffle every night—can we still function?
Co-worker has annoying ringtone
Why is it faster to reheat something than it is to cook it?
Why datecode is SO IMPORTANT to chip manufacturers?
I can't produce songs
Relating to the President and obstruction, were Mueller's conclusions preordained?
The test team as an enemy of development? And how can this be avoided?
Given any 2n-1 integers, prove that there are always n of them which add up to a multiple of n
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Use Pigeonhole to show of any set of $2^n+1-1$ positive integers is possible choose $2^n$ elements such that their sum is divisible by $2^n$.How many integers less than $300$ is such that the sum of any two of them is not divisible by $3$?Prove that the product of primes in some subset of $n+1$ integers is a perfect square.Solve $x^2=b mod m$ congruence equationsFrom any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect squareProve there are k consecutive non-squarefree integersUse Pigeonhole to show of any set of $2^n+1-1$ positive integers is possible choose $2^n$ elements such that their sum is divisible by $2^n$.Prove or disprove there exists a set of four numbers out of the $48$ positive integers of which product is a perfect squareGiven 7 arbitrary integers,sum of 4 of them is divisible by 4Integer pick with pigeon hole principleGiven any $n+2$ integers, show that there exist two of them whose sum, or else whose difference, is divisible by $2n$.
$begingroup$
This is a question I have been trying to solve for days. I feel as though there MUST be some application of the pigeon-hole principle.
Firstly, let us use congruence classes modulo n, as it simplifies the situation.
Now the question is:
From any "assortment" of $2n-1$ numbers in $[0,1,2,3...(n-1)]$ is there a "sub-assortment" of n numbers $[a_0,a_1,a_2,...a_n]$ such that
$a_0+a_1... a_n equiv 0$ mod n
Now, to see some examples of such a "sub-assortment":
There are 2 possible assortments of 2 numbers which add up to a multiple of 2:
$[0,0],[1,1]$
There are 4 possible assortments of 3 numbers which add up to a multiple of 3: $[0,0,0],[1,1,1],[2,2,2],[0,1,2]$
There are 8 possible assortments of 4 numbers which add up to a multiple of 4: $[0,0,0,0],[1,1,1,1],[2,2,2,2],[3,3,3,3],[0,0,2,2],[0,0,1,3],[0,2,2,3],[0,1,1,2]$
It seems as if there are always $2^n-1$ assortments of $n$ integers which add up to a multiple of $n$ (Though I cannot seem to prove it.)
Using the "stars and bars" approach we know there are $2n-1choosen$ different ways of selecting ANY assortment of $n$ integers mod n. (If you have not heard of this, look up the numberphile youtube video of the same name.)
This is because the "bars" represent the dividers between congruence classes
Thus, if there was a way to choose $2n-1$ integers so than NO $n$ integers have the property (of their some being $equiv 0$) there could not be more than $2n-1choose n$ $-2^n-1$ different assortments of n integers to select, or else on of them would have to have the property.
Furthermore, we know any "non-trivial" assortment of $2n-1$ integers mod n must contain at-least 3 different congruences in it, or there would be $n$ of one conguence which would form a trivial solution.
Now, I cannot drive home the solution. I do not know if I am tantalizingly close or far off. Can someone help by either:
- Proving the claim made above
- Providing a different approach
- Giving me a hint on how to finish this approach
elementary-number-theory pigeonhole-principle
asked Apr 2 at 8:37
amanaman
33611
$endgroup$
add a comment |
$begingroup$
This is a question I have been trying to solve for days. I feel as though there MUST be some application of the pigeon-hole principle.
Firstly, let us use congruence classes modulo n, as it simplifies the situation.
Now the question is:
From any "assortment" of $2n-1$ numbers in $[0,1,2,3...(n-1)]$ is there a "sub-assortment" of n numbers $[a_0,a_1,a_2,...a_n]$ such that
$a_0+a_1... a_n equiv 0$ mod n
Now, to see some examples of such a "sub-assortment":
There are 2 possible assortments of 2 numbers which add up to a multiple of 2:
$[0,0],[1,1]$
There are 4 possible assortments of 3 numbers which add up to a multiple of 3: $[0,0,0],[1,1,1],[2,2,2],[0,1,2]$
There are 8 possible assortments of 4 numbers which add up to a multiple of 4: $[0,0,0,0],[1,1,1,1],[2,2,2,2],[3,3,3,3],[0,0,2,2],[0,0,1,3],[0,2,2,3],[0,1,1,2]$
It seems as if there are always $2^n-1$ assortments of $n$ integers which add up to a multiple of $n$ (Though I cannot seem to prove it.)
Using the "stars and bars" approach we know there are $2n-1choosen$ different ways of selecting ANY assortment of $n$ integers mod n. (If you have not heard of this, look up the numberphile youtube video of the same name.)
This is because the "bars" represent the dividers between congruence classes
Thus, if there was a way to choose $2n-1$ integers so than NO $n$ integers have the property (of their some being $equiv 0$) there could not be more than $2n-1choose n$ $-2^n-1$ different assortments of n integers to select, or else on of them would have to have the property.
Furthermore, we know any "non-trivial" assortment of $2n-1$ integers mod n must contain at-least 3 different congruences in it, or there would be $n$ of one conguence which would form a trivial solution.
Now, I cannot drive home the solution. I do not know if I am tantalizingly close or far off. Can someone help by either:
- Proving the claim made above
- Providing a different approach
- Giving me a hint on how to finish this approach
elementary-number-theory pigeonhole-principle
asked Apr 2 at 8:37
amanaman
33611
$endgroup$
1
$begingroup$
I've noticed that your examples include $0$ but in the beginning you said the numbers are in $1,2,ldots,(n-1)$, so I suspect there is a typo. :) Your question seems that is the Erdős–Ginzburg–Ziv theorem. See also a related question for $2^n$ case.
$endgroup$
– Ertxiem
Apr 2 at 9:30
$begingroup$
I have corrected it.
$endgroup$
– aman
Apr 2 at 9:46
$begingroup$
@Ertxiem Wow! That is such a cool approach by induction.
$endgroup$
– aman
Apr 2 at 9:48
$begingroup$
@Ertxiem, Is there a simple proof of that theorem?
$endgroup$
– aman
Apr 2 at 10:00
$begingroup$
I don't know, but the original 1961 paper can be found online.
$endgroup$
– Ertxiem
Apr 2 at 10:08
add a comment |
$begingroup$
This is a question I have been trying to solve for days. I feel as though there MUST be some application of the pigeon-hole principle.
Firstly, let us use congruence classes modulo n, as it simplifies the situation.
Now the question is:
From any "assortment" of $2n-1$ numbers in $[0,1,2,3...(n-1)]$ is there a "sub-assortment" of n numbers $[a_0,a_1,a_2,...a_n]$ such that
$a_0+a_1... a_n equiv 0$ mod n
Now, to see some examples of such a "sub-assortment":
There are 2 possible assortments of 2 numbers which add up to a multiple of 2:
$[0,0],[1,1]$
There are 4 possible assortments of 3 numbers which add up to a multiple of 3: $[0,0,0],[1,1,1],[2,2,2],[0,1,2]$
There are 8 possible assortments of 4 numbers which add up to a multiple of 4: $[0,0,0,0],[1,1,1,1],[2,2,2,2],[3,3,3,3],[0,0,2,2],[0,0,1,3],[0,2,2,3],[0,1,1,2]$
It seems as if there are always $2^n-1$ assortments of $n$ integers which add up to a multiple of $n$ (Though I cannot seem to prove it.)
Using the "stars and bars" approach we know there are $2n-1choosen$ different ways of selecting ANY assortment of $n$ integers mod n. (If you have not heard of this, look up the numberphile youtube video of the same name.)
This is because the "bars" represent the dividers between congruence classes
Thus, if there was a way to choose $2n-1$ integers so than NO $n$ integers have the property (of their some being $equiv 0$) there could not be more than $2n-1choose n$ $-2^n-1$ different assortments of n integers to select, or else on of them would have to have the property.
Furthermore, we know any "non-trivial" assortment of $2n-1$ integers mod n must contain at-least 3 different congruences in it, or there would be $n$ of one conguence which would form a trivial solution.
Now, I cannot drive home the solution. I do not know if I am tantalizingly close or far off. Can someone help by either:
- Proving the claim made above
- Providing a different approach
- Giving me a hint on how to finish this approach
elementary-number-theory pigeonhole-principle
asked Apr 2 at 8:37
amanaman
33611
$endgroup$
This is a question I have been trying to solve for days. I feel as though there MUST be some application of the pigeon-hole principle.
Firstly, let us use congruence classes modulo n, as it simplifies the situation.
Now the question is:
From any "assortment" of $2n-1$ numbers in $[0,1,2,3...(n-1)]$ is there a "sub-assortment" of n numbers $[a_0,a_1,a_2,...a_n]$ such that
$a_0+a_1... a_n equiv 0$ mod n
Now, to see some examples of such a "sub-assortment":
There are 2 possible assortments of 2 numbers which add up to a multiple of 2:
$[0,0],[1,1]$
There are 4 possible assortments of 3 numbers which add up to a multiple of 3: $[0,0,0],[1,1,1],[2,2,2],[0,1,2]$
There are 8 possible assortments of 4 numbers which add up to a multiple of 4: $[0,0,0,0],[1,1,1,1],[2,2,2,2],[3,3,3,3],[0,0,2,2],[0,0,1,3],[0,2,2,3],[0,1,1,2]$
It seems as if there are always $2^n-1$ assortments of $n$ integers which add up to a multiple of $n$ (Though I cannot seem to prove it.)
Using the "stars and bars" approach we know there are $2n-1choosen$ different ways of selecting ANY assortment of $n$ integers mod n. (If you have not heard of this, look up the numberphile youtube video of the same name.)
This is because the "bars" represent the dividers between congruence classes
Thus, if there was a way to choose $2n-1$ integers so than NO $n$ integers have the property (of their some being $equiv 0$) there could not be more than $2n-1choose n$ $-2^n-1$ different assortments of n integers to select, or else on of them would have to have the property.
Furthermore, we know any "non-trivial" assortment of $2n-1$ integers mod n must contain at-least 3 different congruences in it, or there would be $n$ of one conguence which would form a trivial solution.
Now, I cannot drive home the solution. I do not know if I am tantalizingly close or far off. Can someone help by either:
- Proving the claim made above
- Providing a different approach
- Giving me a hint on how to finish this approach
elementary-number-theory pigeonhole-principle
elementary-number-theory pigeonhole-principle
asked Apr 2 at 8:37
amanaman
33611
asked Apr 2 at 8:37
amanaman
33611
edited Apr 2 at 9:46
aman
asked Apr 2 at 8:37
amanaman
33611
asked Apr 2 at 8:37
amanaman
33611
asked Apr 2 at 8:37
amanaman
33611
33611
1
$begingroup$
I've noticed that your examples include $0$ but in the beginning you said the numbers are in $1,2,ldots,(n-1)$, so I suspect there is a typo. :) Your question seems that is the Erdős–Ginzburg–Ziv theorem. See also a related question for $2^n$ case.
$endgroup$
– Ertxiem
Apr 2 at 9:30
$begingroup$
I have corrected it.
$endgroup$
– aman
Apr 2 at 9:46
$begingroup$
@Ertxiem Wow! That is such a cool approach by induction.
$endgroup$
– aman
Apr 2 at 9:48
$begingroup$
@Ertxiem, Is there a simple proof of that theorem?
$endgroup$
– aman
Apr 2 at 10:00
$begingroup$
I don't know, but the original 1961 paper can be found online.
$endgroup$
– Ertxiem
Apr 2 at 10:08
add a comment |
1
$begingroup$
I've noticed that your examples include $0$ but in the beginning you said the numbers are in $1,2,ldots,(n-1)$, so I suspect there is a typo. :) Your question seems that is the Erdős–Ginzburg–Ziv theorem. See also a related question for $2^n$ case.
$endgroup$
– Ertxiem
Apr 2 at 9:30
$begingroup$
I have corrected it.
$endgroup$
– aman
Apr 2 at 9:46
$begingroup$
@Ertxiem Wow! That is such a cool approach by induction.
$endgroup$
– aman
Apr 2 at 9:48
$begingroup$
@Ertxiem, Is there a simple proof of that theorem?
$endgroup$
– aman
Apr 2 at 10:00
$begingroup$
I don't know, but the original 1961 paper can be found online.
$endgroup$
– Ertxiem
Apr 2 at 10:08
1
1
$begingroup$
I've noticed that your examples include $0$ but in the beginning you said the numbers are in $1,2,ldots,(n-1)$, so I suspect there is a typo. :) Your question seems that is the Erdős–Ginzburg–Ziv theorem. See also a related question for $2^n$ case.
$endgroup$
– Ertxiem
Apr 2 at 9:30
$begingroup$
I've noticed that your examples include $0$ but in the beginning you said the numbers are in $1,2,ldots,(n-1)$, so I suspect there is a typo. :) Your question seems that is the Erdős–Ginzburg–Ziv theorem. See also a related question for $2^n$ case.
$endgroup$
– Ertxiem
Apr 2 at 9:30
$begingroup$
I have corrected it.
$endgroup$
– aman
Apr 2 at 9:46
$begingroup$
I have corrected it.
$endgroup$
– aman
Apr 2 at 9:46
$begingroup$
@Ertxiem Wow! That is such a cool approach by induction.
$endgroup$
– aman
Apr 2 at 9:48
$begingroup$
@Ertxiem Wow! That is such a cool approach by induction.
$endgroup$
– aman
Apr 2 at 9:48
$begingroup$
@Ertxiem, Is there a simple proof of that theorem?
$endgroup$
– aman
Apr 2 at 10:00
$begingroup$
@Ertxiem, Is there a simple proof of that theorem?
$endgroup$
– aman
Apr 2 at 10:00
$begingroup$
I don't know, but the original 1961 paper can be found online.
$endgroup$
– Ertxiem
Apr 2 at 10:08
$begingroup$
I don't know, but the original 1961 paper can be found online.
$endgroup$
– Ertxiem
Apr 2 at 10:08
add a comment |
0
active
oldest
votes
Your Answer
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%2f3171625%2fgiven-any-2n-1-integers-prove-that-there-are-always-n-of-them-which-add-up-to-a%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3171625%2fgiven-any-2n-1-integers-prove-that-there-are-always-n-of-them-which-add-up-to-a%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
1
$begingroup$
I've noticed that your examples include $0$ but in the beginning you said the numbers are in $1,2,ldots,(n-1)$, so I suspect there is a typo. :) Your question seems that is the Erdős–Ginzburg–Ziv theorem. See also a related question for $2^n$ case.
$endgroup$
– Ertxiem
Apr 2 at 9:30
$begingroup$
I have corrected it.
$endgroup$
– aman
Apr 2 at 9:46
$begingroup$
@Ertxiem Wow! That is such a cool approach by induction.
$endgroup$
– aman
Apr 2 at 9:48
$begingroup$
@Ertxiem, Is there a simple proof of that theorem?
$endgroup$
– aman
Apr 2 at 10:00
$begingroup$
I don't know, but the original 1961 paper can be found online.
$endgroup$
– Ertxiem
Apr 2 at 10:08