5
|
Задача 191. Сравнения в особых множествахпостоянный адрес задачи: http://www.diofant.ru/problem/566/показать код для вставки на свой сайт >> |
Задачу решили:
5
всего попыток:
7
поделиться задачей:
|
|
Задача опубликована:
07.09.09 10:35
Прислал:
admin
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
арифметика
|
|
Обозначим через S(A) сумму элементов множества A. Будем называть множество целых положительных чисел особым, если для его любых двух непустых непересекающихся подмножеств B и C выполняются следующие условия:
1) S(B) ≠ S(C), т.е. их суммы элементов не могут быть одинаковы.
2) Если B содержит больше элементов, чем C, то S(B) > S(C).
Например, множество {3,5,6,7} - особое, а множество {3,4,5,6} не является особым, так как не выполняется первое условие: 3+6 = 4+5.
Предположим, что n элементов множества расположены в строго возрастающем порядке, и нам нужно проверить, является ли оно особым. Оказывается, что при n=4 из 25 пар подмножеств достаточно всего двух сравнений, а при n=7 достаточно 73 из 966 возможных сравнений.
Сколько нужно выполнить сравнений (из 86526 возможных), чтобы выяснить, является ли особым упорядоченное по возрастанию множество, состоящее из 11 натуральных чисел?
Если Вы не можете ее решить, значит Вы не можете ее решить :-)