|
This is following Gamer's solution, but it's a bit more formal. Let's call a set of positive integers double-free if it does not contain integers x and 2x at the same time. Now fix an integer m and let S be a minimal double-free set of m numbers. Minimal means that any other double-free set S' of m numbers would have a larger sum of its elements. We show how S can be constructed and that it contains exactly 1408 elements for m=43 (The 44th monkey gets no banana).
Let M be the largest number in S. These two statements are easily proven:
1. Every odd number x<M is in S.
Proof: Say x is not in S. Then 2x must be in S, because otherwise we could replace M by x to obtain a smaller set. But again, if 2x is in S, we can replace 2x by x to obtain a smaller set.
2. If x is in S and if 4x<M, then 4x is in S.
Proof: Say 4x is not in S. We know 2x is not in S, because x is. Therefore, the only reason that could prevent us from replacing M by 4x to obtain a smaller set S', is if 8x is in S. But if 8x is in M, we can replace it by 4x to obtain a smaller set S'.
From these two statements, it follows that our set S must contain all numbers smaller than M of the following sets:
S_0 = {1, 3, 5, 7, 9, 11...} = { x | x odd}
S_1 = {4, 12, 20, 28, 36...} = { 4x | x odd}
S_2 = {16, 48, 80, 112...} = {16x | x odd}
generally
S_i = {4^i x | x odd}
Can S contain any other number? Such a number would be of the form 2*4^k*x, with odd x. But then 4^k*x could not be in S, contradictory to what we have just shown. I.e. the set S is in fact exactly the union of all numbers in S_i which are smaller than M. Therefore, to construct a minimal set S, we simply collect the smallest m numbers in the union of S_0, S_1, S_2,... When doing so, we obtain the following sequence:
1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19...
The sum of the first 43 integers is in fact 1408.
|
