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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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