Author |
Topic: challange puzzle (Read 1932 times) |
|
RajivG
Junior Member
Gender: 
Posts: 72
|
 |
challange puzzle
« on: Oct 12th, 2011, 3:55am » |
 Quote  Modify
|
two players (you and other)
* you hold money (lets say 'X' amount)
* other holds cards (win cards and loose cards)
* you put some money and other will give you either 'W' card or 'L' card
* if 'W' card then your bet amount will be doubled
* if 'L' card then your bet amount is zeroed
* you can put zero amount
* you know how much 'W' and 'L' card other is holding
* other knows how much total amount you have
<b>now we need to maximize you's amount</b>
partial solution or hint : if other has only two cards (one 'W' and one 'L') then putting 33% of X is the answer because it gives the maximum gain
--------------------------
ex: X=$10
W=1
L=1
you puts $3.33 on bet
if others gives 'L' card then you know other is left with only 'W' card so you put entire amount on 2nd bet
if others gives 'W' card then you know other is left with only 'L' card so you put zero amount in next bet
----------------------
now the real trouble
we need to have solution which maximize yous X amount on random combination of cards
any help ?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: challange puzzle
« Reply #1 on: Oct 12th, 2011, 9:47am » |
Quote Modify
|
The amount of money you start with doesn't really matter, if you have twice as much money you'll make bets twice as large. So the only thing that's really interesting is what percentage of your money to bet, and what percentage you'll gain.
When you make a bet, it shouldn't matter whether you win or loose to the end-result. So say that F(w, l) is the gain-factor when there are w win-cards and l lose-cards (i.e. if you start with X, at the end of the game you'll have F(w, l)*X). Then we want a bet b such that F(w-1, l)(1+b) = F(w, l-1)(1-b). Which means that b = [F(w, l-1) - F(w-1, l)] / [F(w-1, l) + F(w, l-1)]
So starting with
F(w,0) = 2w
F(0,l) = 1
we can calculate F(w,l) recursively (using a table or memoization)
There might be a way to simplify it to a closed form, which would be nice.
|
| « Last Edit: Oct 12th, 2011, 9:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: challange puzzle
« Reply #2 on: Oct 21st, 2011, 12:07am » |
Quote Modify
|
Nice natural solution. I do thing this is not hard.
May be if one would be asked to make a close form.
As F(w,l)=1+b(w,l) ...
F(w,l)=2F(w,l-1)/(F(w,l-1)+F(w-1,l))
Interesting that F(w,1) goes to F(1)=2 for w going to infty,
F(w,l) goes to F(l) ... F(l)=2F(l-1)/(F(l-1)+F(l)).
F(l)(F(l-1)+F(l))=2F(l-1)
(F(l)+F(l-1)/2)^2=2F(l-1)+F(l-1)^2/4
so
F(l)=sqrt(2F(l-1)+F(l-1)^2/4)-F(l-1)/2.
Oops. F(w,l)=1+b(w,l) is wrong F(w,l)=F(w-1,l)+b(w,l) is correct.
So F(w,l)=F(w-1,l)(1+b(w,l))=2F(w-1,l)F(w,l-1)/(F(w-1,l)+F(w,l-1)) is definitely correct  .
Better description is F(w,l)=2^{w+l}/k(w,l), where k(0,l)=2^l and k(w,0)=1.
With little effort we would find k(w,l)=k(w-1,l)+k(w,l-1) so this is Pascal recurence triangle.
The 2^l initialisation on one coordinate could be changed to initialisation by diagonal halfline of 1's.
Therefore k(w,l)=\sum_i=0^w (w+l \choose i).
So resulting "close form" is ratio of number of all w+l bit numbers to w+l bit numbers with at most w bit's set. I am not sure I could formulate better expression for the k(w,l).
|
| « Last Edit: Oct 21st, 2011, 10:30am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print