Solution to State the Pigeonhole Principle. Prove that if six integers are selected from the set [3,4,5,6,7,8,9,10,11,12] … - Sikademy
Author Image

Archangel Macsika

State the Pigeonhole Principle. Prove that if six integers are selected from the set [3,4,5,6,7,8,9,10,11,12] there must be two integer whose sum is fifteen.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

For natural numbers {\displaystyle k}  and {\displaystyle m}, if {\displaystyle n=km+1} objects are distributed among {\displaystyle m} sets, then the Pigeonhole Principle asserts that at least one of the sets will contain at least {\displaystyle k+1}  objects.


Let us consider the partition of the set \{3,4,5,6,7,8,9,10,11,12\} ito 5 subset: \{3,12\}\{4,11\}\{5,10\}, \{6,9\} and \{7,8\}. The sum of elements in each subset is equal to 15. Taking into account that there are 5 subsets and we choose 6 elements by Pigeonhole Principle we get that at least one pair will be selected. Consequently, there must be two integer whose sum is fifteen.


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-788-qpid-673