Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

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)?
share|improve this question
    
So you need to find 10 nonnegative integer numbers: n1,n2,..n10, such that n1+n2+..+n10 = 10 and n1*n2*..*n10 is maximal? –  klm123 Jun 30 at 16:58
    
@klm123 Yes, precisely. I thought I'd indulge in a little storytelling. My apologies to the more concise of us. :) –  Neil Jul 1 at 7:35
    
I plugged this into Wolfram Alpha, and it seems betting e (2.72) dollars each time is optimal. The closest number that divides evenly into $10 is $2.50. –  Brilliand Jul 1 at 19:37
1  
You should perhaps explicitly state that there is no obligation to participate in any drawing. Otherwise any partition other than (1,1,1,1,1,1,1,1,1,1) would imply that the player wagered \$0 in some drawing, and multiplying that zero-dollar wager by any other winnings would nullify them. Alternatively, one could start with more than \$10 but be required to wager at least something on every drawing. –  supercat Jul 1 at 21:34
    
@supercat I thought that point was clear as indicated by "The total amount of money won is the product of the amounts wagered each round played", though maybe it is ambiguous the fact that a round could be played without wagering anything. Corrected in question to be clearer. –  Neil Jul 2 at 8:44
show 1 more comment

5 Answers 5

up vote 12 down vote accepted

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.

share|improve this answer
    
Could you prove your logic? (statements 2 and 3) –  klm123 Jun 30 at 17:11
1  
substitute 3) for "you dont want any number bigger that 4 in a partition". To prove that, say your partition has a 5. Then you can subtract a 2, and have 3.2 Say it has a n, n>=4 then you can have (n-2)*2=2*n-4 = n + (n-4) (which is nice, since n is >= 4) –  josinalvo Jun 30 at 19:14
2  
actually, this replaces 2) as well =P now you have "no 1" and "no 4, no n>4". That is, only 2s and 3s –  josinalvo Jun 30 at 19:20
3  
Curiously, if betting fractional dollars were allowed, the optimal bet would be $e \approx 2.718281828$ dollars per round. The number 3 appears to simply be the best integer approximation to $e$. (Also, it's easy to see that betting \$2 on more than two rounds can never be optimal, since $2^3 = 8 < 3^2 = 9$.) –  Ilmari Karonen Jun 30 at 21:35
1  
An interesting question. Our ability to break a larger number down into a smaller one does not reverse as the sum would then be violated (for example, instead of doing a bet of $9$ we can do $3$ bets of $3$, which gets a multiplier of $27$ instead of just $9$, but we can't replace two bets of $3$ with a bet of $9$. $3+3 = 6$, so a $9$ would violate our sum rule. My instinct says you should increase as many of the $3$'s to $4$'s as possible, then to $5$'s if necessary, etc, but I'd have to do some more work to check. If this is true, you'd end up with something like: $4,4,4,3,3,3$. –  Duncan Jun 30 at 23:42
show 5 more comments

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.

share|improve this answer
1  
A good answer, but the problem states "Wagers must be in whole dollar amounts.". I suspect, however, that any actual solution will be an integer approximation of this formula, so +1 anyway. –  Bobson Jun 30 at 19:34
    
@Bobson Oh, I completely missed that, I even wondered why Duncan's answer only calculated with integer values... Silly me. –  PrisonMonkeys Jun 30 at 19:40
    
Following up on that, I've demonstrated (via spreadsheet) that your answer will be equivalent to his for $k \mod 3 = 0$, which confirms my impression that his is just a good way to approximate this. –  Bobson Jun 30 at 19:44
add comment

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.

share|improve this answer
    
@klm123 has added an answer, that is exactly what I wanted to say. He expressed more rigorously –  Harsha Vardhan Kode Jul 1 at 10:46
    
Random fact: That approach is actually quite similar to how one would find integer solutions to x^y = y^x with x > y. –  kasperd Jul 1 at 12:22
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.