2
$\begingroup$

There is a magic transmuter which turns stones into the gold! But this transmuter works weird.

Every time you put a stone or more stones and press a button, it takes that stone into a slot in the machine (there are enough amount of slots in the machine, dont worry), and every time you put some stones and press a button, it takes these stones into other slots, then pressing "Transmute" button at the end, the transmuter starts working and gives you some golds with some rules you are trying to figure out;

You tried to put

  • $3,3,3,1$ stones into the slots and it gave you $3$ golds.
  • $4,3,2,1$ stones and it gave you $6$ golds.
  • $2,2,2,2$ stones and it gave you $0$ gold.
  • $3,2,2,1$ stones and it gave you $5$ golds.

Try to figure out the rule of the machine and then maximize the number of gold you can win with 33 stones you have left!

and

What is the number of golds you cannot win after pressing Transmute button and why?

Note that examples are given for 4 slots only, you can put as many slot as you want with your limited stones.

Adding an example to make it much more simple to understand for the first part (Hint):

$5,4,4,4,3,2,2,1$ stones and it gave you $7+4+4+4+3+1+1=24$ golds.

$\endgroup$
  • $\begingroup$ Does the second question use the $33$ stones or any number of stones? $\endgroup$ – noedne Jun 4 '18 at 20:56
  • $\begingroup$ @noedne any actually. $\endgroup$ – Oray Jun 4 '18 at 21:16
7
$\begingroup$

New answer in light of edited question:

Namely, the added note suggests that we can actually input a pile count differing from 4 piles. The general "piles greater than all piles that follow it" rule still applies, however.

We can do much better now:

For instance, if we just limit ourselves to $x$ 2-piles and $y$ 1-piles, we can attain $xy$ gold at the costs of $2x+y$ stones. This is maximized when $x = 8$ and $y = 17$, for a whopping $136$ gold! (For this, we may use AM-GM, using a third variable $2y' = y$, which implies that the maximum product is attained when $x = y'$. Integer considerations prevent us from actually attaining this, however.) But can we do better if we also use 3-piles? Let us see.
.
Suppose we have $x$ >3-piles, $y$ 2-piles, and $z$ 1-pile. Then our current gold gain would be $xy+xz+yz$. In fact, let's be generous, and add $\frac{x(x-1)}{2}$ gold, assuming the 3-piles also give gold to each other. But if we converted all of our 3-piles into 2-piles and 1-piles equally, then we would instead have $y+x$ 2-piles and $z+x$ 1-piles, which would give us $xy+xz+yz+x^2$ gold. And since $x^2 > \frac{x(x-1)}2$, it follows that we should not have any piles that are greater than size 2.

Second question:

You can win any number of golds, given arbitrarily many stones. For instance, input $1$ 2-pile and $x$ 1-piles and you can get $x$ gold from $x+2$ stones for any positive integer $x$.

Old solution underneath:


I believe that the rule is:

It spits out a number of gold pieces equal to the number of pairs of piles that have a different number of stones. (Perhaps the piles should be decreasing, too, but I don't have evidence to the contrary.)

With this in mind:

First, we should figure out the optimal configurations to get gold. We can observe that the difference between successive piles must be at most 1.
$4,3,2,1$ -> 6 gold / 10 stones (optimal 1,1,1,1 split)
$3,2,1,1$ -> 5 gold / 7 stones (optimal 2,1,1 split)
$2,2,1,1$ -> 4 gold / 6 stones (optimal 2,2 split)
$2,1,1,1$ -> 3 gold / 5 stones (optimal 3,1 split)
$1,1,1,1$ -> 0 gold / 4 stones (optimal 4 split, but why would you do this)
From here, we can observe that one should never take the first option (you may as well take two option 4s) or the fifth option. The remaining options have the property that you "lose" $2$ gold per transaction. So it suggests that we should try to get rid of our $33$ stones in the fewest transactions possible. We can do this in $5$ transactions (for instance, $7+7+7+7+5$) but $4$ is impossible as $4\times7 = 28 < 33$. Hence we will lose 10 gold, and therefore be able to attain $33 - 10 = 23$ gold. (To answer the question, you can't attain $24$ gold, for instance. Unless it means from any amount of stones, for which we can use Froebinus to conclude that the only impossible gold values are $1,2$.)

$\endgroup$
3
$\begingroup$

Solving the linear equations $$3a+3b+3c+d+x=3$$$$4a+3b+2c+d+x=6$$$$2a+2b+2c+2d+x=0$$$$3a+2b+2c+d+x=5$$

yields

$$a=1$$$$b=0$$$$c=-2$$$$d=-4$$$$x=10$$

This is incredible because you can just push "transmute" with no stones (according to this equation) and yield 10 gold every time. If a minimum of 1 stone is required for each slot, this will yield 5 gold. As 5 gold for 4 stone is the best ratio you can get with that requirement, you can get 41 gold by doing 1,1,1,1 8 times and then 2,1,1,1 once.


Upon review, I can solve this set of linear equations instead:

$$3a+3b+3c+d=3$$$$4a+3b+2c+d=6$$$$2a+2b+2c+2d=0$$$$3a+2b+2c+d=5$$

yielding

$$a=3.5$$$$b=-2.5$$$$c=.5$$$$d=-1.5$$

In this case, adding no stones results in no gold which makes sense. You can somehow end up with negative gold for both answers so ... lead?

You will receive the maximum amount of gold based on this solution by putting all 33 gold into the first slot which yields 115.5 gold.

$\endgroup$
  • $\begingroup$ I think this answer conflicts with the second question. $\endgroup$ – noedne Jun 4 '18 at 20:42
  • $\begingroup$ @noedne as written this answers the question fine. That answer is infinite. If we say there can be no x in this regression, i can still do a perfect fit. $\endgroup$ – kaine Jun 4 '18 at 20:43
  • $\begingroup$ An infinite number of golds? Just place an infinite number of stones in the first position! $\endgroup$ – noedne Jun 4 '18 at 20:48
  • $\begingroup$ @noedne you only have 33 stones $\endgroup$ – kaine Jun 4 '18 at 20:52
  • $\begingroup$ Note: since the question was editted this answer is no longer valid. $\endgroup$ – kaine Jun 4 '18 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.