0

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

S(B) ≠ S(C); т.е. суммы элементов подмножеств не могут быть равными. Если B содержит больше элементов, чем C, то S(B) > S(C). Если минимизировать сумму S(A) при заданном значении 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}

Похоже на то, что для заданного оптимального множества A = {a1, a2, ... , an}, следующим оптимальным множеством будет множество вида B = {b, a1+b, a2+b, ... ,an+b}, где b - "средний" элемент предыдущей строки.

Применяя данное "правило", можно было бы ожидать, что оптимальным множеством при n = 6 станет A = {11, 17, 20, 22, 23, 24}, у которого S(A) = 117. Однако, данное множество не является оптимальным, поскольку мы всего-лишь применили алгоритм нахождения близкого к оптимальному множества. Оптимальным множеством при for n = 6 будет A = {11, 18, 19, 20, 22, 25}, у которого S(A) = 115. Этому множеству соответствует строка 111819202225.

Дано, что A является оптимальным особым суммарным множеством при n = 7. Найдите строку, соответствующую этому множеству.

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


Поясните мне (возможно, дураку), почему для n=4 не подходит {1,2,3,4}. Ведь данное множество удовлетворяет приведенному условию. Более того данное, множество меньше по сумме, чем, то что приводится в условии.

Для n=5, тоже есть более оптимальное множество {5,6,7,8,9}. Его сумма S = 35. Против того множества для n=5 {6, 9, 11, 12, 13} S = 51, которое приводится задаче.

5
  • разве это 1 + 3 == 4 удовлетворяет условиям для {1,2,3,4}?? 4 мая 2019 в 11:58
  • @MaxU, для множества {1,2,3,4} нет подмножеств {1} + {4}. А = B+C. Иными словами все числа множества А должны быть или в подмножестве В или в подмножестве С. По крайней мере, я так понимаю условие. 4 мая 2019 в 12:04
  • А 2+3 == 1+4 - тоже не нарушает правила? 4 мая 2019 в 12:06
  • @MaxU, спасибо, видимо, это я и упустил! Ушел думать. 4 мая 2019 в 12:10
  • В условии нигде не требуется, чтобы B и C являлись разбиением A. Откуда вы это взяли? Поэтому да, равенство S({ 1, 3 }) == S({ 4 }) уже говорит о том, что множество { 1, 2, 3, 4 } не удовлетворяет требованиям. 4 мая 2019 в 16:11

1 ответ 1

0

Вопрос был глупый. Простая невнимательность.

{1,2,3,4} не канает, потому что, как писали в комментах 2+3 == 1+4.

{5,6,7,8,9} не канает, потому что 5+6+7=18 < 8+9=17

Ваш ответ

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

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