Mfcttrf

New road bike: alloy dual pivot brakes work poorly

I cannot take my Macbook Pro 2015 in my Aegean/Lufthansa flight?

Why is a road bike faster than a city bike with the same effort? How much faster it can be?

Do wheelchair-accessible aircraft exist?

String whitespaces

Another student has been assigned the same MSc thesis as mine (and already defended)

My manager quit. Should I agree to defer wage increase to accommodate budget concerns?

Is differentiation as a map discontinuous?

Why does (inf + 0j)*1 evaluate to inf + nanj?

Two side-by-side squares are inscribed in a semicircle. The diameter of the semicircle is 16. What is the sum of the two squares' areas?

Why does my browser attempt to download pages from http://clhs.lisp.se instead of viewing them normally?

One-digit products in a row of numbers

How should I answer custom and border protection questions if I'm a returning citizen that hasn't been in the country for almost a decade?

What is the difference between an astronaut in the ISS and a freediver in perfect neutral buoyancy?

Help in drawing resonance structures in case of polybasic acids

Why isn't there armor to protect from spells in the Potterverse?

Does the app TikTok violate trademark?

Flowers sent by the birds

Received a package but didn't order it

What secular civic space would pioneers build for small frontier towns?

Number of list elements less than a given integer

Character Transformation

What exactly did this mechanic sabotage on the American Airlines 737, and how dangerous was it?

Why, even after his imprisonment, people keep calling Hannibal Lecter "Doctor"?

There are 51 natural numbers between 1-100, prove that there are 2 numbers such that the difference between them equals to 5

Prove that there exists a numbered socket such that for every orientation, two equal numbers coincidelet $A$ be a set of $n+1$ natural numbers between $1$ and $3n$. Show that there are $a,b in A$ such that $n leq a-b leq 2n$There are 12 children .Assuming there are 4 children’s bedrooms show that there are at least 3 children sleeping in at least one of them.Prove that there exists a multiple of $2016$, such that the multiple has only $4$ and $6$ as its digits.Prove there are $2$ numbers in a set whose difference is a multiple of $9$?How to prove that if $68$ numbers are selected from the set $1, 2, 3, ldots, 100$, then at least three must be consecutive

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

4

1

$begingroup$

This question relates to pigeonhole principle, but I couldn't find what the holes need to be. How should I prove this сlaim?

combinatorics pigeonhole-principle

share|cite|improve this question

edited 32 mins ago

Budd

14333 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

$endgroup$

add a comment
 | 

4

1

$begingroup$

This question relates to pigeonhole principle, but I couldn't find what the holes need to be. How should I prove this сlaim?

combinatorics pigeonhole-principle

share|cite|improve this question

edited 32 mins ago

Budd

14333 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

This question relates to pigeonhole principle, but I couldn't find what the holes need to be. How should I prove this сlaim?

combinatorics pigeonhole-principle

share|cite|improve this question

edited 32 mins ago

Budd

14333 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

$endgroup$

share|cite|improve this question

edited 32 mins ago

Budd

14333 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

share|cite|improve this question

edited 32 mins ago

Budd

14333 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

edited 32 mins ago

Budd

14333 bronze badges

edited 32 mins ago

Budd

14333 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

asked 19 hours ago

M.MitelmanM.Mitelman

3944 bronze badges

3 Answers
3

active

oldest

votes

10

$begingroup$

Here is one solution, uses the pigeonhole principle twice.

First, lets have one hole for every remainder that the number leaves when divided by $5$. So we have holes $h_0,h_1,h_2,h_3$ and $h_4$. Notice that the two numbers that we are looking for should land in the same hole.
Since we have 51 numbers, one of these holes has at least 11 numbers. Let these numbers be $a_1 < a_2 < cdots < a_11$. Throw the rest away, we won't need them.

Moving on, notice that we haven't used the fact that the numbers are between $1$ to $100$. Let us use that now. To keep things simple, subtract $a_1 - 1$ from all the 11 numbers, so that the numbers look like $1 < b_2 < cdots < b_11$, where $b_i$ is just $a_i - a_1 + 1$.

Now, let us have $20$ holes, labelled with numbers that leave a remainder of $1$ when divided by $5$ $1,6,11,ldots,91,96$. What we are looking for is two adjacent holes that are filled. We are bound to succeed as there are $20$ holes and $11$ pigeons (numbers).

Hope this helps.

share|cite|improve this answer

answered 19 hours ago

anamayanamay

12177 bronze badges

New contributor

anamay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  You mean there are 20 pigeons (1,6,...,96) and 11 holes (1,2,...,11)?
  $endgroup$
  – M.Mitelman
  19 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure the second application is using the pigeonhole principle per se. At least, it's not one of the usual variants. To make it an application of the usual pigeonhole principle, your holes should be pairs of adjacent numbers, and each pigeon is then put in two holes.
  $endgroup$
  – 6005
  4 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to the site and thanks for the great answer!
  $endgroup$
  – Joonas Ilmavirta
  1 hour ago
  

  
  
  
  

