Pigeonhole Principle: Getting the Largest Sum

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Problem:

Choose 15 different numbers in sequence 1, 4, 7, 10, 13, ..., 64, 67, 70 to form a group. What is the maximum sum of any 2 numbers selected from the set of the 15 different numbers?

Solution:

There are 24 numbers in the sequence. Using pigeonhole principle, since 15 numbers will be picked from the set, there are at least one pair of numbers whose sum is 83. So the largest sum is 83.

However, I don't get the idea of using the pigeonhole principle if we can choose 67 and 70. So, the sum is 137?

combinatorics number-theory pigeonhole-principle

share|cite|improve this question

edited Jul 24 at 15:35

asked Jul 24 at 15:29

Jeremiah Atenta

63

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It says that there's a sum that'll appear in all sets, but asks you to find the largest sum?
  – MalayTheDynamo
  Jul 24 at 15:33
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

Problem:

Choose 15 different numbers in sequence 1, 4, 7, 10, 13, ..., 64, 67, 70 to form a group. What is the maximum sum of any 2 numbers selected from the set of the 15 different numbers?

Solution:

There are 24 numbers in the sequence. Using pigeonhole principle, since 15 numbers will be picked from the set, there are at least one pair of numbers whose sum is 83. So the largest sum is 83.

However, I don't get the idea of using the pigeonhole principle if we can choose 67 and 70. So, the sum is 137?

combinatorics number-theory pigeonhole-principle

share|cite|improve this question

edited Jul 24 at 15:35

asked Jul 24 at 15:29

Jeremiah Atenta

63

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It says that there's a sum that'll appear in all sets, but asks you to find the largest sum?
  – MalayTheDynamo
  Jul 24 at 15:33
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Problem:

Choose 15 different numbers in sequence 1, 4, 7, 10, 13, ..., 64, 67, 70 to form a group. What is the maximum sum of any 2 numbers selected from the set of the 15 different numbers?

Solution:

There are 24 numbers in the sequence. Using pigeonhole principle, since 15 numbers will be picked from the set, there are at least one pair of numbers whose sum is 83. So the largest sum is 83.

However, I don't get the idea of using the pigeonhole principle if we can choose 67 and 70. So, the sum is 137?

combinatorics number-theory pigeonhole-principle

share|cite|improve this question

edited Jul 24 at 15:35

asked Jul 24 at 15:29

Jeremiah Atenta

63

Problem:

Choose 15 different numbers in sequence 1, 4, 7, 10, 13, ..., 64, 67, 70 to form a group. What is the maximum sum of any 2 numbers selected from the set of the 15 different numbers?

Solution:

There are 24 numbers in the sequence. Using pigeonhole principle, since 15 numbers will be picked from the set, there are at least one pair of numbers whose sum is 83. So the largest sum is 83.

However, I don't get the idea of using the pigeonhole principle if we can choose 67 and 70. So, the sum is 137?

combinatorics number-theory pigeonhole-principle

share|cite|improve this question

edited Jul 24 at 15:35

asked Jul 24 at 15:29

Jeremiah Atenta

63

share|cite|improve this question

share|cite|improve this question

edited Jul 24 at 15:35

edited Jul 24 at 15:35

edited Jul 24 at 15:35

asked Jul 24 at 15:29

Jeremiah Atenta

63

asked Jul 24 at 15:29

Jeremiah Atenta

63

asked Jul 24 at 15:29

Jeremiah Atenta

63

63

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It says that there's a sum that'll appear in all sets, but asks you to find the largest sum?
  – MalayTheDynamo
  Jul 24 at 15:33
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It says that there's a sum that'll appear in all sets, but asks you to find the largest sum?
  – MalayTheDynamo
  Jul 24 at 15:33
  

  
  
  
  

It says that there's a sum that'll appear in all sets, but asks you to find the largest sum?
– MalayTheDynamo
Jul 24 at 15:33

It says that there's a sum that'll appear in all sets, but asks you to find the largest sum?
– MalayTheDynamo
Jul 24 at 15:33

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote

I think you are getting mixed up with your question. You are looking for either:

1. The largest possible sum of two numbers chosen from the set of fifteen.


2. The largest sum of two numbers chosen from the set of fifteen, such that this sum appears in every possible set of fifteen.

In the first case the answer is $67+70 = 137$.

In the second case the answer is the sum of the two largest elements in the smallest set, namely $40 + 43 = 83$. As the elements are in a arithmetic progression, using the pigeonhole principle you can show why there must be at least two elements in any set of fifteen which also add to $83$.

share|cite|improve this answer

answered Jul 24 at 15:56

packetpacket

249112

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
);



);

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861469%2fpigeonhole-principle-getting-the-largest-sum%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

I think you are getting mixed up with your question. You are looking for either:

1. The largest possible sum of two numbers chosen from the set of fifteen.


2. The largest sum of two numbers chosen from the set of fifteen, such that this sum appears in every possible set of fifteen.

In the first case the answer is $67+70 = 137$.

In the second case the answer is the sum of the two largest elements in the smallest set, namely $40 + 43 = 83$. As the elements are in a arithmetic progression, using the pigeonhole principle you can show why there must be at least two elements in any set of fifteen which also add to $83$.

share|cite|improve this answer

answered Jul 24 at 15:56

packetpacket

249112

add a comment | 

up vote
1
down vote

I think you are getting mixed up with your question. You are looking for either:

1. The largest possible sum of two numbers chosen from the set of fifteen.


2. The largest sum of two numbers chosen from the set of fifteen, such that this sum appears in every possible set of fifteen.

In the first case the answer is $67+70 = 137$.

In the second case the answer is the sum of the two largest elements in the smallest set, namely $40 + 43 = 83$. As the elements are in a arithmetic progression, using the pigeonhole principle you can show why there must be at least two elements in any set of fifteen which also add to $83$.

share|cite|improve this answer

answered Jul 24 at 15:56

packetpacket

249112

add a comment | 

up vote
1
down vote

up vote
1
down vote

I think you are getting mixed up with your question. You are looking for either:

1. The largest possible sum of two numbers chosen from the set of fifteen.


2. The largest sum of two numbers chosen from the set of fifteen, such that this sum appears in every possible set of fifteen.

In the first case the answer is $67+70 = 137$.

In the second case the answer is the sum of the two largest elements in the smallest set, namely $40 + 43 = 83$. As the elements are in a arithmetic progression, using the pigeonhole principle you can show why there must be at least two elements in any set of fifteen which also add to $83$.

share|cite|improve this answer

answered Jul 24 at 15:56

packetpacket

249112

I think you are getting mixed up with your question. You are looking for either:

1. The largest possible sum of two numbers chosen from the set of fifteen.


2. The largest sum of two numbers chosen from the set of fifteen, such that this sum appears in every possible set of fifteen.

In the first case the answer is $67+70 = 137$.

In the second case the answer is the sum of the two largest elements in the smallest set, namely $40 + 43 = 83$. As the elements are in a arithmetic progression, using the pigeonhole principle you can show why there must be at least two elements in any set of fifteen which also add to $83$.

share|cite|improve this answer

answered Jul 24 at 15:56

packetpacket

249112

share|cite|improve this answer

share|cite|improve this answer

answered Jul 24 at 15:56

packetpacket

249112

answered Jul 24 at 15:56

packetpacket

249112

answered Jul 24 at 15:56

packetpacket

249112

249112

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861469%2fpigeonhole-principle-getting-the-largest-sum%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Name Email

Name Email

Name

Email

Name Email

Name

Email