Mike's Coin Duplicator

Question

^{This is my first mathematical puzzle on the site. To be honest, I don't know if this should go to M.SE or here. Any grammatical or backstory edits are welcome, as I realized that my English is not that good.}

---

Your friend, Mike, invited you to go treasure hunting in a nearby cave. He told you that he expected $2N$ gold coins to be found. What an offer! Without much hesitation, you agree to accompany him on the trip.

After a couple of nights dreaming about the joy of having $N$ coins, the day finally came. You and Mike went to the cave, and to your surprise, only $2$ coins are found! Angrily, you give one to Mike and take the other home.

Few days later, Mike phoned you that he had invented a new machine which can increase the number of your coins. Of course, since you are his best friend, he invited you to be the first person to try it.

When you arrived at Mike's house, you noticed that there are actually 2 machines. Mike then explained,

All right, you can see here that there are 2 machines. However, I'm so sorry to tell you that you must pay some amount of money in order to use them. At first, the fee of each of them is only $1$ cent. Afterwards, it will change, one at a time. And this is how the machines work.

When you put in $k$ coins into machine A, it will give you back $k+1$ coins. However, after that, the fee will increase by $1$ cent every time.

When you put any number of coins into machine B, it will double your coins. However, the fee will also double every time after you use it.

Ugh! What a con friend you have here! Is he trying to get his revenge after you tricked him on his bakery? Still, you want to achieve your dream of having $N$ gold coins. How much cents do you need to pay the machines at the very least to achieve it?

---

Clarifications:
1. You can put any number of coins into any machine.
2. The answer must be in a form of a function of $N$

Answer 1

First Thoughts

Suppose you use the incrementing machine $i$ times and the doubling machine $d$ times. The cost will be $i(i+1)/2 + 2^{d}-1$. We want to minimize this, which is equivalent to minimizing $i(i+1)/2 + 2^{d}$.

It is most efficient to save all of the doublings for last (since $2(k+1)>2k+1)$. Therefore, in the best case, you will end up with $2^d\cdot (i+1)$ coins. Therefore, our problem is to

Minimize:    $i(i+1)/2 + 2^{d}$
Subject to: $2^d(i+1)\ge N$

---

Appproximate Answer

Let's simplify by first assuming that $N$ is a power of $2$, so $N=2^n$. In this case, you can satisfy the constraint $2^d(i+1)\ge N$ exactly by choosing $i+1=2^{n-d}$. The cost in this case is $$ i(i+1)/2 + 2^{d}= (2^{n-d}-1)2^{n-d-1}+2^d\approx 2^{2n-2d-1}+2^d $$ Only the larger of the two exponents matters ($2^a$ is much greater than $2^b$ when $a>b$), so we want to minimize $\max(2n-2d-1,d)$, which occurs when $d=2n/3$ rounded up.

Therefore, at least roughly, the answer is to use the incrementing machine until you have just less than $\sqrt[3]{N}$ coins, then use the doubling machine until you have at least $N$ coins.

---

Computation

To summarize the results in the previous section, the optimal strategy for $N$ is to use the doubling machine $d=\frac23\log_2 n$ times and to use the other machine $i=2^{\log_2 N -d}=N^{1/3}$ times. This results in a cost of approximately $N^{1/3}\cdot N^{1/3}/2 + 2^{\frac23\log_2 n}=\boxed{1.5N^{2/3}.}$

This heuristic works pretty well for large $N$. Namely, for every $N$ between 10,000 and 100,000, the optimal cost is between 1.47 and 1.7 times $N^{2/3}$. The Python code which checks this is below.

from math import ceil,log

def cost(i,d):
    return (i*(i+1))/2 + 2**d - 1

def optimal_cost(N):
    costs = []
    for d in range(int(ceil(log(N,2)))):
        i = ceil(N/2.0**d) - 1
        costs.append( cost(i,d) )
    return min(costs)

ratios = [optimal_cost(N)/N**(2.0/3) for N in range(10**4,10**5)]
print (min(ratios),max(ratios))

Answer 2

This is a too-long-for-a-comment supplement to Mike Earnest's answer to obtain simple upper and lower bounds on the cost.

We know that the cost for $i$ uses of the incrementor and $d$ uses of the doubler, the cost is:

$$ c=\frac{i(i+1)}{2} + 2^d - 1 \tag{1} $$

And the maximum number of coins obtainable is:

$$ n = (i + 1) 2^d \tag{2} $$

We can rearrange $(2)$ to get, for a given $n$ and $d$, the smallest $i$ that can get at least $n$ coins:

$$ i = \left\lceil\frac{n}{2^d}\right\rceil - 1 $$

(Where $\lceil\cdot\rceil$ is the ceiling function, i.e. "round up to the next integer.")

We can then substitute this into $(1)$ to get an (exact) expression for $c$ in terms of $n$ and $d$ only.

$$ c = \frac 1 2\left\lceil\frac{n}{2^d}\right\rceil\left(\left\lceil\frac{n}{2^d}\right\rceil - 1\right) + 2^d - 1 \tag{3} $$

We can use the fact that $x\le\lceil x \rceil$ to bound $c$ from below:

$$ \frac 1 2\left(\frac{n}{2^d}\right)\left(\frac{n}{2^d} - 1\right) + 2^d - 1 \le c $$

I'll substitute $\beta=2^d$ and expand:

$$ \frac{n^2} 2 \beta^{-2} - \frac n 2 \beta^{-1} + \beta - 1 \le c \tag {4} $$

Minimize with respect to $\beta$ by setting the derivative to zero:

$$ -n^2\beta^{-3}+\frac n 2 \beta^{-2} + 1 = 0 \\ \beta^3 + \frac n 2\beta - n^2 = 0 $$

This equation is cubic in $\beta$, so its solution is a bit tedious; using Wikipedia's notation, we have:

$$ a=1,\ b=0,\ c=\frac n 2,\ d=-n^2 \\ \Delta = -4\cdot \frac{n^3}{8}-27\cdot n^4 = -n^3\left(27n+\frac 1 2\right) \\ \Delta_0 = -\frac 3 2 n \quad \Delta_1 = -27n^2 \\ \begin{align} C &= \sqrt[3]{\frac{-27n^2 - \sqrt{27^2 n^4+4\frac{27}{8}n^3}}{2}} \\ &= \sqrt[3]{\frac{-27n^2 - 27n^2\sqrt{1+\frac 1 {54n}}}{2}} \\ &= -3n^{2/3}\sqrt[3]{\frac{1+\sqrt{1+\frac{1}{54n}}}{2}} \end{align} $$

At this point, notice that the expression inside the cube root is almost equal to $1$. If we take a first-order series expansion, we get:

$$ \begin{align} \sqrt[3]{\frac{1+\sqrt{1+\frac{1}{54n}}}{2}} &\approx \sqrt[3]{\frac{1+1+\frac{1}{108n}}{2}} \\ &\approx \sqrt[3]{1+\frac{1}{216n}} \\ &\approx 1+\frac{1}{648n} + O\!\left(n^{-2}\right) \end{align} $$

The non-constant terms are small enough that we can ignore them going forward. Continuing with solving the cubic:

$$ \begin{align} \beta &= -\frac 1 3\left(b+C+\frac{-3n}{2}\frac 1 C \right) = -\frac{C}{3} + \frac{n}{2C} \\ &\approx n^{2/3}-\frac{n}{6n^{2/3}} = n^{2/3}-\frac{1}{6}n^{1/3} \\ \end{align} $$

We will need $\beta^{-1}$; we can compute a series approximation for it as well:

$$ \begin{align} \beta^{-1} &\approx \frac{1}{n^{2/3}-\frac{1}{6}n^{1/3}} \\ &= \frac{n^{-2/3}}{1-\frac{1}{6n^{1/3}}} \\ &\approx n^{-2/3}\left(1+\frac{1}{6n^{1/3}}+\frac 1 {36n^{2/3}}\right) \\ &= n^{-2/3}+\frac{1}{6}n^{-1}+\frac 1 {36} n^{-4/3} \end{align} $$

Finally we substitute back into $(4)$ to get our lower bound:

$$ \frac{n^2} 2 \left(n^{-2/3}+\frac 1 6 n^{-1}+\frac 1 {36} n^{-4/3}\right)^2 - \frac n 2 \left(n^{-2/3}+\frac 1 6 n^{-1}\right) + \left(n^{2/3}-\frac 1 6 n^{1/3}\right) - 1 \le c \\ \frac 1 2 n^{2/3} + \frac 1 6 n^{1/3}+\frac 1 {72} + \frac 1 {36} - \frac 1 2 n^{1/3} - \frac 1 {12} + n^{2/3} - \frac 1 6 n^{1/3} - 1 \le c \\ \boxed{\frac 3 2 n^{2/3} - \frac 1 2 n^{1/3} - \frac{25}{24} \le c} $$

Note the boxed statement is not completely accurate; I neglect the higher-order terms, which do decrease the "true" lower bound when taken into account. However, the next term is $\frac 1 {216}n^{-1/3}$, which becomes vanishingly small for large $n$, and the above bound holds for all $n\le 100\,000\,000$.

---

Here I'll repeat equation $(3)$:

$$ c = \frac 1 2\left\lceil\frac{n}{2^d}\right\rceil\left(\left\lceil\frac{n}{2^d}\right\rceil - 1\right) + 2^d - 1 \tag{3} $$

If we bound the ceiling function from above by $\lceil x \rceil \lt x+1$, then $(3)$ becomes quadratic in $n$:

$$ c \lt \frac 1 2\left(\frac{n}{2^d}\right)\left(\frac{n}{2^d} - 1\right) + 2^d - 1 \\ = \frac 1 2 \left(\frac{n}{2^d}\right)^2 + \frac 1 2 \left(\frac{n}{2^d}\right) + 2^d - 1 $$

Every time $d$ increases by one, the parabola becomes twice as wide and moves up twice as high, intersecting the previous one. These intersection points are where it becomes advantageous to increase $d$ by one, and they will determine the upper bound. We'll look at the intersection between curve $d$ and $d+1$. Using the same $\beta$ substitution as before (but now with $2^{d+1}=2\beta$), we have:

$$ \frac{n^2}{2\beta^2}+\frac{n}{2\beta}+\beta-1 = \frac{n^2}{8\beta^2}+\frac{n}{4\beta}+2\beta-1 \\ \frac 3 8 n^2\beta^{-2}+\frac 1 4 n \beta^{-1} - \beta = 0 \\ \beta^3 - \frac 1 4 n \beta - \frac 3 8 n^2= 0 $$

We once again encounter our friend the cubic. I'll cut right to the chase, and tell you that the solution is:

$$ a = 1,\ b = 0,\ c = -\frac 1 4 n,\ d = -\frac 3 8 n^2 \\ \Delta = -\frac 1 {64} n^4 \left(243 - \frac 4 n\right) \\ \Delta_0 = \frac 3 4 n \quad \Delta_1 = - \frac {81}{8} n^2 \\ C \approx -\frac 9 2 \left(\frac n 3\right)^{2/3} + \frac 1 {486}\left(\frac n 3\right)^{1/3}\\ \beta \approx \frac {3} 2 \left(\frac n 3\right)^{2/3} + \frac 1 6 \left(\frac n 3\right)^{1/3} \\ \boxed{c \lt \frac 7 2 \left(\frac n 3\right)^{2/3} + \frac{13}{18} \left(\frac n 3\right)^{1/3} - \frac{28}{27}} $$

The same caveats as before apply; the "actual" upper bound is slightly higher, but the difference becomes negligible for large $n$, and the bound holds for all $n\le 100\,000\,000$.