Задача по алгебре Набор гирек с целочисленными весами и общим весом n назовём оптимальным, если груз любого целого веса от 1 до n можно единственным способом уравновесить гирьками этого набора (гири одного веса считаются одинаковыми, класть на одну чашу гирьки и груз не разрешается). Докажите, что если для n существует оптимальный набор гирек, не все из которых весят 1, то число n+1 составное.

Предыдущий
вопрос Следующий
вопрос

Докажем это утверждение от противного. Предположим, что для некоторого n существует оптимальный набор гирек, не все из которых весят 1, и число n+1 - простое.

Так как в наборе есть гири с весами больше 1, то существует гирька с весом k > 1. Поставим на одну чашу весы гирьку весом k и n гирек весами 1, на вторую чашу - груз весом n+1. Так как набор оптимален, то существует единственный способ уравновесить гирьки и груз. Это означает, что груз весом n+1 можно уравновесить только с использованием гирьки веса k, что противоречит предположению, что в наборе есть гири не только весом 1.

Таким образом, если для n существует оптимальный набор гирек, не все из которых весят 1, то число n+1 - составное.