Not Exceeding 24

Solution

|Contact| |Front page| |Contents| |Up| |Store|

I have picked the problem from a combinatorics text, where the omission was detected and corrected.

It is strange, however, why the proposer chose to limit his numbers with 24 and not, say, with 25. The maximum sum in this case would be 94, allowing for a straightforward application of the pigeonhole principle.

The requirement of distinctiveness is however a necessary condition because, otherwise, some two 1-element sets would have equal sum of the elements.

But once the elements are said to be distinct, their upper bound can be upgraded to 25 or even 26! In the latter case, the maximum sum of a 4-set would be 98. Still the Pigeonhole is applicable. How? Why?

Solution 2

(This solution is due to Bernard Murphy)

Assume the numbers chosen are a < b < c < d < e < f < g.

The maximum sum of 6 chosen numbers is 24 + 23 + 22 + 21 + 20 + b = 110 + b and so the maximum sum which could be repeated is 109 + b.

The smallest possible sum which could be repeated is 1 + b since this could be equal to c.

Therefore there are at most 109 different totals but the number of subsets under consideration is 2⁷ - 6 = 122 since each of {}, {a}, {b}, {b, c, d, e, f, g}, {a, c, d, e, f, g} and {a, b, c, d, e, f, g} cannot have the same sum as another set.

So there are 122 pigeons and only 109 pigeonholes.

Note: This solution leads to exactly same question, "Why the number of upper limit of the numbers in hand was chosen to be 24 and not 26?"

References

1. W. D, Wallis, J. C. George, Introduction to Combinatorics, CRC, 2010, p. 49

|Contact| |Front page| |Contents| |Up| |Store|

Prove that no seven distinct positive integers, not exceeding 26, can have sums of all subsets different.

As before, there are 98 subsets of no more than 4 elements and the maximum sum of a four element set is 98. The relief now comes from the other end. If the least number of the given 7 is greater than 1, the range of possible sums contains fewer than 98 terms. But even if the least number is 1, the second least terms could only be at most two, making the sum of 2 impossible. Thus in any event, there are fewer than 98 sums and, again, the pigeonhole works wonders.

Related material Read more...
	Sum of Integers
	More than half of the integers from {1, 2, ..., 2n}
	Consequences of Getting More Than a Half
	Remainder Multiples of 1997
	Intersecting Subsets
	Over-The-Counter Pigeonhole
	Women in a theatre: Pigeonhole Principle
	Pigeonhole Among Friends

|Contact| |Front page| |Contents| |Up| |Store|