Solve the following problem showing any work 1 Let S be a se

Solve the following problem, showing any work.

1. Let S be a set of integers with the following properties:

a. Every element of S is between 1 and 2014 (inclusive).

b. S has at least 1008 elements. Use the Pigenhole Principle to show that S contains two numbers whose sum is exactly 2015.

Solution

Pigeon Hole Principle

If there are m holes and n pigeons, then there will be atleast one hole that will contain atleast two pigeons.

Proof of above problem:

Set S contains 1008 elements varying from [1,2014].

Take the set S\'\' = [2015 - s | s belongs to S]

The intersection of both the set S and S\' will never be empty set since there are 1008 elements in both the sets and total number of possible elements are 2015, hence there will be atleast one element common to both the sets

Let the element that is common to both the sets be x, then S belongs to x as well as S\'\'

Since S\'\' contains x and 2015-x, hence it will contain atleast two elements whose sum is exactly 2015

(x) + (2015-x) = 2015