13
$\begingroup$

You have 99 coins that you need to place into any number of sacks. After doing so, you write on each one the number of sacks that are lighter than that sack. For example, if you put 98 coins into one sack, and 1 coin into another sack, you need to put "1" on the first since only one sack is lighter, and you write nothing on the second since no sack is lighter than that one. You need to ignore sacks which are empty of course.

So

What is the maximum sum you can have with the numbers written on the sacks?

and

What is the maximum product you can have with the numbers written on the sacks?

$\endgroup$
  • 1
    $\begingroup$ Sum and product of what? The numbers written on the sacks? Please make this explicit. $\endgroup$ – jpmc26 May 8 at 4:34
  • $\begingroup$ @jpmc26 it was so obvious so i forgot to add that part, fixed it now, thanks. $\endgroup$ – Oray May 8 at 8:10
13
$\begingroup$

Sum

Put $2$ coins into each of $25$ of the sacks and put $1$ coin into each of $49$ of the sacks.
This makes the total sum $49 \times 25 = 1225$

Product

Put $2$ coins into each of $38$ of the sacks and $1$ coin into each of $23$ of the sacks.
This makes the total product $23^{38}$

Reasoning

We start with the simpler solution of putting $2$ coins into $y$ sacks and $1$ coin into $x$ sacks in each case. This means we'll have $x + 2y = 99$. The sum of the numbers on the sack will be $xy$ and the product will be $x^y$.

Substituting in for $x$ from the initial equation we are maximising, in turn,
Sum: $99 y - 2y^2$
Product: $(99-2y)^y$
on the integers between $0$ and $49$

Although I don't have a proof, moving away from these solutions (to include sacks of more than $2$ coins) seems to reduce the total in both cases.

$\endgroup$
16
$\begingroup$

@hexomino has found optimal solutions with a restricted search space.

Theorem:

There is a solution with as large a sum of sack-labels as possible that doesn't put more than 2 coins into any bag.

Proof:

Suppose the number of sacks containing exactly $k$ coins is $c_k$. Then it's easy to see that the sum of sack-labels is $\sum_{i<j}c_ic_j=\frac12\sum_{i\neq j}c_ic_j=\frac12\left(\left(\sum c_k\right)^2-\sum c_k^2\right)$. Now, suppose we have at least one sack with $k>2$ coins in it. What happens if we take one of those coins out and put it in its own sack? Well, write $n:=\sum c_k$ for the total number of sacks. This increases by 1. At the same time $c_k$ decreases by 1 and $c_1,c_{k-1}$ increase by 1. Note that $1$ and $k-1$ aren't equal since $k>2$. So, $\left(\sum c_k\right)^2=n^2$ increases by $2n+1$; $c_k^2$ decreases by $2c_k-1$; $c_{k-1}^2$ increases by $2c_{k-1}+1$; and $c_1^2$ increases by $2c_1+1$. Hence $\frac12\left(\left(\sum c_k\right)^2-\sum c_k^2\right)$ increases by $\frac12\left((2n+1)+(2c_k-1)-(2c_{k-1}+1)-(2c_1+1)\right)=n+c_k-c_{k-1}-c_1-1$. And $n\geq c_{k-1}+c_1$ because $n$ is the sum of the $c$'s; and $c_k\geq1$ because we assumed we do have a sack of size $k$ to take a coin out of. Hence, our sack-label-sum doesn't decrease when we make this change. So we can keep doing it until we no longer have any sacks with $>2$ coins in, and the sack-label-sum will be at least as big as the one we started with. (Once we are in that situation, the argument above doesn't say that we should keep splitting sacks, because it's invalidated by the fact that when $k=2$ we have $k-1=1$.)

Therefore

@hexomino's solution that assumes no sack has more than 2 coins in it is in fact optimal. (For the sum-of-labels case; I haven't looked at the product-of-labels case.)

Theorem

There is a solution with as large a product of sack-labels as possible that doesn't put more than 2 coins in any sack.

Proof

Same strategy as before: consider turning a sack with $k$ coins into a sack with $k-1$ coins and a new sack with $1$ coin. Let's look in more details at the labels, and for simplicity let's suppose that the sack we do this to is a largest sack: there are no others containing more coins. Sacks with $1$ coin are unlabelled and don't change. Sacks whose coin-count is $>1$ have a label $1$ larger than before because of the new size-$1$ sack EXCEPT that (1) any unaltered sacks of size $k$ have also gained a new size-$k-1$ sack to be bigger than, so their labels increase by $2$ instead of by $1$ and, alas (2) our new sack of size $k-1$ may suffer a decrease in its label, if there were sacks of size $k-1$ that it's no longer bigger than. So, suppose we had $p$ sacks of size $1$, $q$ sacks of size $2\dots k-2$, $r$ sacks of size $k-1$, and $s$ sacks of size $k$. Then $p$ unlabelled sacks become $p+1$ unlabelled sacks; $q$ "small" sacks have their labels increased by $1$; $r$ $k-1$-sacks also have their labels increased by 1; one reduced-size sack has its label reduced by $r-1$; the other $s-1$ "large" sacks have their labels increased by $2$. And, of course, larger sacks have larger labels. In particular, the product of (old) size-$k-1$ sacks' labels has changed by $\left(\frac{l+1}{l}\right)^r$ where $l$ is the label that used to be on those sacks, and the only label-decrease is by a factor of $\frac{l'-r+1}{l'}$ where $l'$ is the label that used to be on sacks of size $k$. Well, in fact we know that $l'=l+r$. So the overall change in label-product is $\left(\frac{l+1}l\right)^r\frac{l+1}{l+r}$ times the changes arising from sacks that don't end up having size $k-1$, and those latter are always increases. Writing $h:=1/l$, that fraction equals $\frac{(1+h)^{r+1}}{1+rh}$. This is $1$ when $h=0$ and its derivative w.r.t. $h$ turns out to be $\frac{(1+h)^r(1+r^2h)}{(1+rh)^2}$ which is positive. So the fraction's value is $\geq1$ for any $h>0$, and in particular is $\geq1$ when $h=1/l$, and therefore our change doesn't decrease the product of the labels. And now we are done, as before.

Therefore

@hexomino's solution for products is optimal across the whole space of possible sack-sizes.

$\endgroup$
  • $\begingroup$ Oops, I just accidentally saved something I was in the middle of which may therefore not make any sense. Anyway, I think I can simplify the sum-of-labels case as well as handling the product-of-labels case. $\endgroup$ – Gareth McCaughan May 7 at 14:41
  • $\begingroup$ Nice, +1, rewriting the sum of the pairwise products is a really good move here. Btw, the first line has s_k instead of c_k. $\endgroup$ – hexomino May 7 at 14:45
  • $\begingroup$ Ah yes, I changed my mind about what to call the sizes but then didn't follow through. $\endgroup$ – Gareth McCaughan May 7 at 14:46
  • 1
    $\begingroup$ But I'm no longer so confident about streamlining the sum-of-labels case -- I thought it was going to turn out that my transformation never decreases any label, but alas that's not true. $\endgroup$ – Gareth McCaughan May 7 at 14:46
  • $\begingroup$ OK, I think I have the products working as well as the sums. $\endgroup$ – Gareth McCaughan May 7 at 15:13
1
$\begingroup$

I'd like to suggest that for the sum:

You could put 2 coins in one bag, and the other 97 each on their own in 97 bags.
Therefore you write 97 on the sack with 2 coins in. Max sum of 97

For the product,

If you put 76 coins in 38 bags, 2 each.
Then split the other 23 coins singularly into bags (1 each)
you could write 23 on each of the 38 bags
giving 23^38 = 5567468501746130000000000000000000000000000000000000

I could be reading the question completely wrong however :)

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