Church charity lottery

Question

Suppose you've rigged the church charity lottery so that you cannot lose (what a swell guy you are). There are 10 drawings, and you start off with 10 dollars exactly.

At each drawing, you must chose an amount to bet, and that amount gets put into a pool (that money then can no longer be used to wager). You then proceed with the next drawing, and you do this until you have no more money left.

The total amount of money won is the product of the amounts wagered each round played that you won (and since it is rigged, everytime you wager you win).

For example, if I wagered all 10 dollars in the first round, I will have won 1 drawing and earned exactly 10 dollars. If I wager 2 in the first round and 8 in the second, I will have won 16 dollars. Wagers must be in whole dollar amounts. Rounds where nothing is wagered are disregarded entirely, depending on how money is distributed amongst the various rounds.

1. What is the best strategy to adopt to maximize winnings?
2. For $n$ dollars and potentially up to $n$ drawings, what is the generalizable best strategy to maximize winnings?
3. Let $\varphi(n)$ represent the maximum amount possible for start amount $n$ and rounds $n$ while observing the rules above. What is the relationship between $\varphi(n)$ and $n$ (can a conclusion be made about its relationship)?

Answer 1

This is basically a question of partitioning - which partition of $n$ generates the largest product?

Let's establish the rules that our partition should follow:

1) It doesn't make sense to make a partition of 1, that won't increase the product. We'd rather make another partition one larger. Better to have $2,3$ than $2,2,1$.

2) It also doesn't make sense to partition except into prime numbers. Since we're multiplying all the numbers together, then multiplying by a composite number is the same as multiplying by its prime factorization. So if we partitioned $10$ into $6,2,2$ then our winnings would be $6*2*2$, but since multiplying by $6$ is the same as multiplying by $2$ and $3$ (its prime factorization), we can partition into $3,2,2,2,1$ and get the same result. EDIT: The prime factorization won't always sum up to the same number, so we may get additional factors, which will only increase our end product, or leave it the same if the additional factor is just $1$ as above.

3) One additional rule is that one larger prime is not as good as two smaller primes. For example, a factor of $5$ is not as good as factors of $2$ and $3$. Similarly, factors of $7$ are not as good as factors of $3,2,2$. Lastly, a factor of $3$ is better than factors of $2$ and $1$. SO a partition that includes $11$ is beaten by a partition that includes $5,5,1$ instead, which is similarly beaten by a partition that includes $3,2,5,1$ which is beaten by a partition of $3,3,3,2$.

This fact can be "proven" by the simple fact that $2$ is less than half of any number greater than $4$. So if you take $c$ and split it into $2$ and $c-2$, then multiplying by $2$ and $c-2$ will yield a product larger than if you just multiplied by $c$. Repeat this process until your numbers are small enough.

So, given the above rules, I think that the best partition would be to make as many 3's as possible, unless it would leave a partition of 1 left in which case you should fill in the rest with 2's.

This would leave the maximal partition of $10$ to be:

$3,3,2,2$

The maximal partition of $11$ would be:

$3,3,3,2$

The maximal partition of $n$ would therefore be:

$n\mod3 \equiv 0$: $k$ $3$'s, where $k = \frac n3$

$n\mod3\equiv1$: $k$ $3$'s and two $2$'s, where $k = \lfloor {\frac n3}\rfloor -1$

$n\mod3\equiv2$: $k$ $3$'s and one $2$, where $k = \lfloor {\frac n3}\rfloor$

Would love for someone to check my logic.

Answer 2

If you take $k$ ($1 <= k <= 10$) as the number of wagers you want to join, then the optimal amount to bet for each wager is $10 / k$. And your total winnings would then be $(10 / k)^k$. So I calculated this for every $k$ from $1$ to $10$ and got this:

k    10/k   (10/k)^k
---------------------
1    10     10
2    5      25
3    3.33   37.04
4    2.5    39.06
5    2      32
6    1.67   21.43
7    1.43   12.14
8    1.25   5.96
9    1.11   2.58
10   1      1

And it clearly shows you that you should participate in 4 wagers of 2,5 dollars each.

For the extended case of $n$ dollars and up to $n$ drawings, you're looking for a $k$ $(1 <= k <= n)$, where $(n / k)^k$ is maximal. I don't know yet how to find such a $k$ without brute forcing it.

Answer 3

