Problem 316

[bphillab]

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]

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

[harryh]

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 ~ ¹/₄ 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...).

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...
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]

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

[sivakd]

so it seems that the ratio mentioned by sivakd is ~ ¹/₄ 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 ¹/₆.

[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.

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

[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]

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.

[Lord_Farin]

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

[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.

[Lord_Farin]

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?

[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.

[Animus]

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).