Pigeonhole Principle Issue five integers where their sum or difference is divisible by seven.

up vote
3
down vote

favorite

Given any five integers, there will be two that have a sum or difference divisible by 7. I'm trying to solve this using the Pigeonhole Principle, but it is not making sense to me, how this principle holds true in this case. Aren't the "pigeons" in this case "five" and the "holes" are "seven"? I'm so confused.

edited 10 mins ago

N. F. Taussig

41.5k93253

asked 7 hours ago

KLaRue

161

New contributor

1

Hint: How many sums are possible? How many differences are possible?
â€“Â JoshuaZ
7 hours ago

The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, pm 1, pm 2, pm 3$
â€“Â fleablood
3 hours ago

add a commentÂ |Â

up vote
3
down vote

favorite

edited 10 mins ago

N. F. Taussig

41.5k93253

asked 7 hours ago

KLaRue

161

New contributor

1

Hint: How many sums are possible? How many differences are possible?
â€“Â JoshuaZ
7 hours ago

The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, pm 1, pm 2, pm 3$
â€“Â fleablood
3 hours ago

add a commentÂ |Â

up vote
3
down vote

favorite

edited 10 mins ago

N. F. Taussig

41.5k93253

asked 7 hours ago

KLaRue

161

New contributor

combinatorics discrete-mathematics proof-writing pigeonhole-principle

edited 10 mins ago

N. F. Taussig

41.5k93253

asked 7 hours ago

KLaRue

161

New contributor

edited 10 mins ago

N. F. Taussig

41.5k93253

asked 7 hours ago

KLaRue

161

New contributor

edited 10 mins ago

N. F. Taussig

41.5k93253

edited 10 mins ago

N. F. Taussig

41.5k93253

edited 10 mins ago

N. F. Taussig

41.5k93253

asked 7 hours ago

KLaRue

161

New contributor

asked 7 hours ago

KLaRue

161

asked 7 hours ago

KLaRue

161

New contributor

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

1

Hint: How many sums are possible? How many differences are possible?
â€“Â JoshuaZ
7 hours ago

The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, pm 1, pm 2, pm 3$
â€“Â fleablood
3 hours ago

add a commentÂ |Â

1

Hint: How many sums are possible? How many differences are possible?
â€“Â JoshuaZ
7 hours ago

The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, pm 1, pm 2, pm 3$
â€“Â fleablood
3 hours ago

Hint: How many sums are possible? How many differences are possible?
â€“Â JoshuaZ
7 hours ago

The 7 holes are not $0,1,2,3,4,5,6,7$. The 4 holes are $0, pm 1, pm 2, pm 3$
â€“Â fleablood
3 hours ago

add a commentÂ |Â

3 Answers
3

active

oldest

votes

up vote
4
down vote

consider $a_n = x_n mod 7$
In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

To avoid a sum or difference divisible by 7 we would need to put 5 integers into 4 holes with no more than one in each hole. This can't be done, therefore having at least one pair whose sum or difference is divisible by 7 is unavoidable.

answered 6 hours ago

WW1

6,9551712

add a commentÂ |Â

up vote
4
down vote

Here is another argument which is based on the following fact:

There are only $4$ quadratic remainders $mod 7$: $0,1,2,4$.

Now, let $a_1, ldots , a_5 in mathbbZ$.

There is $1leq k < l leq 5$ such that

$$a_k^2 equiv a_l^2 mod 7 Rightarrow (a_k + a_l)(a_k - a_l) equiv 0 mod 7$$
This proves the claim.

edited 5 hours ago

answered 5 hours ago

trancelocation

6,8161518

Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done.
â€“Â AndrÃ©s E. Caicedo
5 hours ago

@ AndrÃ©s E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks.
â€“Â trancelocation
5 hours ago

add a commentÂ |Â

up vote
3
down vote

Note every integer $a$ is such that $a equiv 0, pm 1, pm 2, pm 3 pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a equiv pm k pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a equiv pm k pmod 7$ and $b equiv pm k pmod 7$.

which means:

So $a equiv pm b pmod 7$. So $a mp b equiv 0 pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.

answered 3 hours ago

fleablood

63.7k22679

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

KLaRue is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2968588%2fpigeonhole-principle-issue-five-integers-where-their-sum-or-difference-is-divisi%23new-answer', 'question_page');

);

Post as a guest

Name

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

up vote
4
down vote

consider $a_n = x_n mod 7$
In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

answered 6 hours ago

WW1

6,9551712

add a commentÂ |Â

up vote
4
down vote

consider $a_n = x_n mod 7$
In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

answered 6 hours ago

WW1

6,9551712

add a commentÂ |Â

up vote
4
down vote

consider $a_n = x_n mod 7$
In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

answered 6 hours ago

WW1

6,9551712

consider $a_n = x_n mod 7$
In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

answered 6 hours ago

WW1

6,9551712

answered 6 hours ago

WW1

6,9551712

answered 6 hours ago

WW1

6,9551712

answered 6 hours ago

WW1

6,9551712

add a commentÂ |Â

up vote
4
down vote

Here is another argument which is based on the following fact:

There are only $4$ quadratic remainders $mod 7$: $0,1,2,4$.

Now, let $a_1, ldots , a_5 in mathbbZ$.

There is $1leq k < l leq 5$ such that

$$a_k^2 equiv a_l^2 mod 7 Rightarrow (a_k + a_l)(a_k - a_l) equiv 0 mod 7$$
This proves the claim.

edited 5 hours ago

answered 5 hours ago

trancelocation

6,8161518

Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done.
â€“Â AndrÃ©s E. Caicedo
5 hours ago

@ AndrÃ©s E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks.
â€“Â trancelocation
5 hours ago

add a commentÂ |Â

up vote
4
down vote

Here is another argument which is based on the following fact:

There are only $4$ quadratic remainders $mod 7$: $0,1,2,4$.

Now, let $a_1, ldots , a_5 in mathbbZ$.

There is $1leq k < l leq 5$ such that

$$a_k^2 equiv a_l^2 mod 7 Rightarrow (a_k + a_l)(a_k - a_l) equiv 0 mod 7$$
This proves the claim.

edited 5 hours ago

answered 5 hours ago

trancelocation

6,8161518

Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done.
â€“Â AndrÃ©s E. Caicedo
5 hours ago

@ AndrÃ©s E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks.
â€“Â trancelocation
5 hours ago

add a commentÂ |Â

up vote
4
down vote

Here is another argument which is based on the following fact:

There are only $4$ quadratic remainders $mod 7$: $0,1,2,4$.

Now, let $a_1, ldots , a_5 in mathbbZ$.

There is $1leq k < l leq 5$ such that

$$a_k^2 equiv a_l^2 mod 7 Rightarrow (a_k + a_l)(a_k - a_l) equiv 0 mod 7$$
This proves the claim.

edited 5 hours ago

answered 5 hours ago

trancelocation

6,8161518

Here is another argument which is based on the following fact:

There are only $4$ quadratic remainders $mod 7$: $0,1,2,4$.

Now, let $a_1, ldots , a_5 in mathbbZ$.

There is $1leq k < l leq 5$ such that

$$a_k^2 equiv a_l^2 mod 7 Rightarrow (a_k + a_l)(a_k - a_l) equiv 0 mod 7$$
This proves the claim.

edited 5 hours ago

answered 5 hours ago

trancelocation

6,8161518

edited 5 hours ago

answered 5 hours ago

trancelocation

6,8161518

answered 5 hours ago

trancelocation

6,8161518

answered 5 hours ago

trancelocation

6,8161518

Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done.
â€“Â AndrÃ©s E. Caicedo
5 hours ago

@ AndrÃ©s E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks.
â€“Â trancelocation
5 hours ago

add a commentÂ |Â

Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done.
â€“Â AndrÃ©s E. Caicedo
5 hours ago

@ AndrÃ©s E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks.
â€“Â trancelocation
5 hours ago

Why argue by contradiction? If two integers have equal quadratic remainder, then either their sum or their difference is a multiple of 7, and you are done.
â€“Â AndrÃ©s E. Caicedo
5 hours ago

@ AndrÃ©s E. Caicedo: Ha!. That's right. It's still early here in the morning. Will edit it accordingly. :-) Thanks.
â€“Â trancelocation
5 hours ago

add a commentÂ |Â

up vote
3
down vote

Note every integer $a$ is such that $a equiv 0, pm 1, pm 2, pm 3 pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a equiv pm k pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a equiv pm k pmod 7$ and $b equiv pm k pmod 7$.

which means:

So $a equiv pm b pmod 7$. So $a mp b equiv 0 pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.

answered 3 hours ago

fleablood

63.7k22679

add a commentÂ |Â

up vote
3
down vote

Note every integer $a$ is such that $a equiv 0, pm 1, pm 2, pm 3 pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a equiv pm k pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a equiv pm k pmod 7$ and $b equiv pm k pmod 7$.

which means:

So $a equiv pm b pmod 7$. So $a mp b equiv 0 pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.

answered 3 hours ago

fleablood

63.7k22679

add a commentÂ |Â

up vote
3
down vote

Note every integer $a$ is such that $a equiv 0, pm 1, pm 2, pm 3 pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a equiv pm k pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a equiv pm k pmod 7$ and $b equiv pm k pmod 7$.

which means:

So $a equiv pm b pmod 7$. So $a mp b equiv 0 pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.

answered 3 hours ago

fleablood

63.7k22679

Note every integer $a$ is such that $a equiv 0, pm 1, pm 2, pm 3 pmod 7$.

Let the pigeons be the $5$ integers. Let $k = 0, 1, 2, 3$ be the $4$ holes.

We assign pigeons to holes:

We assign pigeon $a$ the hole $k$ if $a equiv pm k pmod 7$.

Two pigeons must share the same hole:

There are five pigeons so we are going to have two pigeons, $a$ and $b$ in the same hole, $k$. i.e. $a equiv pm k pmod 7$ and $b equiv pm k pmod 7$.

which means:

So $a equiv pm b pmod 7$. So $a mp b equiv 0 pmod 7$. So either $a + b$ is divisible by $7$ or $a-b$ is divisible by $7$.

answered 3 hours ago

fleablood

63.7k22679

answered 3 hours ago

fleablood

63.7k22679

answered 3 hours ago

fleablood

63.7k22679

answered 3 hours ago

fleablood

63.7k22679

add a commentÂ |Â

KLaRue is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

KLaRue is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky