# Thread: Pigeon Hole Principle Question

1. ## Pigeon Hole Principle Question

Utilizing the pigeon hole principle answer the following question:

show that if any 9 digit integers are chosen from 1 to 16, then two of them will add up to 17

2. Originally Posted by fusion1455
Utilizing the pigeon hole principle answer the following question:

show that if any 9 digit integers are chosen from 1 to 16, then two of them will add up to 17
what have you tried? note that if the digits are listed in order from 1 up to 16, then the nth number, and then (17 - n)th number (for n ranging from 1 to 8) sum to 17. so then, we can pair off integers in the list that sum to 17. there are 8 such pairs. if we pick numbers so that we do not pick 2 numbers from the same pair, the most we could pick is 8, because upon picking the ninth number, we would have picked a number that pairs off with one of the other numbers to make 17. confused? so am i. take this instead. let the pigeons be the digits, let the holes be the pairs. every time you select a digit (pigeon) place it in the hole that corresponds to the pair it belongs to. since there are 8 pairs in total, namely (1,16),(2,15), (3,14), (4,13), (5,12), (6,11), (7,10), (8,9), if you pick 9 integers, you will have to reuse one of the holes, since you only have 8 of them