As long as there are enough drawings, the optimal strategy is to bet 3 dollars each time as long as you have more than 4 dollars left. Once you have 4 dollars or less left, you bet the rest.

Any bet of 5 or more won't be optimal, because you could bet 2 of them and then the rest, and get a larger return. A bet of 1 obviously doesn't make sense either.

The strategy is optimal, because if you had spent more than 4 dollars on bets of sizes 2 or 4, the strategy could be improved as follows. Any bet of 4 dollars is split into two of 2 dollars (which doesn't change anything), and then you change three bets of 2 into two bets of 3, which is better because 3*3 > 2*2*2.

If you started with less than 5 dollars, the above strategy will only pay back your initial bets, instead you just don't bet at all and win one dollar, because the product over the empty set is 1.

If there are too few drawings to use the above strategy, you split your bets evenly over the drawings. Round up or down enough times to exactly use up all your money.

Answer 4

Adding to PrisonMonkeys' answer, We need to find the value of k such that the value of (n/k)^k is maximized. on differentiating and solving this, the value of k happens to be n/e , where e is the irrational 2.71828... . That means, we would have the most optimal product when we divide it into n/e parts with each part having the value of e . I think the accepted solution of Duncan makes sense because 3 is the closest integer value to e and 2 is the next closest. So when we are going for integer partitions, make maximum of the partitions equal to the integer nearest to e and the rest to the next nearest.

This is just my thought, not a rigorous proof as such. Feel free to comment and improve/ add more rigour to the answer. Lastly, I am new here, so sorry about the formatting.

Answer 5

I would like to combine answers of Duncan and PrisonMonkeys (my credits to them) and add some prove (not 100% strict, but it let to feel what is happening in this puzzle).

To formulate problem on mathematical language we need to find $k<=N$ nonnegative integer numbers: $n_1,n_2,..n_k$, such that sum $S = n_1+n_2+..+n_k = N$ and product $P = n_1 \cdot n_2 \cdot .. \cdot n_k$ is maximal.

1. Let's first allow $n_i$ to be not integer.

   1. If $k$ is fixed we need to find conditional extremum. I use Lagrange function, that would be: $L = n_1 \cdot n_2 \cdot .. \cdot n_k + \lambda(n_1+n_2+..+n_k - N)$
      $\partial L/\partial n_i = P / n_i + \lambda$, for any $i = 1, .., k$ therefore $n_1 = n_2 = .. = n_k = P/\lambda$,
      $n_i = N/k$ for any $i = 1, .., k$,
      $P = (N/k)^k$

   2. Let's suppose $k$ is not integer too. Then maximum is achieved when
      $dP/dk = 0$ or
      $P(ln(N) - ln(k) - 1) = 0$, or
      $k = N/e$ therefore
      $n_i = e$.

2. When we go from real $n_i = e \approx 2.7$ to integer we can suppose that the closest possible integer number must be chosen. This is reasonable assumption, since function $P(k)=(N/k)^k$ has monotonic increase before $k<e$ and monotonic decrease with $k>e$.
   The closest numbers to $2.7$ are $2$ on the left and $3$ on the right, one can compare them directly and find out that $3$ is optimal.
   Since not all $N$ are dividable by $3$ we may need to use 2, which is also close to $2.7$, but not more that two $2$'s will be needed.

Summarising:

If $N \bmod 3 = 0$ : we wager all $3$'s.

If $N\bmod3 = 1$ : we wager two $2$'s and rest are $3$'s.

If $N\bmod3 =2$ : we wager one $2$'s and rest are $3$'s.

When $N = 10 = 9+1$, we can win $2\cdot 2\cdot 3\cdot 3=36$.

Answer 6

This question has been answered fairly. However, I want to point out that an algorithmic way of answering it, could be used. Indeed, Let $\xi(n, m)$ be the maximum amount obtained using exactly $n$ dollars and $m$ bets. It is clear that:

\begin{align*} \xi\left(n, m\right) = \begin{cases}0 & \text{if $n< m$}\\ n &\text{if $m=1$}\\ \max\limits_{s\in\{1,\ldots,n\}} \left(s\times\xi\left(n-s,m-1\right)\right)& \text{otherwise}\end{cases} \end{align*}

Finally $\varphi(n) = \max\limits_{k\in\{1,\ldots,n\}} \xi(n, k)$. We can compute $\xi$ using dynamic programming and compute $\varphi(n)$ after that.