Let S (A) be the sum of the elements of the set A of size n. We will call this set a special total set if for any two non-empty and disjoint subsets B and C the following is true:

S (B) ≠ S (C); those. sums of elements of subsets cannot be equal. If B contains more elements than C, then S (B)> S (C). For this problem, we assume that this set consists of n strictly increasing elements and it already complies with the second rule.

Surprisingly, out of 25 possible pairs of subsets that can be obtained from the set with n = 4, only one of them should be checked for equality (the first condition). Similarly, with n = 7, only 70 out of 966 pairs of subsets should be checked for equality.

How many pairs of subsets need to be checked for equality from the total number of 261625 pairs that can be formed with n = 12?

Note: This task is also related to tasks №103 and №105.

Here are some special sets for the first initial n:

n = 1: {1}

n = 2: {1, 2}

n = 3: {2, 3, 4}

n = 4: {3, 5, 6, 7}

n = 5: {6, 9, 11, 12, 13}

My question is as follows. For n = 4, there really are 25 possible unique pairs of non-empty sets. I agree with this. I do not understand why checking for 1 condition requires only one.

If I think correctly, the fulfillment of the second condition is checked only for the case when the sizes of the sets are different. If the second condition is satisfied, then check 1 of the condition is passed automatically. It is obvious.

However, if we eliminate a pair of equal size from 25 variants, then it turns out not 1 pair, but 9. Why for n = 4 in the problem is only 1 pair checked for equality ?!

Just in case, I’ll give my code for searching pairs of subsets:

import itertools a = [3, 5, 6, 7] combinations = set() pair_combinations = list() for b in range(1, len(a)): combinations.update(itertools.combinations(a, b)) combinations = list(combinations) combinations.sort() num = 0 for b in combinations: b_ = list(combinations) b_.remove(b) for с in b_: sum_b = sum(b) sum_c = sum(с) len_set_b = len(list(b)) len_set_c = len(list(с)) set_b = set(b) set_c = set(с) # определяем непересекающиеся подмножества и проводим над ними проверку по условию if set_b.isdisjoint(set_c): # проверка, чтобы не дублировать пары if [с, b] not in pair_combinations: # if len_set_b == len_set_c: pair_combinations.append([b, с]) num = 0 for pair in pair_combinations: print(num, pair) num = num + 1

    1 answer 1

    Let be

     A = {a, b, c, d}

    It is known that the sequence is strictly increasing:

     a < b < c < d

    Also, on the basis of compliance with the second rule, it is known that the sum of any larger subset is greater than any smaller:

     a + b > c a + b > d ... b + c + d > a

    It remains to prove the first rule, i.e. inequality of subsets of the same size:

     a + b != c + d a + c != b + d a + d != b + c

    The first case is true automatically, because each term from the right side is larger than each of the left, so the sum is greater

     a + b < c + d

    With the second as well, because b > a and d > c , it means

     a + c < b + d

    but the third case needs to be checked, because at least b > a , but c > d

    • But this is a very interesting idea. Thank you. We need to think about how to scale it on the machine. - Alexander Ryadinsky
    • one
      @Alexander Ryadinsky there is a purely mathematical solution without cycles (except for the sum and factorial). But even with the help of combinations with filtering out extra sequences, you can solve the problem for n=12 in a reasonable time. As far as I understand, you didn’t come here for the decision, you can probably google it, so I will not upload the working code, but the information that I gave should be enough to implement at least a non-optimal solution. - extrn