Pigeonhole Principle ProblemPigeonhole principle: 112 hrs over 12 days, then at least 19 hrs over some...
How to get SEEK accessing converted ID via view
Problems with numbers (result of calculations) alignment using siunitx package inside tabular environment
LT Spice Voltage Output
Survey Confirmation - Emphasize the question or the answer?
Write to EXCEL from SQL DB using VBA script
An 'if constexpr branch' does not get discarded inside lambda that is inside a template function
Can I use 1000v rectifier diodes instead of 600v rectifier diodes?
Is there a QGIS plugin that reclassify raster symbology based on current extent?
Can a cyclic Amine form an Amide?
How to creep the reader out with what seems like a normal person?
How did Captain America use this power?
What happens if I start too many background jobs?
Feels like I am getting dragged into office politics
If Earth is tilted, why is Polaris always above the same spot?
I caught several of my students plagiarizing. Could it be my fault as a teacher?
When do aircrafts become solarcrafts?
Visualizing a complicated Region
How do I tell my manager that his code review comment is wrong?
Game of Life meets Chaos Theory
Why is the SNP putting so much emphasis on currency plans?
Historically, were women trained for obligatory wars? Or did they serve some other military function?
What was the state of the German rail system in 1944?
If 1. e4 c6 is considered as a sound defense for black, why is 1. c3 so rare?
Why is Arya visibly scared in the library in S8E3?
Pigeonhole Principle Problem
Pigeonhole principle: 112 hrs over 12 days, then at least 19 hrs over some consecutive 2 daysPigeonhole-principle with two choicesPigeonhole problem - salvaging my solutionProblem on pigeon hole principleTricky pigeonhole principle questionPigeonhole Principle Question: Jessica the Combinatorics StudentJessica the Combinatorics Student, part 2Pigeonhole problem involving team playing 14 consecutive gamesDifferent approach to classic pigeonhole principle problem yields different results. Why?(Generalised) pigeonhole principle
$begingroup$
Problem: In the following 30 days you will get 46 homework sets out of which you will do at least one every day and - of course - all during the 30 days. Show that there must be a period of consecutive days during which you will do exactly 10 homework sets!
Solution: Let $f_n$ denote the number of homeworks from day $1$ to day $n$, where $nle 30$. So, let us consider from $f_1$ up to $f_{11}$. There are ten possibilities for the remainder when each is divided by $10$. By the pigeonhole principle, there must exist two that have the same remainder, call these $f_i$ and $f_j$, for some $i,jin [1,11]$. Therefore $$f_i - f_j equiv 0 pmod{10}.$$ But also $f_i - f_j not = 20$. Hence $f_i - f_j = 10$.
I think this is on the right track. However, I have not convinced myself that $f_i - f_j not = 20$
pigeonhole-principle
asked 4 hours ago
WesleyWesley
646613
$endgroup$
add a comment |
$begingroup$
Problem: In the following 30 days you will get 46 homework sets out of which you will do at least one every day and - of course - all during the 30 days. Show that there must be a period of consecutive days during which you will do exactly 10 homework sets!
Solution: Let $f_n$ denote the number of homeworks from day $1$ to day $n$, where $nle 30$. So, let us consider from $f_1$ up to $f_{11}$. There are ten possibilities for the remainder when each is divided by $10$. By the pigeonhole principle, there must exist two that have the same remainder, call these $f_i$ and $f_j$, for some $i,jin [1,11]$. Therefore $$f_i - f_j equiv 0 pmod{10}.$$ But also $f_i - f_j not = 20$. Hence $f_i - f_j = 10$.
I think this is on the right track. However, I have not convinced myself that $f_i - f_j not = 20$
pigeonhole-principle
asked 4 hours ago
WesleyWesley
646613
$endgroup$
1
$begingroup$
I don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice.
$endgroup$
– Robert Shore
4 hours ago
add a comment |
$begingroup$
Problem: In the following 30 days you will get 46 homework sets out of which you will do at least one every day and - of course - all during the 30 days. Show that there must be a period of consecutive days during which you will do exactly 10 homework sets!
Solution: Let $f_n$ denote the number of homeworks from day $1$ to day $n$, where $nle 30$. So, let us consider from $f_1$ up to $f_{11}$. There are ten possibilities for the remainder when each is divided by $10$. By the pigeonhole principle, there must exist two that have the same remainder, call these $f_i$ and $f_j$, for some $i,jin [1,11]$. Therefore $$f_i - f_j equiv 0 pmod{10}.$$ But also $f_i - f_j not = 20$. Hence $f_i - f_j = 10$.
I think this is on the right track. However, I have not convinced myself that $f_i - f_j not = 20$
pigeonhole-principle
asked 4 hours ago
WesleyWesley
646613
$endgroup$
Problem: In the following 30 days you will get 46 homework sets out of which you will do at least one every day and - of course - all during the 30 days. Show that there must be a period of consecutive days during which you will do exactly 10 homework sets!
Solution: Let $f_n$ denote the number of homeworks from day $1$ to day $n$, where $nle 30$. So, let us consider from $f_1$ up to $f_{11}$. There are ten possibilities for the remainder when each is divided by $10$. By the pigeonhole principle, there must exist two that have the same remainder, call these $f_i$ and $f_j$, for some $i,jin [1,11]$. Therefore $$f_i - f_j equiv 0 pmod{10}.$$ But also $f_i - f_j not = 20$. Hence $f_i - f_j = 10$.
I think this is on the right track. However, I have not convinced myself that $f_i - f_j not = 20$
pigeonhole-principle
pigeonhole-principle
asked 4 hours ago
WesleyWesley
646613
asked 4 hours ago
WesleyWesley
646613
asked 4 hours ago
WesleyWesley
646613
asked 4 hours ago
WesleyWesley
646613
asked 4 hours ago
WesleyWesley
646613
646613
1
$begingroup$
I don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice.
$endgroup$
– Robert Shore
4 hours ago
add a comment |
1
$begingroup$
I don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice.
$endgroup$
– Robert Shore
4 hours ago
1
1
$begingroup$
I don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice.
$endgroup$
– Robert Shore
4 hours ago
$begingroup$
I don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice.
$endgroup$
– Robert Shore
4 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In fact, you would have to consider the case where $f_i-f_j=20$. Which might be messy...
You could alternatively do the following: we know that $$1le f_1<f_2<ldots<f_{30}=46iff 11le f_1+10<f_2+10<ldots <f_{30}+10=56$$ Observe know that we are considering $60$ postive integers $f_1,f_2,ldots ,f_{30},f_1+10,f_2+10,ldots , f_{30}+10$ where all of them are less than $57$. By the Pigeonhole principle, at least $2$ numbers must be equal.
Therefore, we must have one integer from the first inequality being equal to another integer from the second inequality. Hence $$f_i=f_j+10$$ for some $i,jinBbb N_{<31}$. Which is exactly what we wanted to prove.
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
$endgroup$
2
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
add a comment |
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%2f3207276%2fpigeonhole-principle-problem%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$
In fact, you would have to consider the case where $f_i-f_j=20$. Which might be messy...
You could alternatively do the following: we know that $$1le f_1<f_2<ldots<f_{30}=46iff 11le f_1+10<f_2+10<ldots <f_{30}+10=56$$ Observe know that we are considering $60$ postive integers $f_1,f_2,ldots ,f_{30},f_1+10,f_2+10,ldots , f_{30}+10$ where all of them are less than $57$. By the Pigeonhole principle, at least $2$ numbers must be equal.
Therefore, we must have one integer from the first inequality being equal to another integer from the second inequality. Hence $$f_i=f_j+10$$ for some $i,jinBbb N_{<31}$. Which is exactly what we wanted to prove.
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
$endgroup$
2
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
add a comment |
$begingroup$
In fact, you would have to consider the case where $f_i-f_j=20$. Which might be messy...
You could alternatively do the following: we know that $$1le f_1<f_2<ldots<f_{30}=46iff 11le f_1+10<f_2+10<ldots <f_{30}+10=56$$ Observe know that we are considering $60$ postive integers $f_1,f_2,ldots ,f_{30},f_1+10,f_2+10,ldots , f_{30}+10$ where all of them are less than $57$. By the Pigeonhole principle, at least $2$ numbers must be equal.
Therefore, we must have one integer from the first inequality being equal to another integer from the second inequality. Hence $$f_i=f_j+10$$ for some $i,jinBbb N_{<31}$. Which is exactly what we wanted to prove.
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
$endgroup$
2
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
add a comment |
$begingroup$
In fact, you would have to consider the case where $f_i-f_j=20$. Which might be messy...
You could alternatively do the following: we know that $$1le f_1<f_2<ldots<f_{30}=46iff 11le f_1+10<f_2+10<ldots <f_{30}+10=56$$ Observe know that we are considering $60$ postive integers $f_1,f_2,ldots ,f_{30},f_1+10,f_2+10,ldots , f_{30}+10$ where all of them are less than $57$. By the Pigeonhole principle, at least $2$ numbers must be equal.
Therefore, we must have one integer from the first inequality being equal to another integer from the second inequality. Hence $$f_i=f_j+10$$ for some $i,jinBbb N_{<31}$. Which is exactly what we wanted to prove.
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
$endgroup$
In fact, you would have to consider the case where $f_i-f_j=20$. Which might be messy...
You could alternatively do the following: we know that $$1le f_1<f_2<ldots<f_{30}=46iff 11le f_1+10<f_2+10<ldots <f_{30}+10=56$$ Observe know that we are considering $60$ postive integers $f_1,f_2,ldots ,f_{30},f_1+10,f_2+10,ldots , f_{30}+10$ where all of them are less than $57$. By the Pigeonhole principle, at least $2$ numbers must be equal.
Therefore, we must have one integer from the first inequality being equal to another integer from the second inequality. Hence $$f_i=f_j+10$$ for some $i,jinBbb N_{<31}$. Which is exactly what we wanted to prove.
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
answered 4 hours ago
Dr. MathvaDr. Mathva
3,8811630
3,8811630
2
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
add a comment |
2
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
2
2
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
$begingroup$
Nice ...............+1
$endgroup$
– Maria Mazur
4 hours ago
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%2f3207276%2fpigeonhole-principle-problem%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 don't think you can rule out the possibility that $f_i-f_j=20$. Fortunately, you don't have to. If that's the case, then do the same analysis with the next $11$ days. There aren't enough homework sets for you to hit $20$ twice.
$endgroup$
– Robert Shore
4 hours ago