Would I apply max/min to find out how many of each bird to get 200 birds for $200?
As you have to spend all $\$200$, this means:
$2x + 2y + 10z = 200$
And because the total number of birds cannot be more than $200$, therefore:
$40x + 2y + 2z \le 200$
To optimize the solution, meaning than the total number of birds should be as close to $200$ as possible (but not more than $200$). We can first try exactly $200$ birds first:
$40x + 2y + 2z = 200$
Simplifying the first and third equations give $4z = 19x$. Note that all $x, y, z$ are non-negative integers. We shall try the smallest pair of non-negative integers $x$ and $z$ first (because if we choose a larger pair, $y$ will more likely become negative). Since $4$ and $19$ are relatively prime, hence we try $x = 4$ and $z = 19$. Solving the equations give $y = 1$.
In other words, there exists an optimal solution such that we can buy:
$40 \times 4 = 160$ pigeons for $\$8$
$2 \times 1 = 2$ parrots for $\$2$
$2 \times 19 = 38$ falcons for $\$190$
A total of $200$ birds for $\$200$.
In this question we are lucky to get the optimal answer at the first try. It is easy to spot that if we choose a larger pair of $x$ and $z$ (such as $x=8$ and $z=38$), $y$ becomes negative immediately so there won't be another optimal answer.
In the case if there are no solutions for $200$ birds, a way to continue is to reduce the number of birds $200$ to, for example, $198$, then $196$ and so on (we need not try odd numbers because we have to buy any type of birds in even number).
Related videos on Youtube
imparante
Updated on March 12, 2020Comments
-
imparante over 3 years
You are off to a bird market with \$$200$ to purchase $200$ birds. The following are prices of birds in the market
- $40$ Pigeons — \$$2$
- $2$ parrot — \$$2$
- $2$ falcon — \$$10$
If you have to spend the entire \$$200$ and you are not supposed to buy more than $200$ birds, then how many birds will you buy and of which type?
If I don't optimize the solution to be the maximum number of birds in each category. I can obtain an arbitrary number of birds under 200.
- 80 pigeons = \$$4$
- 16 parrots = \$$16$
- 36 falcons = \$$180$
How would I be able to optimize a solution?
-
Joffan over 8 yearsIf I don't want to think too hard, I'll just buy 200 parrots. Assuming I have to buy exactly 200 birds, that is. Otherwise - are there any other criteria?
-
imparante over 8 yearsNo, I was overthinking it. I was starting to look at writing a linear program for this and about to go for overkill.
-
Admin over 8 yearsVery similar to this question.
-
JMoravitz over 8 yearsIndeed, however, if we put the added condition that you need at least one of each bird, and you need to purchase exactly \$200 worth of birds and get exactly 200 birds (and buying only integer multiples of each package of birds), the only potential answer is then 160 pigeons(\$8), 2 parrots(\$2), and 38 falcons (\$190) (found via modular arguments on the money and number of birds and brute force)
-
imparante over 8 yearsHow would you work that out? Do you have a link to the modular arguments on the money and number of birds and brute force?