11
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ Can you borrow Mike's gold coin? $\endgroup$ – StephenTG Jul 24 '17 at 15:54
  • 4
    $\begingroup$ Are we allowed to end up with more than N gold coins? I.e., is the goal "have exactly N" or "have at least N"? $\endgroup$ – Gareth McCaughan Jul 24 '17 at 16:44
  • $\begingroup$ Is it decreed that we must go iteratively? ie, for k = k + 1, pay 1, k must traverse all whole numbers [1,2,3,4,5,...] or can we have k be any sequence, say 1 then 4 then 8? $\endgroup$ – abbaf33f Jul 24 '17 at 17:00
  • 3
    $\begingroup$ I think I'm confused about how many coins you start with. You said you have one coin from the cave, but if the fee for each machine is a coin, then won't you not have enough to use either machine the first time? $\endgroup$ – MMAdams Jul 24 '17 at 21:05
  • 3
    $\begingroup$ You need to earn at least N coins. And one cent is different from one coin. The fees are measured in cents, while the coins are what you put tin the machine and what you get from the machine. You start with one coin and need to spend the least number of cents to make N coins. $\endgroup$ – William Nathanael Jul 25 '17 at 6:31
7
$\begingroup$

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))
$\endgroup$
  • $\begingroup$ I think I found a counter example with N = 16. Use adding machine once, and doubling machine 3 times. Fee = 1 + 1 + 2 + 4 = 8. Your lower bound in this case is 8.44 $\endgroup$ – Greg Petersen Jul 31 '17 at 15:03
  • $\begingroup$ @2012rcampion Greg is right, but your lower bound is quite close. Here is a pretty picture of the optimal cost for the first 10,000 values of N oscillating between your upper and lower bounds. I'm beginning to think there is not a clever solution to this problem... $\endgroup$ – Mike Earnest Jul 31 '17 at 22:30
  • $\begingroup$ @MikeEarnest Are we sure your not trying to solve a much harder problem then is stated? You are looking for exactly N when he says in the comments it's ok to exceed N. However, I'm loving the nerding out on trying to solve the much more difficult problem! Kudos to you gentlemen! $\endgroup$ – Greg Petersen Aug 1 '17 at 20:15
  • $\begingroup$ @GregPetersen I'm not looking for exactly N, which is why the constraint I have is $2^d(i+1)\ge N$ and not $2^d(i+1)= N$. Requiring the exact value of N makes the problem much easier, since there is a unique way to use the machines to get exactly N coins. The cost to make N would be $2^(d-1)-1+i(i-1)/2$, where d is the number of bits N has written in binary, and i is the number of those bits which are 1. $\endgroup$ – Mike Earnest Aug 3 '17 at 15:36
  • $\begingroup$ @MikeEarnest There isn't a unique way to get N though. Take N=2. You can either use the adding machine twice or the doubling machine once. As you go further in N, the degeneracy explodes. For N=4, you can double twice, or add 4 times, or double than add twice, or add once then double. $\endgroup$ – Greg Petersen Aug 3 '17 at 19:34
3
$\begingroup$

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

$\endgroup$

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.