add a comment
 | 

12

$begingroup$

For a variant that uses the pigeonhole principle only once, consider the $50$ pairs

$$
1,6, 2,7, 3,8, 4,9, 5,10 \
11,16, 12,17, 13,18, 14,19, 15,20 \
... \
91,96, 92,97, 93,98, 94,99, 95,100
$$
or in other words the sets $10i + j, 10i+j+5$ for each $0 le i le 9$ and each $1 le jle 5$.

Or in other other words, pair each number $n$ whose last digit is $1$, $2$, $3$, $4$, or $5$ with $n+5$.

With $51$ numbers chosen, at least one of these pairs has both elements chosen from it, giving us $2$ numbers that are exactly $5$ apart.

share|cite|improve this answer

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

$endgroup$

add a comment
 | 

4

$begingroup$

Let $S_k$, $0 leq k leq 4$, be the set of integers in $1, 2, 3, ldots, 100$ that have remainder $k$ when divided by $5$. Each such set has $20$ elements. Since you have $51$ numbers in this set, at least one of the $S_k$'s must have at least $11$ elements. Show that such an $S_k$ must have two elements in that set that differ by $5$.

share|cite|improve this answer

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges

$endgroup$

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/4.0/"u003ecc by-sa 4.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

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3365356%2fthere-are-51-natural-numbers-between-1-100-prove-that-there-are-2-numbers-such%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

10

$begingroup$

Here is one solution, uses the pigeonhole principle twice.

First, lets have one hole for every remainder that the number leaves when divided by $5$. So we have holes $h_0,h_1,h_2,h_3$ and $h_4$. Notice that the two numbers that we are looking for should land in the same hole.
Since we have 51 numbers, one of these holes has at least 11 numbers. Let these numbers be $a_1 < a_2 < cdots < a_11$. Throw the rest away, we won't need them.

Moving on, notice that we haven't used the fact that the numbers are between $1$ to $100$. Let us use that now. To keep things simple, subtract $a_1 - 1$ from all the 11 numbers, so that the numbers look like $1 < b_2 < cdots < b_11$, where $b_i$ is just $a_i - a_1 + 1$.

Now, let us have $20$ holes, labelled with numbers that leave a remainder of $1$ when divided by $5$ $1,6,11,ldots,91,96$. What we are looking for is two adjacent holes that are filled. We are bound to succeed as there are $20$ holes and $11$ pigeons (numbers).

Hope this helps.

share|cite|improve this answer

answered 19 hours ago

anamayanamay

12177 bronze badges

New contributor

anamay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  You mean there are 20 pigeons (1,6,...,96) and 11 holes (1,2,...,11)?
  $endgroup$
  – M.Mitelman
  19 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure the second application is using the pigeonhole principle per se. At least, it's not one of the usual variants. To make it an application of the usual pigeonhole principle, your holes should be pairs of adjacent numbers, and each pigeon is then put in two holes.
  $endgroup$
  – 6005
  4 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to the site and thanks for the great answer!
  $endgroup$
  – Joonas Ilmavirta
  1 hour ago
  

  
  
  
  

add a comment
 | 

10

$begingroup$

Here is one solution, uses the pigeonhole principle twice.

First, lets have one hole for every remainder that the number leaves when divided by $5$. So we have holes $h_0,h_1,h_2,h_3$ and $h_4$. Notice that the two numbers that we are looking for should land in the same hole.
Since we have 51 numbers, one of these holes has at least 11 numbers. Let these numbers be $a_1 < a_2 < cdots < a_11$. Throw the rest away, we won't need them.

Moving on, notice that we haven't used the fact that the numbers are between $1$ to $100$. Let us use that now. To keep things simple, subtract $a_1 - 1$ from all the 11 numbers, so that the numbers look like $1 < b_2 < cdots < b_11$, where $b_i$ is just $a_i - a_1 + 1$.

Now, let us have $20$ holes, labelled with numbers that leave a remainder of $1$ when divided by $5$ $1,6,11,ldots,91,96$. What we are looking for is two adjacent holes that are filled. We are bound to succeed as there are $20$ holes and $11$ pigeons (numbers).

Hope this helps.

share|cite|improve this answer

answered 19 hours ago

anamayanamay

12177 bronze badges

New contributor

anamay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  You mean there are 20 pigeons (1,6,...,96) and 11 holes (1,2,...,11)?
  $endgroup$
  – M.Mitelman
  19 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I am not sure the second application is using the pigeonhole principle per se. At least, it's not one of the usual variants. To make it an application of the usual pigeonhole principle, your holes should be pairs of adjacent numbers, and each pigeon is then put in two holes.
  $endgroup$
  – 6005
  4 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to the site and thanks for the great answer!
  $endgroup$
  – Joonas Ilmavirta
  1 hour ago
  

  
  
  
  

add a comment
 | 

$begingroup$

Here is one solution, uses the pigeonhole principle twice.

