Текстовые задачи из Абитуриентского Тестирования

[Гоша]

Помогите подготовиться к поступлению в ВУЗ. Объясните решение следующих задач:

1. Имеются 2 слитка золота разной пробы (концентрации): первый 20 г., второй - 60 г. От обоих слитков одновременно требуется отрезать по х г. каждый и отрезанный кусок первого слитка сплавить с остатком второго, а кусок второого - с остатком первого. При каком х качество золота в обоих слитках будет одинаковой?

-------------------------------------------------Варианты ответов---------------------------------------------

1) 10 2) 12 3) 15 4) 20 5) Ни при каком

2. Петя, Вася и Толя в течение часа бегали по круговой дорожке с постоянными скоростями в оном направлении, причем Петя с Васей стартовали из одной точки, а Толя из другой. Сколько раз Толя мог обогнать Васю при условии, что после старта Петя обогнал Васю 8 раз, а Т олю 2 раза?

-------------------------------------------------Варианты ответов---------------------------------------------

1) 6 2) 5 или 6 3) 6 или 7 4) 5, 6 или 7 5) Нет правильного

3. Из деталей двух видов делают 7-местные и 12-местные клетки для животных. На одну 7-местную клетку уходит 7 деталей первого вида и 3 второго, а на одну 12-местную - 12 и 5 деталей соответственно. Наибольшее суммарное кол-во мест, которое можно создать из 155 деталей первого вида и 62 леталей второго?

Не обязательно писать все решение объясните главное суть задач и подход к ним. Заранее благодарен

[faruk]

Похоже, господа ученые считают ниже своего достоинства помочь с решением школьных задач.
А между тем задача N3 не такая уж простая.



Как видно из диаграммы, последовательно приблизиться к максимуму не получается.
Можно эту задачу решить не перебором чисел, а аналитически (алгебраически)?

[незваный гость]

Пусть $x$ -- количество 7-местных клеток, $y$ -- 12-местных. Тогда мы имеем ограничения $7x + 12y \le 155$, $3x + 5y \le 62$, и максимизацию функционала $7x + 12y$. Уравнение $7x + 12y = 1$ имеет решенение в целых числах $x = 7 - 12t$, $y = -4 + 7 t$. Отсюда для целого $m$ (максимума) имеем $x = 7 m - 12t$, $y = -4 m + 7 t$. Подставляя в ограничения получаем: $m \le 155$, $m - t \le 62$. Кроме того, надо считаться с неотрицательностью количеста клеток. Выпишем все неравенства относительно $t$: $ m - 62 \le t$ (второе ограничение), $t \le \frac{7m}{12}$ (неотрицательность $x$), $\frac{4m}{7} \le t$ (неотрицательность $y$). Объединяя первое и второе неравенство, получаем неравенство для $m$: $ m - 62 \le \frac{7m}{12}$, откуда $ m \le \frac{62 * 12}{5} \approx 148.8$. В силу целостности, $ m \le 148$. Имееем (при $m = 148$) $\frac{148 \cdot 4}{7} \le t \le \frac{148 \cdot 7}{12}$, $ 148 - 62 \le t$, откуда $ t = 86$. Теперича умозаключаем $x = 4$, $y = 10$.

В целом это относится к дискретной оптимизации, которая по традиции весьма тяжела. Нам просто повезло.

[Гоша]

У! Не думал что все на столько сложно Задачи расчитаны на 3-4 минуты а я эту уже 2 дня решить не могу.
To: незванный гость
Спасибо!

[Dan_Te]

Цитата:

Похоже, господа ученые считают ниже своего достоинства помочь с решением школьных задач.

Может, просто "господам ученым" это не очень интересно? Вы как-то тоже не торопитесь, как я посмотрю.

Как решить 3-ю задачу за 3 минуты.
Определяем, что на одно звероместо уходит одна деталь первого вида, какие бы клетки мы ни делали. То есть, мы не сделаем больше 155 мест, как ни крути.
С другой стороны, на одно звероместо уходит не менее 5/12 деталей 2 вида, так что мы сделаем не более 62/(5/12)<149 мест.
Это значит, что если мы будем рассчитывать клетки только исходя из деталей второго вида, то деталей первого вида нам стопудово хватит. Так что про них можно просто забыть.

Теперь нам надо оптимально израсходовать 62 детали второго вида. Быстро прикидываем два варианта:
либо делаем по максимуму больших клеток (12 штук) и оставляем две детали без дела (144 звероместа),
либо расходуем все детали и делаем 10 больших и 4 маленьких, 148 зверомест.

Но ведь мы уже оценили, что 149 мест нельзя сделать. Значит, 148 - это ответ.

[незваный гость]

А можно пояснить, откуда два варианта? Почему бы не рассмотреть (2, 11) ->146?

Я согласен с Вашим решением в том смысле, что Вы доказали, что больше 148 быть не может, и что 148 -- может. Мой вопрос -- из каких соображений Вы выбирали пример.

[Dan_Te]

Черт Вы правы, это тоже надо рассматривать. Получается не 2, а 3 варианта.

[незваный гость]

Ну хорошо, а как насчет (9, 7) -> 147?

И почему надо начинать с максимального числа больших клеток? Ведь следующий по количеству посадочных мест пример - (9,7), а не (7, 8) и не (2, 11)? То есть далек от максимума.



Диаграмма выше -- максимально количество посадочных мест в зависимости от количества больших клеток ($y$). Видно, что у нее много экстремумов. Посему и вопрос -- а как выбирать примеры?

[Dan_Te]

Нет смысла рассматривать варианты, при которых маленьких клеток больше четырех, поскольку пять маленьких клеток требуют столько же деталей, сколько и три больших, а зверомест дают на одно меньше.

На самом деле, там есть еще одно соображение, из-за которого я изначально рассмотрел только два варианта, но меня заломало его описывать, к тому же оно не очень строгое. Вот оно: очевидно, нам надо забить по максимуму больших клеток, а потом думать. Либо мы (1) заменяем большие клетки маленькими и тем самым используем оставшиеся детали, либо (2) оставляем максимальное количество больших клеток, но тогда будут незадействованные детали. Надо просто понять, что выгоднее.
Но в любом случае, какой бы из вариантов (1) и (2) ни был более выгодным, по всей видимости, не имеет смысла останавливаться на полпути. То есть, промежуточный вариант, коим является (2,11) (мы и одну большую клетку заменили, и одну деталь не используем), будет менее эффективным, чем один из крайних вариантов.

Надеюсь, я достаточно внятно написал =))

[незваный гость]

Да, конечно. Я бы, по въедливости, считал бы три варианта. Но Вы правы...

[незваный гость]

К первой задаче -- предположите пробу (то есть, количество золота на единицу веса в первом бруске $\lambda$, во втором - $\mu$. Тогда вес чистого золота до отрезания - $20 \lambda$ и $60 \mu$. После переноса / переплавки $x$ грамм, имеем $(20-x) \lambda + x \mu$ и $(60-x) \mu + x \lambda$, а пробы -- $\frac{(20-x) \lambda + x \mu}{20}$ и $\frac{(60-x) \mu + x \lambda}{60}$ соответственно. Приравниваем, и получаем уравнение для $x$. Ответ -- 15.