>>
|
094652.jpg
Blue Evening Berry
094652
Let's generalize the problem and see if we can work out an induction.
Let A be the set of natural numbers from 1 to a, and let b be a natural number. Let B be any subset such that for all x,y in B_i, x/=y -> MOD(x+y, b) /= 0.
We want to find the particular subset B_i whose sum of all elements is equal to or higher than any B.
There's a trick to this question; she said no pair of distinct elements can be a multiple of 5, which means that 30 can be in the subset because as long as we don't add any other multiple of 5 to the subset,
One possible subset is [26,27,28,29,30]=140, which is the set of numbers greater than the largest number in the set minus 5, which ensures each of the numbers is of a different type of modulo with 5, and thus none of the numbers hybridize. But my intuition suspects that at sufficiently high numbers, skimming the 'top' will not be sufficient to offset the majority of contributions.
Another possible subset is [1,6,11,16,21,26,30], because each number is sufficiently spaced apart evenly that no two numbers reach a multiple of 5. However, 1 isn't expected to be of much use, here.
I suspect the answer is a hybrid of the two questions, dependent on the ratio between a and b.
Maybe the answer is simpler than one might think: if a = 5, what is the largest possible value?
5 is allowed because its modulo is 0 and thus when added to any nonzero modulo will be nonzero.
4 cannot interact with 1
3 cannot interact with 2
So the set with the largest possible sum of elements is [3,4,5] = 12.
Let's test this by induction:
Suppose we select a subset B which consists of only elements x in A up to a such that x mod b <= b/2. We assume that sum of subset B's elements is the largest possible out of all subsets in the limitation that (for all x,y in B_i, x <= a, y <= a, x/=y -> MOD(x+y, b) /= 0) (where a is a multiple of b). Now let's prove that B', which consists of only elements up to a+b, is also the largest of its kind.
B' consists of the elements in B. We have assumed that B is the largest. Now we focus on subset B_5, which consists of elements [a-floor(b)/2...a+b]. We can arbitrarily see that this is the largest possible set of all sets of numbers from a to a+b, because adding any number from the lower levels means sacrificing at least one higher-numbered level. Since B and B_5 make up B', and each is the respective maximum of its range on natural numbers, we conclude that B' is the largest possible.
[3,4,5, 8,9,10, 13,14,15, 23,24,25, 28,29,30] = 240
This takes up a chunk of the largest numbers without actively finding any two which sum to a multiple of 5.
|