Silver Prospector Problem (General Case)

[SSequence]

Here is a a description of the problem:
http://mathcentral.uregina.ca/QQ/database/QQ.09.99/jackson2.html
http://mathcentral.uregina.ca/QQ/database/QQ.09.07/h/shanna1.html

The question is also in one of Martin Gardner's puzzle books. I was thinking about the solution of the problem for a general input (any non-negative integer).

It is reasonably clear that for large enough values, eventually there are going to be input values where a switch to a higher base would be made (in the solution --- using minimum number of pieces).

Take the example of 999:
100 length --- 9 pieces
10 length --- 9 pieces
1 length --- 9 pieces

This division is likely not the solution for 999 but as we increase the input (say 9999) this probably becomes a better approximation to the solution. And eventually higher and higher bases (and possibly some combinations of higher and lower bases too?) would be used in solutions.

=====

But there is also the question of an elegant (relatively easy to describe) and reasonably efficient method for values that don't admit a direct solution.
For example, input values like 31,63, etc. have direct solutions (it seems "apparently" that eventually all base values will be used in at least one direct solution).

There is also the question of input values for which there are more than one solutions (that is, two different divisions that use the same number of pieces). Can one find an example of their existence ... or disprove their existence mathematically.

 

[wle]

It is reasonably clear that for large enough values, eventually there are going to be input values where a switch to a higher base would be made (in the solution --- using minimum number of pieces).

Take the example of 999:
100 length --- 9 pieces
10 length --- 9 pieces
1 length --- 9 pieces

That's a total of 27 pieces. Using doubling lengths you only need ten: 999 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 488.

 

[SSequence]

Yes, you are right. I didn't imply otherwise. I think I might be wrong about the use of arbitrarily higher bases in general solution (and hence the general solution might be fairly simple).

Because for the case of 9999 for example, using base 10 you get 36 pieces. While using powers of 2 one should get there with just around 13/14 pieces.

And then the following identity is suggestive of why a base such as 10 may never be used:
10*x<(2^4)*x
So that's an increase of roughly 9 pieces compared with 4 pieces. I would have to check whether one could make a similar guess for bases lower than 10.

Edit:
It also seems that perhaps one can make the pigeonhole argument (like in one of the links in my first post) to conclude that base-2 would always give the best solution?

Though I think that wouldn't prove or disprove multiplicity of solutions (for arbitrarily large inputs).
There is one simple example of multiple solutions for input=8.
3,3,1,1
1,2,4,1

 

[wle]

It also seems that perhaps one can make the pigeonhole argument (like in one of the links in my first post) to conclude that base-2 would always give the best solution?

It seems fairly straightforward. If you have $k$ pieces then you can make at maximum up to $2^{k}$ different lengths including zero (you can only use or not use each piece). If the total length is $N$ then you need to be able to make $N + 1$ different lengths (all the integers between $0$ and $N$). So the number of pieces $k$ has to satisfy $2^{k} \geq N + 1$. (For $N = 999$ for example, the smallest integer satisfying this condition is $k = 10$, so you cannot make all the lengths between $0$ and $999$ with less than ten pieces.)

You can always attain this using the kind of doubling I described (cut a piece off of length 1, then 2, then 4, then 8, and so on, until you've used all the length or the remaining length is less than the next power of two.)

 

[SSequence]

Yeah, this seems about right. That just leaves the possibility of multiplicity of solutions (for arbitrarily higher inputs). It seems to me that it "may" be ruled out too (but I am not fully clear on this... though the inequality I wrote in post#3 seems to be suggestive of that).

Mainly there seem to be two points:
(1) Whether a higher base can incidentally catch-up very "early on" or not? I gave an example of base-3 in post#3. If the early catch-up part is ruled out (for arbitrarily higher bases) relatively easily, then multiple solutions (arbitrarily high inputs) should definitely not exist either.

The "early on" part is important because similar to inequality in post#3 it seems one could establish that a higher base would start lagging behind base-2 in terms of optimality (will use higher number of pieces).

(2) Showing that non-base solutions are always less efficient ones then the ones that use bases (needs better formalisation).

 

[donpacino]

There are two option with each piece of silver; give them to the landlord, or keep it. That is where the base 2 comes from.

Any higher base will have inefficiencies

 

[SSequence]

Yes, base-2 always gives at least one optimal solution. I made a similar remark in post#3 (the OP had some mistakes).

This doesn't rule out multiplicity of solutions (for arbitrarily large inputs) by itself directly though (I made a detailed comment about it in post#5).

 

[donpacino]

Yes, base-2 always gives at least one optimal solution. I made a similar remark in post#3 (the OP had some mistakes).

This doesn't rule out multiplicity of solutions (for arbitrarily large inputs) by itself directly though (I made a detailed comment about it in post#5).

There are other solutions when they coincide with a base 2 system, but only in that one case, not leading up to that case

 

[donpacino]

IDK what you're trying to argue for? A new way of counting?

 

[SSequence]

For example as I wrote above in post#3:
for input=8 (both are solutions and both use minimum number of pieces)
3,3,1,1
1,2,4,1

What I was just saying in post#5 was that "probably" multiple (optimal) solutions also cease to exist completely after a high enough input value (and I gave some supporting reasoning).
In case it's true, I guess it would be of some interest to know the last input value which will have multiple (optimal) solutions.

By optimal solution above, I mean solution using minimum number of pieces (I think that some of the confusion may be because I just used the word "solution" in place of "optimal solution" in post#3,5).

 

[donpacino]

One can make an argument that the number of solutions would decrease as the number gets higher, not increase.

edit: that is what you said in your last post.

Thats a rather high level problem you are trying to solve. Meta-huristics might be a good way to solve it

 

[wle]

What I was just saying in post#5 was that "probably" multiple (optimal) solutions also cease to exist completely after a high enough input value

That isn't generally true (though it may be true if you restrict what kinds of strategies are allowed and/or for certain numbers like $N = 2^k - 1$).

Probably the worst would be powers of 2. For $N = 2^{k}$ you need at least $k + 1$ pieces. The strategy I described in post #4 is to split this as $$\begin{equation}
N = 2^{k} = \sum_{j=0}^{k-1} 2^{j} + 1 \,.
\end{equation}$$ Since you have two pieces of length 1 anyway another strategy is to cut off two pieces of length 1, then length 3, then lengths 6, 12, 24, etc. (so that each length is one more than the sum of all the previous lengths), until the remaining length is less than the next length in the sequence, i.e., write $N = 2^{k}$ as $$\begin{equation}
N = 1 + 1 + \sum_{j=0}^{k-3} 3 \cdot 2^{j} + \bigl( 2^{k-2} + 1 \bigr) \,.
\end{equation}$$ This uses $1 + 1 + (k - 2) + 1 = k + 1$ pieces. For $k \geq 3$ the splitting is different from the one above, and it's easy to check that it still adds back up to $2^{k}$: $$\begin{eqnarray}
N &=& 1 + 1 + 3 \cdot \sum_{j=0}^{k-3} 2^{j} + \bigl( 2^{k-2} + 1 \bigr) \nonumber \\
&=& 3 + 2^{k-2} + 3 \cdot \bigl( 2^{k-2} - 1 \bigr) \nonumber \\
&=& 4 \cdot 2^{k - 2} \nonumber \\
&=& 2^{k} \,.
\end{eqnarray}$$

 

[SSequence]

That isn't generally true (though it may be true if you restrict what kinds of strategies are allowed and/or for certain numbers like $N = 2^k - 1$).

Probably the worst would be powers of 2. For $N = 2^{k}$ you need at least $k + 1$ pieces. The strategy I described in post #4 is to split this as $$\begin{equation}
N = 2^{k} = \sum_{j=0}^{k-1} 2^{j} + 1 \,.
\end{equation}$$ Since you have two pieces of length 1 anyway another strategy is to cut off two pieces of length 1, then length 3, then lengths 6, 12, 24, etc. (so that each length is one more than the sum of all the previous lengths), until the remaining length is less than the next length in the sequence...

You are absolutely right. So my guess in post#5 wasn't correct. I wonder how easy or difficult would be to find all the solutions (for a given input).

And whether there are certain (simple) sequences for which there are only unique solutions (probably an easier problem than the above one).