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

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

clipka <ano### [at] anonymousorg> 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

clipka <ano### [at] anonymousorg> 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

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

Kevin Wampler <wam### [at] uwashingtonedu> 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

Warp wrote:
> Kevin Wampler <wam### [at] uwashingtonedu> 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

Warp <war### [at] tagpovrayorg> 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

triple_r wrote:
> 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.

My guess would be that the solution isn't closed form but can be solved 
for in time which is logarithmic (or some other o(n) function) in n. 
Looks fun though (and tricky)!

Post a reply to this message

Kevin Wampler <wam### [at] uwashingtonedu> wrote:
> triple_r wrote:
> > 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.
>
> My guess would be that the solution isn't closed form but can be solved
> for in time which is logarithmic (or some other o(n) function) in n.
> Looks fun though (and tricky)!

Yes, I think you're right.  I should be more careful with what I mean by 'closed
form.'  I did feel better when I cheated and looked at the answer though. (#160)

http://www.haskell.org/haskellwiki/Euler_problems/151_to_160

I guess I just neglected to remember that the group of invertible elements of
the ring of integers modulo 10^d is isomorphic to the product of a cyclic group
of order 2 and another cyclic group.

It was so obvious!

 - Ricky

Post a reply to this message