First, lets have one hole for every remainder that the number leaves when divided by $5$. So we have holes $h_0,h_1,h_2,h_3$ and $h_4$. Notice that the two numbers that we are looking for should land in the same hole.
Since we have 51 numbers, one of these holes has at least 11 numbers. Let these numbers be $a_1 < a_2 < cdots < a_11$. Throw the rest away, we won't need them.

Moving on, notice that we haven't used the fact that the numbers are between $1$ to $100$. Let us use that now. To keep things simple, subtract $a_1 - 1$ from all the 11 numbers, so that the numbers look like $1 < b_2 < cdots < b_11$, where $b_i$ is just $a_i - a_1 + 1$.

Now, let us have $20$ holes, labelled with numbers that leave a remainder of $1$ when divided by $5$ $1,6,11,ldots,91,96$. What we are looking for is two adjacent holes that are filled. We are bound to succeed as there are $20$ holes and $11$ pigeons (numbers).

Hope this helps.

share|cite|improve this answer

answered 19 hours ago

anamayanamay

12177 bronze badges

New contributor

anamay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

answered 19 hours ago

anamayanamay

12177 bronze badges

New contributor

anamay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 19 hours ago

anamayanamay

12177 bronze badges

New contributor

anamay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 19 hours ago

anamayanamay

12177 bronze badges

12

$begingroup$

For a variant that uses the pigeonhole principle only once, consider the $50$ pairs

$$
1,6, 2,7, 3,8, 4,9, 5,10 \
11,16, 12,17, 13,18, 14,19, 15,20 \
... \
91,96, 92,97, 93,98, 94,99, 95,100
$$
or in other words the sets $10i + j, 10i+j+5$ for each $0 le i le 9$ and each $1 le jle 5$.

Or in other other words, pair each number $n$ whose last digit is $1$, $2$, $3$, $4$, or $5$ with $n+5$.

With $51$ numbers chosen, at least one of these pairs has both elements chosen from it, giving us $2$ numbers that are exactly $5$ apart.

share|cite|improve this answer

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

$endgroup$

add a comment
 | 

12

$begingroup$

For a variant that uses the pigeonhole principle only once, consider the $50$ pairs

$$
1,6, 2,7, 3,8, 4,9, 5,10 \
11,16, 12,17, 13,18, 14,19, 15,20 \
... \
91,96, 92,97, 93,98, 94,99, 95,100
$$
or in other words the sets $10i + j, 10i+j+5$ for each $0 le i le 9$ and each $1 le jle 5$.

Or in other other words, pair each number $n$ whose last digit is $1$, $2$, $3$, $4$, or $5$ with $n+5$.

With $51$ numbers chosen, at least one of these pairs has both elements chosen from it, giving us $2$ numbers that are exactly $5$ apart.

share|cite|improve this answer

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

For a variant that uses the pigeonhole principle only once, consider the $50$ pairs

$$
1,6, 2,7, 3,8, 4,9, 5,10 \
11,16, 12,17, 13,18, 14,19, 15,20 \
... \
91,96, 92,97, 93,98, 94,99, 95,100
$$
or in other words the sets $10i + j, 10i+j+5$ for each $0 le i le 9$ and each $1 le jle 5$.

Or in other other words, pair each number $n$ whose last digit is $1$, $2$, $3$, $4$, or $5$ with $n+5$.

With $51$ numbers chosen, at least one of these pairs has both elements chosen from it, giving us $2$ numbers that are exactly $5$ apart.

share|cite|improve this answer

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

$endgroup$

share|cite|improve this answer

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

answered 9 hours ago

Misha LavrovMisha Lavrov

54.6k77 gold badges6161 silver badges115115 bronze badges

4

$begingroup$

Let $S_k$, $0 leq k leq 4$, be the set of integers in $1, 2, 3, ldots, 100$ that have remainder $k$ when divided by $5$. Each such set has $20$ elements. Since you have $51$ numbers in this set, at least one of the $S_k$'s must have at least $11$ elements. Show that such an $S_k$ must have two elements in that set that differ by $5$.

share|cite|improve this answer

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges

$endgroup$

add a comment
 | 

4

$begingroup$

Let $S_k$, $0 leq k leq 4$, be the set of integers in $1, 2, 3, ldots, 100$ that have remainder $k$ when divided by $5$. Each such set has $20$ elements. Since you have $51$ numbers in this set, at least one of the $S_k$'s must have at least $11$ elements. Show that such an $S_k$ must have two elements in that set that differ by $5$.

share|cite|improve this answer

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

Let $S_k$, $0 leq k leq 4$, be the set of integers in $1, 2, 3, ldots, 100$ that have remainder $k$ when divided by $5$. Each such set has $20$ elements. Since you have $51$ numbers in this set, at least one of the $S_k$'s must have at least $11$ elements. Show that such an $S_k$ must have two elements in that set that differ by $5$.

share|cite|improve this answer

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges

$endgroup$

share|cite|improve this answer

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges

answered 19 hours ago

N. F. TaussigN. F. Taussig

49.4k1010 gold badges3737 silver badges6060 bronze badges