Elephant VS Horse Powers

Relevant wiki: Linear programming algorithms

Let $x$ be the amount of logs $1$ elephant could drag and $y$ be the amount for each horse.

For $1$ log, $x\geq 1$ because we know that one elephant could at least drag one log. On the other hand, $\dfrac{1}{3} \leq y \leq \dfrac{1}{2}$ because we know that only $2$ horses only couldn't complete the task and would need at least $3$ horses.

Similarly, for $3$ logs, we would obtain: $\dfrac{3}{2}\leq x \leq3$ and $\dfrac{3}{7} \leq y \leq \dfrac{3}{6}$

Finally, for $4$ logs, we would obtain: $\dfrac{4}{3}\leq x\leq2$ and $\dfrac{4}{10} \leq y \leq \dfrac{4}{9}$

By combining all constraints, we can conclude that $\dfrac{3}{2}\leq x\leq 2$ and $\dfrac{3}{7} \leq y \leq \dfrac{4}{9}$

From the last information, for $2$ logs, $x+y \geq 2$ . Then we can set up a linear programming for these inequalities as shown below:

The shaded area indicates the possible values of $x$ and $y$ , and so the minimal capacity lies within the four vertices of the polygon, specifically either on the point $(\dfrac{11}{7}, \dfrac{3}{7})$ or $(\dfrac{14}{9},\dfrac{4}{9})$ .

Taking the ratios from those points we will get the ratio of $\dfrac{x}{y}$ as $\dfrac{11}{7} \times \dfrac{7}{3} = \dfrac{11}{3} \approx 3.67$ or $\dfrac{14}{9} \times \dfrac{9}{4} = \dfrac{14}{4} =3.5$ .

However, the ratio of the price is only $\dfrac{25}{8} = 3.125$ . Thus, it will be more cost-effective to buy elephants than the horses, and the strategy would be to buy as many elephants as possible and to compensate with some horses when some residual work load is left.

To ensure that, we have to think of the worst case scenario with least possible capacity of the elephants, which would be on point $(\dfrac{14}{9},\dfrac{4}{9})$ .

For $7$ logs, $7\times \dfrac{9}{14} = \dfrac{9}{2} =4.5$ . Then we would have two options: to buy $5$ elephants or to buy $4$ elephants plus $2$ horses, which would suffice half of the elephant's capacity or about $\dfrac{3.5}{2} =1.75$ horses. Clearly, the latter option is cheaper. Therefore, we need to invest at least $4\times 25 + 2\times 8 = \boxed{116}$ gold coins.

$$

Checking on point $(\dfrac{11}{7}, \dfrac{3}{7})$ , $7\times \dfrac{7}{11} = \dfrac{49}{11} \approx 4.45$ . Again, $4$ elephants should be bought and $\dfrac{5}{11} \times \dfrac{11}{3} = \dfrac{5}{3} \approx 1.67$ or $2$ horses should be compensated to minimize the cost.