44 monkeys have a total of 1407 bananas. No two monkeys have the same number of bananas. Show that there is a monkey that has exactly twice as many bananas as another one.

To get numbers on the list, take the smallest integers of form O*2^2k, where O is an odd number, and k is a nonnegative integer. If the sum is greater than the total bananas, then there is a contradiction with assuming no monkey has exactly twice as many as another one, thus proving the statement.

To prove that it is the smallest such list, imagine breaking the numbers into rows, grouping numbers with the same prime together.

Any arbitrary such list with no number being twice another must have the groups in the O, 4O, 16O pattern. If the first element is greater than O, the second element must be greater than 4O, and so on. Similarly, if the second element is greater than 4O, then the third element must be greater than 16O, and so on. (If this such list doesn't follow this property, reduce it so it does -- then it will be strictly less than it was previously.)

However, we chose the numbers in the "smallest" list so they were the smallest n satisfying this property. So any other list with this property must have greater elements, and thus a greater sum. (thus, if the list was transformed in the previous step, it has an even greater sum)

Posted by Gamer on 2006-11-14 00:52:50