Чтобы решить эту задачу давайте на примере маленького множества посмотрим, сколько пар можно составить из его чисел так, чтобы сумма каждой пары была одинакова.
Разбить его можно на следующие пары: 0 и 9, 1 и 8, 2 и 7, 3 и 6, 4 и 5. Их сумма равна 9, а количество пар в 2 раза меньше количества чисел в множестве. Это нам сейчас пригодится.
Переходим к нашему множеству.
Разобьем его на пары чисел, сумма которых равна 2199: 1000 и 1199, 1001 и 1198, . 1099 и 1100. И этих пар будет в 2 раза меньше, чем количество чисел в множестве, т.е. 200 : 2 = 100.
Разделим эти пары поровну и получим 2 подмножества с равной суммой.
Значит, да, множество <1000; 1001; . ; 1199>- удивительное.
Теперь из множества <1; 2; 3; 4; 5; 10; 11>будем выделять подмножества, состоящие из 5 элементов так, чтобы они были удивительные.
1) , т.к. 2 + 4 + 10 = 5 + 11.
2) , т.к. 2 + 3 + 10 = 4 + 11.
3) , т.к. 3 + 4 + 5 = 1 + 11.
4) , т.к. 1 + 2 + 3 + 4 = 10.
5) , т.к. 1 + 2 + 3 + 5 = 11.
6) , т.к. 2 + 4 + 5 = 1 + 10.
7) , т.к. 3 + 4 + 5 = 2 + 10.
8) , т.к. 1 + 3 + 11 = 5 + 10.
9) , т.к. 1 + 2 + 11 = 4 + 10.
Ответ: а) да, множество <1000; 1001; . ; 1199>- удивительное;
Не нашли нужную задачу? Предложи свою на нашей странице в ВК!
Два множества, содержащих одинаковые элементы, называются пересекающимися. В этом случае говорят, что множества пересекаются.
Два множества, нс имеющих общих элементов, называются непересекающимися. В этом случае говорят, что множества не пересекаются.
Пример 6.3.1. Множества <1,2,3,4,5>, <а,б,в,г,д>нс псрссскаются.
Непересекающимися являются множество треугольников и множество параллелограммов.
Также нс псрссскаются множества решений уравнений * 3 =3* 2 и *+3=0. •
Пример 6.3.2. Пусть А — множество треугольников, площадь которых равна 6, В — множество прямоугольных треугольников.
А и В — пересекающиеся множества, так как существует треугольник, являющийся одновременно элементом множеств А и В, например треугольник со сторонами 3, 4, 5. Он прямоугольный и имеет площадь.
равную 6 (проверьте эти утверждения). Этот пример нс единственен. Приведите пример еще одного такого треугольника.
Пересекаются также множества решений уравнений х 2 +х=0 и х 2 -х=0, так как оба эти множества содержат число 0. •
Заметим, термины «множества пересекаются» и «множества не пересекаются» определены для двух множеств. Если множеств будет больше, то необходимы уточнения. Например, множества могут нс иметь ни одного общего элемента, но некоторые из множеств могут пересекаться.
Пример 6.3.3. Множества <1,2>, <2,3>и <1,3>не пересекаются в совокупности, то есть нет ни одного элемента, который принадлежал бы каждому из множеств. Однако любая пара этих множеств имеет общий элемент. •
Пусть дана совокупность множеств. Говорят, что множества этой совокупности попарно не пересекаются, если никакие два (различных) множества совокупности нс псрссскаются.
Пример 6.3.4. Множества <1,2,3>, <5,7>, <4,6,8>и <9>попарно не пересекаются. •
Два множества могут находиться в следующих отношениях:
- 1) множества могут быть пересекающимися,
- 2) множества могут быть нспсрссскающимися,
- 3) множества могут быть связаны отношением включения.
Ясно, что первые два отношения исключают друг друга, то есть каждое из предложений «Множества псрссскаются» и «Множества нс псрссскаются» является отрицанием другого. Пересекающиеся множества, в частности, могут быть связаны отношением включения. На первый взгляд может показаться, что нспсрссскающисся множества не могут находиться в отношении включения. Это так, но только с некоторым исключением.
Пример 6.3.5. Рассмотрим два предложения:
Р = «Множества А и В пересекаются»,
Q = «Множество А содержится в множестве В».
Ясно, что РФ(). Оказывается, обратное утверждение в общем случае тоже неверно, то есть ()ФР. Контрпример: Л=0, В — любое. Как известно, 0сЯ, но это непересекающиеся множества.
Если же исключить случай пустого множества, то Q => Р. Действительно, берем любой элемент а из А. Так как A
Встретилось задание из раздела о динамическом программировании, которое вызывает у меня трудности. Необходимо построить алгоритм, который по заданному множеству определяет, можно ли его разбить на три части, в которых суммы всех элементов будут равны. Например:
[1, 2, 3, 4, 4, 5, 8] -> <1,8>, <4,5>,
Очевидно, что если сумма всех элементов не делится на 3, то множество не содержит такого разбиения (самая простая часть:) ). Но как действовать дальше? Вроде как мы должны проверять, к какому подмножеству у нас относится a_i элемент.
Но все это формализовать и прикрутить динамику не получается.
Буду признателен, если сможете направить на истинный путь.
Загрузка...
