wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> challange puzzle
        
(Message started by: RajivG on Oct 12^th, 2011, 3:55am)

Title: challange puzzle
Post by RajivG on Oct 12^th, 2011, 3:55am

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????

Title: Re: challange puzzle
Post by towr on Oct 12^th, 2011, 9:47am

[hide]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) = 2^w
F(0,l) = 1
we can calculate F(w,l) recursively (using a table or memoization)[/hide]

There might be a way to simplify it to a closed form, which would be nice.

Title: Re: challange puzzle
Post by Hippo on Oct 21^st, 2011, 12:07am

Nice natural solution. I do thing this is not hard.
May be if one would be asked to make a close form.

[hide]
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.
[/hide]

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