Re: Real tough problem.....pls try...

"Risto Lankinen" <rlankine@xxxxxxxxxxx> writes:

<arun.madras@xxxxxxxxx> wrote in message
news:1152107624.371637.177670@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Come up with the strategy
which ensures you the largest possible amount (that is, the strategy
which whose worst-case scenario is as good as possible).

Maximizing _worst-case_ return is not tough at all...

The worst case-scenario is that you lose all bets (no matter whether
by random, or by a lie from the Oracle). To minimize this loss, you
should bet 0 dollars at each round. This strategy will guarantee the
worst case return of exactly 100 dollars.

All other strategies (i.e. at least one non-zero bet) have a worst-case
return less than 100 dollars.

- Risto -

It seems you didn't read the problem carefully. The oracle can lie
at most once, so if you bet the way it says you can lose only once.
The problem is that you don't know when it's going to lie.

David

.

Relevant Pages

  • Re: Real tough problem.....pls try...
    ... initial amount eventually leaving u 2^N-2 times the initial amount. ... The oracle will tell you which way the coin will ... What is the significance of the fact that the Oracle may lie after ... a lie one is left with fraction X of one's bank, ...
    (comp.theory)
  • Re: Real tough problem.....pls try...
    ... result of a coin flip. ... The oracle will tell you which way the coin will ... What is the significance of the fact that the Oracle may lie after ... a lie one is left with fraction X of one's bank, ...
    (comp.theory)
  • Re: Real tough problem.....pls try...
    ... result of a coin flip. ... The oracle will tell you which way the coin will ... but may lie on just one occasion and may do so after seeing your ... What is the significance of the fact that the Oracle may lie after seeing your bet? ...
    (comp.theory)
  • Re: Tech building
    ... There are whole domains of problems which lie ... outside what is calculable by a Turing Machine. ... The mechanisms are ... My backbrain says a QM is equivalent to a TM plus an oracle, ...
    (rec.arts.sf.composition)
  • Re: Real tough problem.....pls try...
    ... result of a coin flip. ... The oracle will tell you which way the coin will ... but may lie on just one occasion and may do so after seeing your ...
    (comp.theory)