Problem 316

[abdyresul]

I couldn't understantd the problem 316 how to choose value of p. Please help me with that if anybody has read this problem.

[TripleM]

Problem 316 (View Problem)

p is chosen uniformly at random - you have to calculate the expected (average) position of a certain integer over all possible values of p.

[abdyresul]

Thank you TripleM, I got it

[bphillab]

Sorry to hijack the thread, but I didn't really want to open a new one if I didn't have to.

I'm having some trouble with this problem. I'm sensing that there should be a pen and paper solution, however my methods tell me that the average number of digits you need to go before finding a 3 digit pattern is slightly larger (about 100 more) I know this implies a flaw in my methodology, but I'm not sure what in particular is wrong. I hope I'm not violating any rules if I leave everything a bit more cryptic, but my method involves relating the probability for an N digit number terminating in the sequence 000 to the probability that an N-1 digit number terminating in the same sequence and the probability an N-2 digit number terminates in 000. I then use a German "innate" method to figure out the probability as a function of N, then do a weighted average.

Does anyone know where I'm going wrong with this little amount of cryptic information? If you need more I can add a bit more in private conversation.

edit: My error was failure to account for the fact that 000 is not equivalent 535! As noted if I get 5535 the answer is 2, however my method wouldn't pickup on such possibilities. This means my method should work for numbers of the form aaa, but fails for permutations of aab and abc, with a,b,c all different numbers.

[texane]

Hi,

I dont know if it helps you, but the following code:

Code: Select all

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>

static unsigned int gn()
{
  unsigned int state = 0;
  unsigned int count = 0;

  for (; state != 3; ++count)
  {
    const unsigned int n = rand() % 10;
    if (state == 0 && n == 5) ++state;
    else if (state == 1 && n == 3) ++state;
    else if (state == 2 && n == 5) break ;
    else state = 0;
  }

  return count;
}

int main(int ac, char** av)
{
  srand(getpid() * time(NULL));

  unsigned int sum = 0;
  for (unsigned int i = 0; i < 100000; ++i)
    sum += gn();
  printf("%lf\n", (double)sum / 100000);
  return 0;
}

outputs something like 1109, not 1008... actually
100 more digits.

[harryh]

@texane : There seem to be at least two errors in your code:

(a) When state==1 && n==5, the inner loop returns state=0. Imo, it should return state=1.

(b) When 535 is eventually found and you break out of the inner loop the variable "count" is not the index of the first digit, as the problem states.

Hopefully, that helps to set you on the right track

@bphillab :

No need to worry about "hijacking the thread". You've done exactly what you are expected to do:
For a given problem, always use an existing thread (if it's there).

I'm not sure I understand your method, but I guess you are making the same (or similar) mistakes as texane.
If so, please take a look at the answer above.

[texane]

Hi,

Thanks for the comments. I don t understand the first one but agree
with the second... I corrected the mistake inbetween but always get
1109 instead of 1008. By the way, I do not use this code in my (still
in progress) solution...

edit: no you are right, by taking the first digit we get the right answer.

Cheers,

f.

[bphillab]

@harryh:
I suspect you are right. To clarify my method slightly, now that I see what is acceptable:
My plan was to use:
\begin{equation*}
P_N = \frac{9}{10} P_{N-1} + \frac{9}{100} P_{N-2} + \frac{9}{1000} P_{N-3}
\end{equation*}
Allowing me to make a matrix representing going from $P_{N-1}, P_{N-2}, P_{N-3} \rightarrow P_{N}, P_{N-1}, P_{N-2}$ then solve for eigenvalues and eigenvectors finally take a weighted sum and done.
It looks like this solution method won't work as easily as I originally planned. Oh well back to the drawing board!

[texane]

Hi,

Could someone point me to the maths needed
to prove that g(535) = 1008? I have trouble
understanding this... Intuititvely I would say the
odd a 1/1000 (ie. 1/10 * 1/10 * 1/10), thus g(xxx)
is 1000, no?

Thanks for helping,

f.

[stijn263]

Perhaps it's best to look at a simpler problem:
What's the expected number of coin flips needed until you've flipped heads followed by tails?
What's the expected number of coin flips needed until you've flipped heads followed by another heads?
Can you explain the difference?

Good luck!

[raggie]

@texane
your code doesn't work for numbers like 53531 (don't know whether they appear in the problem), because if it finds ***53535, it wil jump to zero at the last 5, but it should be 3, because at new 'instance' of the number alrady started.

[bphillab]

Perhaps it's best to look at a simpler problem:
What's the expected number of coin flips needed until you've flipped heads followed by tails?



For this I get 3: once we get one heads (h) we'll have a chain of heads until it completes with a tails.
edit: This was a quick calculation via induction & brute force, I found a way to solve the presented problem using m proposed method and present it here instead.

Let $P_i ^{(n)}$ be the probability that given $n$ digits are correct before starting the chain that the $i$th component will terminate the chain. ($i$ corresponds to $k$)
Then: $P_N ^{(0)} = (2-1)/2 P_{N-1} ^{(0)} + 1/2 P_{N-1} ^{(1)}$
and: $P_N ^{(1)} = (2-2)/2 P_{N-1} ^{(0)} +1/2 P_{N-1} ^{(1)}+1/2 P_{N-1} ^{(2)} = 1/2 P_{N-1}^{(1)}$
one can form a matrix and solve for probability as a function of N given the initial conditions of $P_0 ^{(0)}$ and $P_0 ^{(1)}$ which should both be $1/4$. This ends up giving me 3. That number is confirmed by simulation.


What's the expected number of coin flips needed until you've flipped heads followed by another heads?

From Monte Carlo I get 5.
My method gives 5 and is applicable for this part.

[bleach1005]

i just want to know, how can i get 1008 ??

[stijn263]

Once you know that, you've more or less solved the entire problem. Perhaps you can verify the 1008 by coding a simulation? Good luck!

[sivakd]

Surprisingly this problem has low private-forum-posts/solvers ratio. Perhaps due to fewer ways to solve it? I also felt this problem to be reasonably difficult but perhaps due to the way I approached the problem.

[Susanne]

sivakd said:

I also felt this problem to be reasonably difficult

I do so, as well and could not solve the problem yet.
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.

Regards, Susanne

[georgeu2000]

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?

Also, I implemented texane's code (working in VS 2008 C++), but I don't get clear answers. Do you think it is because rand is not random enough?

Here's what I did figure out, in case it helps other people: For the coin flip, the expected values for strings of length x are: f(1) = 2, f(2) = 5, f(3) = 12, f(4) = 27.

By the way, Project Euler is super cool. I think it is the best way to learn a programming language ever! Thank you!

[stijn263]

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?

Did you code a simulation to see whether this is a reasonably assumption?

[georgeu2000]

Yes. Apparently I am not supposed to post the code...

Looking at bphillab's post I get the feeling there is an error in my logic...

[TripleM]

If you want to PM me your code for the head/tail case, I can explain either what you did wrong or why it shouldn't be equal.