Правильный ответ и набор весов прислали многие, но только трое (
ilya_dogolazky, chyyr и e2pii1) дали себе труд доказать, что 40 - действительно максимум. Под катом - их доказательство, слегка разжеванное:Пусть есть четыре целых разновеса Х1, Х2, Х3 и Х4. Когда мы уравновешиваем груз, то фактически образуем такую сумму: А1*Х1 + А2*Х2 + А3*Х3 + А4*Х4, где коэффициенты А1, А2, А3 и А4 могут принимать значение +1 (разновес на чашке, противоположной грузу), - 1 (разновес на той же чашке, что и груз) и 0 (разновес не используется).
Сколько же существует таких сумм? Первый коэффициент можно выбрать тремя способами (0, 1, -1). На каждый из этих способов тремя способами можно выбрать второй - итого получается 9. На каждый из этих девяти способов тремя способами можно выбрать третий - итого 27. И на каждый из них тремя способами выбираем четвертый - итого 81.
Теперь выкинем отсюда тот случай, когда все коэффициенты равны нулю. Остается 80 сумм. Но у них на каждую положительную сумму приходится отрицательная (если в сумме поменять плюсы на минусы и наоборот, она поменяет знак), а нас интересуют только положительные. Их всего 40, и большее количество весов никакими разновесами не взвесить.
Для сорока есть решение, предложенное многими:
1, 3, 9, 27.
Спасибо всем участникам!
