Question

How many numbers must be selected from the set {1, 2, 3, 4} to guarantee that at least one pair of these numbers add up to 7?

(a) 14

(b) 5

(c) 9

(d) 24

This question was posed to me in a national level competition.

The query is from Counting topic in chapter Counting of Discrete Mathematics

Answer 1

Right option is (b) 5

To elaborate: With 2 elements pairs which give sum as 7 = {(1,6), (2,5), (3,4), (4,3)}. So choosing 1 element from each group = 4 elements (in worst case 4 elements will be either {1,2,3,4} or {6,5,4,3}). Now using pigeonhole principle = we need to choose 1 more element so that sum will definitely be 7. So Number of elements must be 4 + 1 = 5.