Would I apply max/min to find out how many of each bird to get 200 birds for $200?

4,226

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).

Share:
4,226

Related videos on Youtube

imparante
Author by

imparante

Updated on March 12, 2020

Comments

  • imparante
    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
      Joffan over 8 years
      If 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
      imparante over 8 years
      No, I was overthinking it. I was starting to look at writing a linear program for this and about to go for overkill.
    • Admin
      Admin over 8 years
      Very similar to this question.
    • JMoravitz
      JMoravitz over 8 years
      Indeed, 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
      imparante over 8 years
      How would you work that out? Do you have a link to the modular arguments on the money and number of birds and brute force?