3

Пусть S(A) представляет собой сумму элементов множества А размером n. Будем называть это множество особым суммарным множеством, если для любых двух непустых и непересекающихся подмножеств B и C справедливо следующее:

S(B) ≠ S(C); т.е. суммы элементов подмножеств не могут быть равными. Если B содержит больше элементов, чем C, то S(B) > S(C). Для этой задачи предположим, что данное множество состоит из n строго возрастающих элементов и оно уже соответствует второму правилу.

К удивлению, из 25 возможных пар подмножеств, которые можно получить из множества при n = 4, лишь одну из них надо проверить на равенство (первое условие). Подобным образом, при n = 7, лишь 70 из 966 пар подмножеств надо проверить на равенство.

Сколько пар подмножеств необходимо проверить на равенство из общего числа 261625 пар, которые можно образовать при n = 12?

Примечание: Данная задача имеет также отношение к задачам №103 и №105.

Вот некоторые особые множества для первых начальных 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}

Мой вопрос в следующем. Для n=4, действительно, есть 25 возможных уникальных пар непустых множеств. С этим согласен. Я не понимаю, почему проверить на 1 условие надо только одну.

Если я верно мыслю, то выполнение второго условия проверяется только для случая, когда размеры множеств отличны. Если второе условие выполняется, то проверка 1 условия пройдена автоматически. Это очевидно.

Однако если отсеять из 25 вариантов пары равного размера, то получается никак не 1 пара, а 9. Почему для n=4 в задаче проверяется на равенство только 1 пара?!

На всякий случай приведу свой код поиска пар подмножеств:

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 ответ 1

1

Пусть

A = {a, b, c, d}

Известно, что последовательность строго возрастающая:

a < b < c < d

Также исходя из соответствия второму правилу, известно, что сумма любого большего подмножества больше любого меньшего:

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

Остается доказать первое правило, т.е. неравенство подмножеств одинакового размера:

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

Первый случай верен автоматически, потому, что каждое слагаемое из правой части больше каждого из левой, значит и сумма больше

a + b < c + d

Cо вторым так же, потому, что b > a и d > c, значит

a + c < b + d

а вот третий случай нужно проверить, потому, что хоть b > a, но c > d

2
  • А вот это очень интересная мысль. Благодарю. Надо подумать, как ее отмасштабировать на автомате. 8 мая 2019 в 12:49
  • 1
    @АлександрРядинских существует чисто математическое решение без циклов (если не считать сумму и факториал). Но даже с помощью combinations с отфильтровкой лишних последовательностей можно решить задачу для n=12за разумное время. Вы, насколько я понимаю, не за решением сюда пришли, его наверняка и нагуглить можно, так что выкладывать рабочий код я не буду, но той информации что я дал должно хватить для реализации хотя бы неоптимального решения.
    – extrn
    8 мая 2019 в 16:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.