Problem 316

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
bphillab
Posts: 5
Joined: Mon Dec 27, 2010 1:15 pm

Re: Problem 316

Post by bphillab »

georgeu2000 wrote:To Bhpillab,

Why is there a difference between flipping heads followed by tails and flipping two heads? If it is random, shouldn't the probability be the same?
To give a more succinct explanation:

Imagine the two cases where there is a mess up:
Consider the case HT:
A mess up would look like HH which can always be followed by a tails ( HHT finishes it)
Consider the case of HH:
A mess up would look like HT which needs at least two more coin flips to finish. (HTHH is required to finish)

This shows that it is shorter to get HT than it is to get HH.
I hope that this proves enlightening!

PS I ran my algorithm and your results match that of a H, HH, HHH, HHHH... I know texane had a similar error which restarted a success counter for every misstep, but this is only accurate in the case that all coins are showing the same face. Otherwise it was start you off at 1 again instead of 0.

georgeu2000
Posts: 3
Joined: Fri Dec 31, 2010 12:03 am

Re: Problem 316

Post by georgeu2000 »

Yes, that was my problem. Thanks so much for your help.

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 316

Post by harryh »

sivakd wrote:Surprisingly this problem has low private-forum-posts/solvers ratio. Perhaps due to fewer ways to solve it?
I tend to disagree :
Right now, #316 has 97 correct answers and 25 posts,
#314 has 95 correct solutions and 22 posts,
#311 has 108 correct solutions and 35 posts,
#312 has 182 correct solutions and 44 posts,
#305 has 185 correct solutions and 43 posts...
so it seems that the ratio mentioned by sivakd is ~ 1/4 all around :)

Anyway, I can assure you that there are at least two different approaches to a solution (plus the usual fair number of variants thereof...).
Susanne wrote:By the way, it surprises me that solving problem 316 is discussed so detailed in this forum. For other problems such discussions mostly were rejected.
You are not complaining, I presume... 8-)
The piece of code posted by texane, the comments on what's wrong with it etc are merely connected with simulating some small-value cases. Of course, such simulations will never solve the problem efficiently; however, I consider them to be very useful in providing essential understanding.
I could be wrong, but I think that the same applies to the other explanations posted above: they are connected with understanding the essence (rather than providing solutions).
It may well be true that the discussion is unusually detailed, but then, it's an unusual sort of problem too, isn't it?

Susanne
Posts: 32
Joined: Sun Nov 08, 2009 7:39 am

Re: Problem 316

Post by Susanne »

Hello harryh,

Of course it is no reason to complain if more information about a problem is given. There are even several other problems for which I would be glad to be given some advice. It just bothered me, that in this case debating a problem was allowed and in former cases had not been allowed. Thank you for de-escalating this situation.

Happy New Year, Susanne
Image

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 316

Post by sivakd »

harryh wrote: so it seems that the ratio mentioned by sivakd is ~ 1/4 all around :)
harryh, thanks for the analysis. My post was based on the observation that my first private forum post was 11th while I was 66th or 67th solver for this problem. That's 1/6.
Image
puzzle is a euphemism for lack of clarity

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 316

Post by sivakd »

Susanne, I know what you are saying but we all need to master the art of asking and replying the right way that it doesn't spoil the fun for others. When in doubt, best way is to just ask someone to volunteer to look at your code or your specific question in private message.
Susanne wrote:Hello harryh,

Of course it is no reason to complain if more information about a problem is given. There are even several other problems for which I would be glad to be given some advice. It just bothered me, that in this case debating a problem was allowed and in former cases had not been allowed. Thank you for de-escalating this situation.

Happy New Year, Susanne
Image
puzzle is a euphemism for lack of clarity

bphillab
Posts: 5
Joined: Mon Dec 27, 2010 1:15 pm

Re: Problem 316

Post by bphillab »

I have empirically derived a couple of formulae by looking at some patterns for g(x) in the case of repeating and non-repeating representations. I understand the reasoning for the non-repeating case as it is presented here by a number of people, but I can't quite get the reasoning behind the repeating case, could someone who has solved the problem confirm my formula just so I know it isn't moonshine math?

Susanne
Posts: 32
Joined: Sun Nov 08, 2009 7:39 am

Re: Problem 316

Post by Susanne »

sivakd said:
Susanne, I know what you are saying but we all need to master the art of asking and replying the right way that it doesn't spoil the fun for others. When in doubt, best way is to just ask someone to volunteer to look at your code or your specific question in private message.
sivakd, thanks for your reply.
Image

User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Problem 316

Post by Lord_Farin »

Shouldn't the interval from which is picked be [0,1]? For 0.999... = 1 is possible to select.
Image

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problem 316

Post by stijn263 »

Yes, that might be more consistent with the fact that 0 is included in the interval.

We could also change it to (0,1) as both 0.00000.. and 0.9999999.... have probability 0.

User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Problem 316

Post by Lord_Farin »

stijn263 wrote:Yes, that might be more consistent with the fact that 0 is included in the interval.

We could also change it to (0,1) as both 0.00000.. and 0.9999999.... have probability 0.
Any specific real number has probability zero. Shouldn't we change it to the empty set by that reasoning? :)
Image

voltara
Posts: 2
Joined: Fri May 03, 2019 7:10 am

Re: Problem 316

Post by voltara »

The problem description for 316 appears to have a typo in it. The upper limit of the summation is off to the right of the $\sum$ rather than above it: $\sum \limits_{n = 2}{999999}$. It should read $\sum \limits_{n = 2}^{999999}$ instead.

User avatar
Animus
Administrator
Posts: 1907
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 316

Post by Animus »

voltara wrote:
Fri May 03, 2019 7:30 am
The problem description for 316 appears to have a typo in it. The upper limit of the summation is off to the right of the $\sum$ rather than above it: $\sum \limits_{n = 2}{999999}$. It should read $\sum \limits_{n = 2}^{999999}$ instead.
Thanks, changed. (That typo must have sliped in during the last site update).

Post Reply