Пусть 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.