Взвешивание

[wpoms.]

Имеется `n` блоков, вес каждого из них выражается целым числом фунтов и он меньше `n` фунтов. Общий вес этих `n` блоков меньше `2n` фунтов. Докажите, что блоки могут быть разделены на две группы так, чтобы общий вес блоков в одной из групп был равен точно `n` фунтов.

@темы: Комбинаторика

Comments

[Adjirranirr]

Первый контрпример — `n` блоков массы `1`. На две непустых группы они разделены быть не могут. Будем считать, что есть хотя бы один блок с массой, превышающей `1`.

Если каждый блок весит не менее `2`, то их суммарная масса не меньше `2n`, что противоречит условию; значит, есть хотя бы один блок с массой `1`.
Для начала, пусть среди `n` данных блоков нет блоков с массой `2`.
Пусть `n <= S < 2n` — суммарная масса всех блоков, `k < n` — количество блоков с массой `1`, тогда блоков с массой не меньше `3` фунтов `n - k` штук. Тогда `2n > S >= k + 3 (n - k) = 3n - 2k => n < 2k`, и `k > n/2`. Разделим теперь набор из всех `n` блоков на `[(n + 1)/2] >= n/2` блоков массы `1` и «все остальные». Суммарная масса «всех остальных» не меньше `n/2`, так как в противном случае выполнялось бы `S < n`, что невозможно. Выберем из «всех остальных» подмножество с максимальной суммарной массой, меньшей `n`, и добавим недостающее число блоков массы `1` (это, очевидно, всегда возможно).

Пусть теперь среди `n` блоков есть `p >= 1` блоков с массой `2`. `n - p` блоков (предварительно убрав все блоки массы `2`) разделим на две группы так, чтобы масса одной из них была равна `n - p` по вышеописанному алгоритму. В той группе, масса которой равна `n - p`, обязательно найдется хотя бы один блок массы `1`. Если `p` четно, то добавив в эту группу `p/2` блоков массы 2, мы получим группу массы `n`. Если же `p` нечетно, то убрав один блок массы `1` и добавив `(p + 1)/2 <= p` блоков массы `2`, опять же получим группу суммарной массы `n`.