![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp <war### [at] tag povray org> wrote:
> 3) Assume two people, person A and person B, who want to decide who gets
> a price by tossing a coin.
> Person A is a bad loser and a bully, so if he loses he says "I said it's
> two out of three". So they play it like that. If A loses again, he says
> "I said it's three out of five", and so on, until he wins.
> How many tosses is this game expected to last, in average?
Actually this problem isn't so "relatively easy" is it first seemed.
It's actually quite complicated.
AFAIK the answer lies on whether the sum of probabilities for a game
lasting a certain number of rounds forms a convergent or a divergent series.
If it forms a divergent series, then the average is infinite. However,
proving that the series is divergent is, AFAIK, not trivial at all.
Anyways, maybe you could want to consider two variants with finite
solutions:
3a) Like above, but after n losses the bully gets tired and declares himself
a winner anyways. In other words, rather than saying "I said it's <n+1> out
of <(n+1)*2-1>" he just ends the game.
Question: How many coin tosses does a game have in average, with an upper
limit of n round losses for the bully?
3b) Like 3a, but instead of tossing a coin, they play rock-paper-scissors.
How many hand throws in average does a game last with an upper limit of n
round losses for the bully?
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp schrieb:
> The game starts with "1 out of 2" (regular coin toss).
Isn't that "1 out of 1"?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp schrieb:
>
>> I think that very much depends on whether the sequence is
>
>> 1 - 3 - 5 - 7 - 9 - ...
>
>> or
>
>> 1 - 3 - 5 - 9 - 17 - ...
>
> How would "four out of nine" work? If there are nine tosses, four wins
> wouldn't yet be decisive.
>
> Of course it's "4 out of 7", "5 out of 9", "6 out of 11" and so on.
Who says that the bloke will demand 4 out of anything, and not just skip
on to 5 out of 9 ?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Some relatively easy math problems for your consideration and enjoyment:
>
>
> 1)
Key phrase: "not divisible by any *of the* primes"
> 2)
Some of the permutations will be repeat the same sequence.
> 3)
This value is bounded below by:
(1/4) * sum_{i=1:inf} 1/sqrt(i)
Which diverges, so the expected length of the game is infinite.
> 4)
I don't see how this is possible to give in closed form unless you allow
the ability to sum the digits in the base-5 representation of a number
(which you'd need a recursion or summation to do). If you actually know
a closed form that doesn't use a cheat like this I'd be curious to hear it.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> Warp schrieb:
> > The game starts with "1 out of 2" (regular coin toss).
> Isn't that "1 out of 1"?
Yes. I got confused.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> Warp schrieb:
> >
> >> I think that very much depends on whether the sequence is
> >
> >> 1 - 3 - 5 - 7 - 9 - ...
> >
> >> or
> >
> >> 1 - 3 - 5 - 9 - 17 - ...
> >
> > How would "four out of nine" work? If there are nine tosses, four wins
> > wouldn't yet be decisive.
> >
> > Of course it's "4 out of 7", "5 out of 9", "6 out of 11" and so on.
> Who says that the bloke will demand 4 out of anything, and not just skip
> on to 5 out of 9 ?
While he is at it, while not skip directly to 1000 out of 1999?
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Anyways, maybe you could want to consider two variants with finite
> solutions:
>
> 3a) Like above, but after n losses the bully gets tired and declares himself
> a winner anyways. In other words, rather than saying "I said it's <n+1> out
> of <(n+1)*2-1>" he just ends the game.
>
> Question: How many coin tosses does a game have in average, with an upper
> limit of n round losses for the bully?
I won't spoil it since I found this to be a very fun little problem, but
once you get the answer in the right form it's not too bad to show that
the series diverges. In fact, I derived my previous answer by noting
that (unless I made algebra errors) for epsilon > 0 the value:
1/2 + 1/(2*sqrt(pi)+epsilon) * sum_{i=1:n} (2*i+1) / i**(3/2)
lower bounds the answer to 3a for sufficiently large values of n (I
don't think this is too much of a hint).
The main problem is that it requires either significant derivation or
some background knowledge to approximate the sum in that form. Of
course you can still compute the answers efficiently for any given n
without this, and I found deriving even this part of the answer pretty
satisfying.
Basically: fun problem! (although I agree that it wasn't "relatively
easy", nor is #4, as I don't think it's possible).
> 3b) Like 3a, but instead of tossing a coin, they play rock-paper-scissors.
> How many hand throws in average does a game last with an upper limit of n
> round losses for the bully?
It should be 1.5 times as many rounds as the answer to part 3a I would
think.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler <wam### [at] u washington edu> wrote:
> nor is #4, as I don't think it's possible).
AFAIK the simplest recursive solution to the problem is (as I mentioned in
another post) this:
f(0) = 0
f(n) = floor(n/5) + f(floor(n/5))
One could try to prove that the above cannot be expressed in closed form.
But AFAIK that wouldn't be a proof that there is no closed form solution at
all, just that the above method cannot be expressed in that form.
Of course for a simpler version of the problem one could remove the
limitation that the solution must not be recursive. It's, in fact, not
completely trivial to come up with the simplest possible solution, as above.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Kevin Wampler <wam### [at] u washington edu> wrote:
>> nor is #4, as I don't think it's possible).
>
> AFAIK the simplest recursive solution to the problem is (as I mentioned in
> another post) this:
>
> f(0) = 0
> f(n) = floor(n/5) + f(floor(n/5))
>
> One could try to prove that the above cannot be expressed in closed form.
> But AFAIK that wouldn't be a proof that there is no closed form solution at
> all, just that the above method cannot be expressed in that form.
I'm not sure quite what you mean here, wouldn't any closed form solution
to the original problem also by definition be a closed form solution to
the above recursion?
In any case, I'm relatively confident that the answer can't be
represented in closed form under the standard definition of closed form
since the sequence has a sort of fractal structure to it.
I do agree that it's a neat problem if you remove the closed form
restriction, and seems about the right difficulty to fit with the others.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp <war### [at] tag povray org> wrote:
> 4) By their nature, factorials tend to accumulate trailing zeroes. For
> example, 5! (120) has one trailing zero, 10! (3628800) has two trailing
> zeroes, 25! (15511210043330985984000000) has six trailing zeroes, etc.
>
> Give a (non-recursive) mathematical function which, for an integer n,
> gives the number of trailing zeroes in n!.
That's closely related to this exceedingly difficult problem, at least for those
of us not familiar with number theory.
http://projecteuler.net/index.php?section=problems&id=160
I spent a lot of time on this, but was never able to get the right answer. You
basically need a closed-form solution since you can't even iterate a simple
model that far in a reasonable amount of time.
- Ricky
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |