 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Some relatively easy math problems for your consideration and enjoyment:
1) The classical proof that there are infinitely many primes is a proof by
contradiction: Let's assume that there's a largest prime. If we multiply
all the primes up to that largest prime and add 1, we get a number which
is not divisible by any of the primes, and thus the assumption we made is
false: There was a prime which is larger than the one we assumed was the
largest.
However, consider this: 2*3*5*7*11*13 + 1 = 30031, which is a composite
number.
Isn't this a contradiction to the proof? It clearly doesn't hold that the
product of the first n primes plus 1 is a prime.
How to explain this apparent contradiction?
2) Assume you have an array of 24 integers. Each element of that array
can get a value between 0 and 7. Thus the total amount of different contents
for such as an array is 8^24, which is approximately 4*10^21.
Now assume that you fill the array with some values and then calculate
all the possible permutations of that array. The amount of permutations
for 24 elements is 24!, which is approximately 6*10^23.
Now here's the apparent paradox: The total amount of different contents is
about 4*10^21, and naturally all those permutations should be among them as
well. How come the total amount of permutations, 6*10^23, is way larger
than the total amount of possible different array contents?
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?
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!.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> 1) The classical proof that there are infinitely many primes is a proof by
> How to explain this apparent contradiction?
Oh, I like that. That took a while to figure out.
> 2) Assume you have an array of 24 integers. Each element of that array
That one's easy. :-)
> How many tosses is this game expected to last, in average?
Boring. :-)
> Give a (non-recursive) mathematical function which, for an integer n,
> gives the number of trailing zeroes in n!.
Cute, and not too difficult, I'm thinking.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> 1) The classical proof that there are infinitely many primes is a proof by
> contradiction: Let's assume that there's a largest prime. If we multiply
> all the primes up to that largest prime and add 1, we get a number which
> is not divisible by any of the primes, and thus the assumption we made is
> false: There was a prime which is larger than the one we assumed was the
> largest.
>
> However, consider this: 2*3*5*7*11*13 + 1 = 30031, which is a composite
> number.
>
> Isn't this a contradiction to the proof? It clearly doesn't hold that the
> product of the first n primes plus 1 is a prime.
>
> How to explain this apparent contradiction?
The answer lies (as I look at that bit of the wikipedia article on
primes) in that there exists a prime smaller than 30031 by which it's
divisible that's also larger than 13, so 13 isn't the largest prime.
> 2) Assume you have an array of 24 integers. Each element of that array
> can get a value between 0 and 7. Thus the total amount of different contents
> for such as an array is 8^24, which is approximately 4*10^21.
>
> Now assume that you fill the array with some values and then calculate
> all the possible permutations of that array. The amount of permutations
> for 24 elements is 24!, which is approximately 6*10^23.
>
> Now here's the apparent paradox: The total amount of different contents is
> about 4*10^21, and naturally all those permutations should be among them as
> well. How come the total amount of permutations, 6*10^23, is way larger
> than the total amount of possible different array contents?
The total amount of permutations doesn't consider duplicate cell values.
It treats 77 and 77 (with the 7s being swapped) as two different numbers.
--
Tim Cook
http://empyrean.freesitespace.net
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I got 1, but I had to factor 30,031 before I got it.
Permutations and combinations make my eyes go wonky, so I have pass on 2.
I quite know what's meant in 3 by an "average", unless it's the convergence
of a series; not sure if I have that one or not.
As for 4, I'm stumped. :)
Thanks for the fun though... must get back to work now.
"Warp" <war### [at] tag povrayorg> wrote in message
news:4ab90520@news.povray.org...
> Some relatively easy math problems for your consideration and enjoyment:
>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 22-9-2009 19:10, Warp wrote:
> Some relatively easy math problems for your consideration and enjoyment:
>
>
> 1) The classical proof that there are infinitely many primes is a proof by
> contradiction: Let's assume that there's a largest prime. If we multiply
> all the primes up to that largest prime and add 1, we get a number which
> is not divisible by any of the primes, and thus the assumption we made is
> false: There was a prime which is larger than the one we assumed was the
> largest.
>
> However, consider this: 2*3*5*7*11*13 + 1 = 30031, which is a composite
> number.
>
> Isn't this a contradiction to the proof? It clearly doesn't hold that the
> product of the first n primes plus 1 is a prime.
>
> How to explain this apparent contradiction?
The claim is not that the products of primes plus one is a prime, just
that it has a prime divisor that is not one in the product.
> 2) Assume you have an array of 24 integers. Each element of that array
> can get a value between 0 and 7. Thus the total amount of different contents
> for such as an array is 8^24, which is approximately 4*10^21.
>
> Now assume that you fill the array with some values and then calculate
> all the possible permutations of that array. The amount of permutations
> for 24 elements is 24!, which is approximately 6*10^23.
>
> Now here's the apparent paradox: The total amount of different contents is
> about 4*10^21, and naturally all those permutations should be among them as
> well. How come the total amount of permutations, 6*10^23, is way larger
> than the total amount of possible different array contents?
8 is less than 24
> 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?
same answer as: what will the average number if boys be if every pair of
parents continues getting children untill they get a boy. (assuming 50%
chance of a boy, which is not exactly correct, and that every pair that
gets one child can in principle get an infinite number)
> 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!.
just count the number of 5s, 25s, 125s etc
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 22-9-2009 21:20, andrel 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!.
>
> just count the number of 5s, 25s, 125s etc
BTW I did write a quick and dirty arbitrary precision integer thing to
compute some factorials. I saw the answer before actually having to use
it, but here is 100!:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
in case you wanted to know.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel <a_l### [at] hotmailcom> wrote:
> > 2) Assume you have an array of 24 integers. Each element of that array
> > can get a value between 0 and 7. Thus the total amount of different contents
> > for such as an array is 8^24, which is approximately 4*10^21.
> >
> > Now assume that you fill the array with some values and then calculate
> > all the possible permutations of that array. The amount of permutations
> > for 24 elements is 24!, which is approximately 6*10^23.
> >
> > Now here's the apparent paradox: The total amount of different contents is
> > about 4*10^21, and naturally all those permutations should be among them as
> > well. How come the total amount of permutations, 6*10^23, is way larger
> > than the total amount of possible different array contents?
> 8 is less than 24
So? How does that answer the question?
> > 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?
> same answer as: what will the average number if boys be if every pair of
> parents continues getting children untill they get a boy.
It isn't. It would be if the game would have been "we throw the coin
until it gives heads". However, that's not how the game goes.
> > 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!.
> just count the number of 5s, 25s, 125s etc
Firstly, the question didn't ask for an algorithm to calculate the number
of zeros (which is what the "non-recursive" part more or less rules out).
It asked for a closed-form function which tells the number of zeros.
Secondly, your algorithm is flawed. 10! has two zeros and only one 5 as
a factor.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/22/09 12:10, Warp 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!.
For a tougher problem, estimate the number of digits in n!
(Well, easy if you know one certain piece of information...).
--
I think animal testing is a terrible idea. They get all nervous and give
the wrong answers.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 22-9-2009 21:58, Warp wrote:
> andrel <a_l### [at] hotmailcom> wrote:
>>> 2) Assume you have an array of 24 integers. Each element of that array
>>> can get a value between 0 and 7. Thus the total amount of different contents
>>> for such as an array is 8^24, which is approximately 4*10^21.
>>>
>>> Now assume that you fill the array with some values and then calculate
>>> all the possible permutations of that array. The amount of permutations
>>> for 24 elements is 24!, which is approximately 6*10^23.
>>>
>>> Now here's the apparent paradox: The total amount of different contents is
>>> about 4*10^21, and naturally all those permutations should be among them as
>>> well. How come the total amount of permutations, 6*10^23, is way larger
>>> than the total amount of possible different array contents?
>
>> 8 is less than 24
>
> So? How does that answer the question?
that is obvious, I would think.
>>> 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?
>
>> same answer as: what will the average number if boys be if every pair of
>> parents continues getting children until they get a boy.
>
> It isn't. It would be if the game would have been "we throw the coin
> until it gives heads". However, that's not how the game goes.
Ok I read that wrong. Can you give an algorithm for 'and so on'?
1 2 3 4 5..
- - - - -
2 3 5 8 13...
or
1 2 3 4 5 ..
- - - - -
2 3 5 7 11...
or
?
>>> 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!.
>
>> just count the number of 5s, 25s, 125s etc
>
> Firstly, the question didn't ask for an algorithm to calculate the number
> of zeros (which is what the "non-recursive" part more or less rules out).
> It asked for a closed-form function which tells the number of zeros.
>
> Secondly, your algorithm is flawed. 10! has two zeros and only one 5 as
> a factor.
No it has 2 both 10 and 5 have a factor of 5. So if you want your
algorithm:
sum_k floor(x/(5^k)) over all k from 1 till 5^k<=x
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp schrieb:
> 1) The classical proof that there are infinitely many primes is a proof by
> contradiction: Let's assume that there's a largest prime. If we multiply
> all the primes up to that largest prime and add 1, we get a number which
> is not divisible by any of the primes, and thus the assumption we made is
> false: There was a prime which is larger than the one we assumed was the
> largest.
>
> However, consider this: 2*3*5*7*11*13 + 1 = 30031, which is a composite
> number.
>
> Isn't this a contradiction to the proof? It clearly doesn't hold that the
> product of the first n primes plus 1 is a prime.
>
> How to explain this apparent contradiction?
I didn't verify whether 30031 is indeed composite - but one thing's for
sure: It is not a multiple of 2, 3, 5, 7, 11 or 13 (I checked :-)). So
whatever the smallest factor, that's (a) a prime by definition
(otherwise there would obviously be a smaller factor) and (b) it's
larger than 13, our "current largest prime". Q.e.d.
> 2) Assume you have an array of 24 integers. Each element of that array
> can get a value between 0 and 7. Thus the total amount of different contents
> for such as an array is 8^24, which is approximately 4*10^21.
>
> Now assume that you fill the array with some values and then calculate
> all the possible permutations of that array. The amount of permutations
> for 24 elements is 24!, which is approximately 6*10^23.
>
> Now here's the apparent paradox: The total amount of different contents is
> about 4*10^21, and naturally all those permutations should be among them as
> well. How come the total amount of permutations, 6*10^23, is way larger
> than the total amount of possible different array contents?
You used the wrong formula for your permutations, as the one you used
presumes that all elements are unique.
> 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?
I think that very much depends on whether the sequence is
1 - 3 - 5 - 7 - 9 - ...
or
1 - 3 - 5 - 9 - 17 - ...
> 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!.
Obviously, trailing zeros are due to the presence of prime factors 2 and
5 in the factorial term. As that term is defined recursively as n! =
(n-1)!*n, n! "inherits" all the prime factors from (n-1)!, additionally
"injecting" its own prime factors.
We can ignore the factor 2 here, as the prime factor 2 is much more
frequent than the factor 5, so for every factor of 5 we have ample
factors of 2 to complement for a factor of 10, and thus a digit.
Any multiple of 5 will therefore "inject" at least one trailing zero.
Any multiple of 5^2 will "inject" an additional trailing zero.
Any multiple of 5^3 will "inject" an additional third trailing zeros.
And so forth.
Thus, the number of trailing zeros can be expressed as:
floor(n/5) + floor (n/(5^2)) + floor(n/(5^3)) + ...
which is a perfectly valid, non-recursive (albeit infinite) mathematical
formula for the desired thing. (Unfortunately the floor() function
complicates matters, otherwise this would be a nice straightforward
geometric series, and we'd end up with the number of trailing zeros
being equal to n/4, which is apparently not /quite/ right :-P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Warp schrieb:
>> 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?
>
> I think that very much depends on whether the sequence is
>
> 1 - 3 - 5 - 7 - 9 - ...
>
> or
>
> 1 - 3 - 5 - 9 - 17 - ...
>
>
I didn't look at the other puzzles, but this one sounds easy enough to
work with before sleep.
First round, A claims 'heads I win' so could win 50% of the time.
Each time B gets a tail flip, A increments how many are needed to win.
Best N out of 2N-1.
Okay, A stands to win first round 50% of the time.
Second round, A can not win because he obviously lost first round.
Third round, A has a remaining 50% chance to win if he won either
previous, a 0 if not.
Just going on brain alone, and barely any of that since it is late here.
But it seems that if the game progresses past the first round, it has a
high chance of going on forever. Same for any of the loss points after
that. Average of 1 + infinity is somewhat closer to infinity than to
one. I would say the game in unwinnable.
The other option is that Player B just needs to punch A, take the coin
and walk away. At least he wins a coin, this way.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp 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!.
>
I think I have a numerical solution, but I do not have the formulas to
write the equation. Yet. . .
What you are interested in is the number of numbers, less than n, that
end in 5, or 0. Five times any even number will result in a multiple of
10 and have add zero at the end. All factorials after 2! are even, given
that 2 is even and they are all multiplied by 2 by recursion.
So, to solve for the number of integers that are multiples of 10, X =
floor(N/10), but save the remainder of N/10 as R. Y, the number of
integers <N ending in 5s, can be gotten via R. Y = floor(R/5)+X. Number
of zeros would be X + Y.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/22/09 15:44, clipka wrote:
> Thus, the number of trailing zeros can be expressed as:
>
> floor(n/5) + floor (n/(5^2)) + floor(n/(5^3)) + ...
>
> which is a perfectly valid, non-recursive (albeit infinite) mathematical
> formula for the desired thing. (Unfortunately the floor() function
While he didn't state it in his original phrasing, he meant closed form.
--
I think animal testing is a terrible idea. They get all nervous and give
the wrong answers.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Neeum Zawan schrieb:
> On 09/22/09 15:44, clipka wrote:
>> Thus, the number of trailing zeros can be expressed as:
>>
>> floor(n/5) + floor (n/(5^2)) + floor(n/(5^3)) + ...
>>
>> which is a perfectly valid, non-recursive (albeit infinite) mathematical
>> formula for the desired thing. (Unfortunately the floor() function
>
> While he didn't state it in his original phrasing, he meant closed
> form.
This being a mathematical puzzle, I'm adhering to the /definition/, not
the /intention/ :-P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel <a_l### [at] hotmailcom> wrote:
> >> 8 is less than 24
> >
> > So? How does that answer the question?
> that is obvious, I would think.
Care to explain? It's not obvious to me.
> Ok I read that wrong. Can you give an algorithm for 'and so on'?
"I said it's <n> of <n*2-1>" with consecutive values of n.
> No it has 2 both 10 and 5 have a factor of 5. So if you want your
> algorithm:
> sum_k floor(x/(5^k)) over all k from 1 till 5^k<=x
But I want a closed-form function, not a recursive function or summation.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Neeum Zawan <m.n### [at] ieeeorg> wrote:
> On 09/22/09 15:44, clipka wrote:
> > Thus, the number of trailing zeros can be expressed as:
> >
> > floor(n/5) + floor (n/(5^2)) + floor(n/(5^3)) + ...
> >
> > which is a perfectly valid, non-recursive (albeit infinite) mathematical
> > formula for the desired thing. (Unfortunately the floor() function
> While he didn't state it in his original phrasing, he meant closed form.
If we allow recursive functions, then the simplest answer would be:
f(0) = 0
f(n) = floor(n/5) + f(floor(n/5))
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka <ano### [at] anonymousorg> 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?
> 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.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 23-9-2009 21:02, Warp wrote:
> andrel <a_l### [at] hotmailcom> wrote:
>>>> 8 is less than 24
>>> So? How does that answer the question?
>
>> that is obvious, I would think.
>
> Care to explain? It's not obvious to me.
See Tim Cook.
>> Ok I read that wrong. Can you give an algorithm for 'and so on'?
>
> "I said it's <n> of <n*2-1>" with consecutive values of n.
where? This formula does not match your problem for n=1.
Strange bully to incrementally decrease his changes.
Or am I still not getting it?
>> No it has 2 both 10 and 5 have a factor of 5. So if you want your
>> algorithm:
>> sum_k floor(x/(5^k)) over all k from 1 till 5^k<=x
>
> But I want a closed-form function, not a recursive function or summation.
>
you said you didn't want a recursive function. You never said anything
about summations.
I am afraid we enter into a semantic discussion here, where I might take
another POV than you about what is a closed-form. I'll for the moment
assume that you had stated it as you have now modified it and think again.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 23-9-2009 22:22, andrel wrote:
> On 23-9-2009 21:02, Warp wrote:
>> andrel <a_l### [at] hotmailcom> wrote:
>
>>> Ok I read that wrong. Can you give an algorithm for 'and so on'?
>>
>> "I said it's <n> of <n*2-1>" with consecutive values of n.
>
> where? This formula does not match your problem for n=1.
> Strange bully to incrementally decrease his changes.
> Or am I still not getting it?
Am was indeed not getting it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel <a_l### [at] hotmailcom> wrote:
> > "I said it's <n> of <n*2-1>" with consecutive values of n.
> where? This formula does not match your problem for n=1.
> Strange bully to incrementally decrease his changes.
> Or am I still not getting it?
The game starts with "1 out of 2" (regular coin toss). But if the bully
loses, he declares "I said it's 2 out of 3" and the game continues. If he
loses again, he declares "I said it's 3 out of 5", and so on.
In general, when he loses the n'th time, he declares "I said it's <n+1>
out of <(n+1)*2-1>".
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp <war### [at] tagpovrayorg> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
|
|
