Prove that there is a number that appears at least N times The 2019 Stack Overflow Developer Survey Results Are In$NtimesN$ chessboard, adjacent squares differ by oneUsing the pigeonhole principle to prove there is at least two groups of people whose age sums are the same.Twenty distinct integers are chosen from $1,2,…,69$ and their differencesChoose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.Show that there are at least 2 computers in the network … (Pigeonhole Principle)Mathematical induction and pigeon-hole principleInduction to prove that a set of $n+1$ integers between $1$ and $2n$ has at least one number which divides another number in the setconfusion in a combinatorics problem of IMO 2001Show that there are two distinct positive integers such that: $1394|2^a-2^b$Pigeon Hole Principle: 10 balls are partitioned to 5 people, someone has sum over 11Pigeon hole principle: Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Did Scotland spend $250,000 for the slogan "Welcome to Scotland"?
Why are there uneven bright areas in this photo of black hole?
What is the meaning of Triage in Cybersec world?
Getting crown tickets for Statue of Liberty
Output the Arecibo Message
Deal with toxic manager when you can't quit
How to support a colleague who finds meetings extremely tiring?
Match Roman Numerals
How can I define good in a religion that claims no moral authority?
How can I add encounters in the Lost Mine of Phandelver campaign without giving PCs too much XP?
Short story: man watches girlfriend's spaceship entering a 'black hole' (?) forever
What is the motivation for a law requiring 2 parties to consent for recording a conversation
Falsification in Math vs Science
Pokemon Turn Based battle (Python)
A female thief is not sold to make restitution -- so what happens instead?
Likelihood that a superbug or lethal virus could come from a landfill
Why doesn't UInt have a toDouble()?
Does adding complexity mean a more secure cipher?
Geography at the pixel level
ELI5: Why they say that Israel would have been the fourth country to land a spacecraft on the Moon and why they call it low cost?
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?
Ubuntu Server install with full GUI
Prove that there is a number that appears at least N times
The 2019 Stack Overflow Developer Survey Results Are In$NtimesN$ chessboard, adjacent squares differ by oneUsing the pigeonhole principle to prove there is at least two groups of people whose age sums are the same.Twenty distinct integers are chosen from $1,2,…,69$ and their differencesChoose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.Show that there are at least 2 computers in the network … (Pigeonhole Principle)Mathematical induction and pigeon-hole principleInduction to prove that a set of $n+1$ integers between $1$ and $2n$ has at least one number which divides another number in the setconfusion in a combinatorics problem of IMO 2001Show that there are two distinct positive integers such that: $1394|2^a-2^b$Pigeon Hole Principle: 10 balls are partitioned to 5 people, someone has sum over 11Pigeon hole principle: Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three.
$begingroup$
An $N times N$ table is filled with integers such that numbers in cells that share a side differ by at most 1. Prove that there is some number that appears in the table at least N times.
An example:
In the example the numbers 1 and 2 both appear at least 5 times.
I think this has something to do with the pigeon-hole principle. If you set one of the center most cells to 0.
In odd $N$ cases, the integers in all the other cells can vary between $[-n+1,+n-1]$.
In even $N$ cases, the integers in all the other cells can vary between $[-n,n]$.
In either case you can only show that some number appears at least $n/2$ times. It might also be induction, but I don't really know how to apply induction to this problem.
combinatorics pigeonhole-principle
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
$endgroup$
add a comment |
$begingroup$
An $N times N$ table is filled with integers such that numbers in cells that share a side differ by at most 1. Prove that there is some number that appears in the table at least N times.
An example:
In the example the numbers 1 and 2 both appear at least 5 times.
I think this has something to do with the pigeon-hole principle. If you set one of the center most cells to 0.
In odd $N$ cases, the integers in all the other cells can vary between $[-n+1,+n-1]$.
In even $N$ cases, the integers in all the other cells can vary between $[-n,n]$.
In either case you can only show that some number appears at least $n/2$ times. It might also be induction, but I don't really know how to apply induction to this problem.
combinatorics pigeonhole-principle
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
$endgroup$
$begingroup$
See also math.stackexchange.com/questions/2254667/… for a different solution.
$endgroup$
– Mike Earnest
8 hours ago
add a comment |
$begingroup$
An $N times N$ table is filled with integers such that numbers in cells that share a side differ by at most 1. Prove that there is some number that appears in the table at least N times.
An example:
In the example the numbers 1 and 2 both appear at least 5 times.
I think this has something to do with the pigeon-hole principle. If you set one of the center most cells to 0.
In odd $N$ cases, the integers in all the other cells can vary between $[-n+1,+n-1]$.
In even $N$ cases, the integers in all the other cells can vary between $[-n,n]$.
In either case you can only show that some number appears at least $n/2$ times. It might also be induction, but I don't really know how to apply induction to this problem.
combinatorics pigeonhole-principle
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
$endgroup$
An $N times N$ table is filled with integers such that numbers in cells that share a side differ by at most 1. Prove that there is some number that appears in the table at least N times.
An example:
In the example the numbers 1 and 2 both appear at least 5 times.
I think this has something to do with the pigeon-hole principle. If you set one of the center most cells to 0.
In odd $N$ cases, the integers in all the other cells can vary between $[-n+1,+n-1]$.
In even $N$ cases, the integers in all the other cells can vary between $[-n,n]$.
In either case you can only show that some number appears at least $n/2$ times. It might also be induction, but I don't really know how to apply induction to this problem.
combinatorics pigeonhole-principle
combinatorics pigeonhole-principle
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
edited Apr 8 at 2:00
Arvin Ding
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
asked Apr 8 at 1:54
Arvin DingArvin Ding
266
266
$begingroup$
See also math.stackexchange.com/questions/2254667/… for a different solution.
$endgroup$
– Mike Earnest
8 hours ago
add a comment |
$begingroup$
See also math.stackexchange.com/questions/2254667/… for a different solution.
$endgroup$
– Mike Earnest
8 hours ago
$begingroup$
See also math.stackexchange.com/questions/2254667/… for a different solution.
$endgroup$
– Mike Earnest
8 hours ago
$begingroup$
See also math.stackexchange.com/questions/2254667/… for a different solution.
$endgroup$
– Mike Earnest
8 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This question was also asked on Puzzling Stack Exchange: link. This answer is paraphrased from the top answer there.
The adjacency condition implies that the set of numbers appearing in each row is a contiguous interval of integers, $a,a+1,a+2,dots,b$. Let $[a_i,b_i]$ be the interval of numbers appearing in the $i^th$ row. Furthermore, let $a_max$ be the maximum value of the $a_i$'s, and let $b_min$ be the minimum of the $b_i$'s.
If $a_maxle b_min$, then every row contains a number less than or equal to $a_max$, and every row contains a number greater than or equal to $a_max$, so every row contains $a_max$.
If $a_max>b_min$, then suppose row $i$ is one for which $a_i=a_max$, and row $j$ is one for which $b_j=b_min$. Imagine starting in row $i$ in the $k^th$ column, and moving vertically to row $j$ in the $k^th$ column. You start at a value greater than or equal to $a_max$, end at a value less than or equal to $b_min$, so less than $a_max$, and hit every value in between. Therefore, the $k^th$ column contains $a_max$, so all columns contain $a_max$.
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
$endgroup$
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%2f3179038%2fprove-that-there-is-a-number-that-appears-at-least-n-times%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This question was also asked on Puzzling Stack Exchange: link. This answer is paraphrased from the top answer there.
The adjacency condition implies that the set of numbers appearing in each row is a contiguous interval of integers, $a,a+1,a+2,dots,b$. Let $[a_i,b_i]$ be the interval of numbers appearing in the $i^th$ row. Furthermore, let $a_max$ be the maximum value of the $a_i$'s, and let $b_min$ be the minimum of the $b_i$'s.
If $a_maxle b_min$, then every row contains a number less than or equal to $a_max$, and every row contains a number greater than or equal to $a_max$, so every row contains $a_max$.
If $a_max>b_min$, then suppose row $i$ is one for which $a_i=a_max$, and row $j$ is one for which $b_j=b_min$. Imagine starting in row $i$ in the $k^th$ column, and moving vertically to row $j$ in the $k^th$ column. You start at a value greater than or equal to $a_max$, end at a value less than or equal to $b_min$, so less than $a_max$, and hit every value in between. Therefore, the $k^th$ column contains $a_max$, so all columns contain $a_max$.
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
$endgroup$
add a comment |
$begingroup$
This question was also asked on Puzzling Stack Exchange: link. This answer is paraphrased from the top answer there.
The adjacency condition implies that the set of numbers appearing in each row is a contiguous interval of integers, $a,a+1,a+2,dots,b$. Let $[a_i,b_i]$ be the interval of numbers appearing in the $i^th$ row. Furthermore, let $a_max$ be the maximum value of the $a_i$'s, and let $b_min$ be the minimum of the $b_i$'s.
If $a_maxle b_min$, then every row contains a number less than or equal to $a_max$, and every row contains a number greater than or equal to $a_max$, so every row contains $a_max$.
If $a_max>b_min$, then suppose row $i$ is one for which $a_i=a_max$, and row $j$ is one for which $b_j=b_min$. Imagine starting in row $i$ in the $k^th$ column, and moving vertically to row $j$ in the $k^th$ column. You start at a value greater than or equal to $a_max$, end at a value less than or equal to $b_min$, so less than $a_max$, and hit every value in between. Therefore, the $k^th$ column contains $a_max$, so all columns contain $a_max$.
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
$endgroup$
add a comment |
$begingroup$
This question was also asked on Puzzling Stack Exchange: link. This answer is paraphrased from the top answer there.
The adjacency condition implies that the set of numbers appearing in each row is a contiguous interval of integers, $a,a+1,a+2,dots,b$. Let $[a_i,b_i]$ be the interval of numbers appearing in the $i^th$ row. Furthermore, let $a_max$ be the maximum value of the $a_i$'s, and let $b_min$ be the minimum of the $b_i$'s.
If $a_maxle b_min$, then every row contains a number less than or equal to $a_max$, and every row contains a number greater than or equal to $a_max$, so every row contains $a_max$.
If $a_max>b_min$, then suppose row $i$ is one for which $a_i=a_max$, and row $j$ is one for which $b_j=b_min$. Imagine starting in row $i$ in the $k^th$ column, and moving vertically to row $j$ in the $k^th$ column. You start at a value greater than or equal to $a_max$, end at a value less than or equal to $b_min$, so less than $a_max$, and hit every value in between. Therefore, the $k^th$ column contains $a_max$, so all columns contain $a_max$.
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
$endgroup$
This question was also asked on Puzzling Stack Exchange: link. This answer is paraphrased from the top answer there.
The adjacency condition implies that the set of numbers appearing in each row is a contiguous interval of integers, $a,a+1,a+2,dots,b$. Let $[a_i,b_i]$ be the interval of numbers appearing in the $i^th$ row. Furthermore, let $a_max$ be the maximum value of the $a_i$'s, and let $b_min$ be the minimum of the $b_i$'s.
If $a_maxle b_min$, then every row contains a number less than or equal to $a_max$, and every row contains a number greater than or equal to $a_max$, so every row contains $a_max$.
If $a_max>b_min$, then suppose row $i$ is one for which $a_i=a_max$, and row $j$ is one for which $b_j=b_min$. Imagine starting in row $i$ in the $k^th$ column, and moving vertically to row $j$ in the $k^th$ column. You start at a value greater than or equal to $a_max$, end at a value less than or equal to $b_min$, so less than $a_max$, and hit every value in between. Therefore, the $k^th$ column contains $a_max$, so all columns contain $a_max$.
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
answered Apr 8 at 21:36
Mike EarnestMike Earnest
27.6k22152
27.6k22152
add a comment |
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%2f3179038%2fprove-that-there-is-a-number-that-appears-at-least-n-times%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
See also math.stackexchange.com/questions/2254667/… for a different solution.
$endgroup$
– Mike Earnest
8 hours ago