Чему равно минимальное значение выражения pq + rs + uvw + xyz , где вместо букв должны стоять цифры от 0 до 9 по одному разу каждая?

задан 30 Янв '14 20:05

изменен 31 Янв '14 15:08

Deleted's gravatar image


126

10|600 символов нужно символов осталось
2

Отметим для начала следующее: если имеется четыре различных (положительных) числа, то для достижения минимального значения суммы произведений пар нужно перемножать самое маленькое с самым большим, а также два "средних". Например, для чисел 3, 4, 7, 9 соответствующее минимальное значение будет равно $%3\cdot9+4\cdot7=55$%. В противном случае, если группировка устроена по другому принципу, то в выражении $%ab+cd$%, где $%a$% -- самое большое число, а $%b$% -- не самое маленькое, можно считать, что $%b > c$%. Тогда значение выражения $%ac+bd$% будет меньше. Действительно, $%(ab+cd)-(ac+bd)=a(b-c)-d(b-c)=(a-d)(b-c) > 0$%. Этот принцип мы будем несколько раз применять.

Сначала убедимся в том, что цифра 0 находится в одной из троек, а не в паре. Если бы оно было в паре, то умножалось бы на цифру, не превосходящую 9. При этом в одной из троек заведомо присутствуют две цифры, произведение которых равно как минимум $%3\cdot4=12$%. Тогда выгодно совершить обмен, домножая 0 не на 9, а на самое большое из чисел.

Теперь, когда мы знаем, что 0 входит в тройку, мы можем сделать вывод, что вместе с ним там находятся две самые большие цифры 8 и 9. В противном случае одну из них можно обменять на 8 или 9, уменьшая общее значение суммы. Тем самым, задача свелась к минимизации выражения вида $%pq+rs+uvw$% для цифр от 1 до 7.

Если допустить, что 1 входит в пару, а не в тройку, то единица домножается самое большее на 7, а в тройку при этом входят две цифры, произведение которых больше. Тогда снова возможен обмен с уменьшением. Считая, что $%w=1$%, мы теперь минимизируем выражение вида $%pq+rs+uv$% для цифр от 2 до 7.

Ясно, что 2 должно быть в паре с самым большим, то есть с 7. Оставшиеся цифры группируются по принципу 3 с 6, 4 с 5. Это даёт значение суммы, равное $%2\cdot7+3\cdot6+4\cdot5=52$%, и оно будет наименьшим. Самих способов группировки при это будет несколько, так как 1 можно "отдать" любому из трёх произведений.

ссылка

отвечен 31 Янв '14 1:02

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×56

задан
30 Янв '14 20:05

показан
1878 раз

обновлен
31 Янв '14 1:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru