Question

Show that given any set of \({\bf{10}}\) positive integers not exceeding \({\bf{50}}\) there exist at least two different five-element subsets of this set that have the same sum.

Short answer

There are at least two such subsets with the same sum.

Step-by-step solution

Definition of pigeonhole

The principle of the generalized pigeonhole there exists a box with at least\(lceilN/krceil\)items when\(N\)objects are placed into\(k\)boxes.

Permutation (order is important) is defined as:

\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Definition of a combination (the order is irrelevant):

\(C(n,r) = \left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)

The total number of potential sums (boxes)

If the positive integers in the set are not greater than\(50\), the sum is taken of\(5\)members from the set.

The sum of the five greatest integers that do not exceed\(50\)is then the highest feasible sum:

The most significant amount =\(50 + 49 + 48 + 47 + 46 = 240\)

The sum of the five smallest positive integers not exceeding\(50\)is then the lowest possible sum:

The smallest amount =\(1 + 2 + 3 + 4 + 5 = 15\)

As a result, all sums are between \(15\) and \(240\) (inclusive), resulting in a total of \(240 - 15 + 1 = 22\) potential sums.

Number of sets of five integers from a set of 10 integers (objects)

We need to select \(5\) integers from\(10\). The order of the integers is not important,

Thus:

\(C(10,5) = \frac{{10!}}{{5!(10 - 5)!}} = \frac{{10!}}{{5!5!}} = 252\)

{Generalized pigeonhole principle}

Since there are\(252\)objects in\(226\)boxes, the generalized pigeonhole principle tells that at least\((252/226) = 2\)objects in some box and thus there are at least two subsets with the same sum.

Hence, there are at least two subsets of this kind that have the same sum.