help plz...

Printable View

Show 40 post(s) from this thread on one page

February 2nd 2006, 11:03 PM
yiyayiyayo

help plz...

Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips?
February 2nd 2006, 11:27 PM
yiyayiyayo

another one

Some integers can be expressed as the sum of two or more consecutive positive integers. For example, 17 = 8+9, 24 = 7+8+9. Other integers, such as 8, cannot be expressed that way. Which integers can be expressed as a sum of two or more consecutive positive integers, and which cannot? See if you can prove your answer.
February 3rd 2006, 02:02 AM
CaptainBlack

Quote:

Originally Posted by yiyayiyayo

Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips?

Do you mean given a sequence a flips which may continue as long as we
like, what is the probability that at some time in this sequece of flips we
have the number of heads so far equals the number of tails so far?

RonL
February 3rd 2006, 02:11 AM
yiyayiyayo

The answer is 2*min(p,1-p).
Could you tell me how to do it?
Thank you.
February 3rd 2006, 09:12 AM
ThePerfectHacker

Quote:

Originally Posted by yiyayiyayo

Some integers can be expressed as the sum of two or more consecutive positive integers. For example, 17 = 8+9, 24 = 7+8+9. Other integers, such as 8, cannot be expressed that way. Which integers can be expressed as a sum of two or more consecutive positive integers, and which cannot? See if you can prove your answer.

I like the problem.
Now observe the following:

Those expressed as 2 consecutives:
$n+(n+1)=2n+1$
Those expressed as 3 consecutives:
$n+(n+1)+(n+2)=3n+3$
.................................................. .....
Those expressed as $k$ consecutives:
$\sum^{k-1}_{j=0}(n+j)=kn+\frac{k(k-1)}{2}$ .

Thus, a number $m$ has the form of
$m=kn+\frac{k(k-1)}{2}$ if and only if it can be expressed as consectutives. (Although the converse part was omitted in the proof, I assume you see it).

Thus the answer to your question is the above statement. To put it more elegantly:
If the Diophantine equation
$2m=2kn+k(k-1)=k(2n+k-1)$
has a solution for a given $m$ for certain $k,n$ if and only if $m$ can be expressed as consecutives.
Q.E.D.
I am trying to see if I can simplify what I just said. I think it might be brought to the Pellian equation, but that needs some work. If I find a way I will respond back.
February 3rd 2006, 09:23 AM
ThePerfectHacker

Quote:

Originally Posted by yiyayiyayo

Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips?

The infinite part gives me confusion. See, that if the number of flips is an odd number there is no way how they can be equal! However, the problem changes when you are speaking of an even number because that is possible.

Let me explain why the infinity part gives me confusion. Let $f(x)=\left\{\begin{array}{cc}P(x)&\mbox {if even}\\0&\mbox{if odd}\end{array}\right$
Where $P(x)$ is the probability of getting for same head and tails for even amount of throws which as said above exists. Now when you say infinity I understand that as,
$\lim_{x\to \infty}f(x)=?$ , I believe it diverges by osicallation, does it not?
February 3rd 2006, 09:36 AM
CaptainBlack

Quote:

Originally Posted by yiyayiyayo

The answer is 2*min(p,1-p).
Could you tell me how to do it?
Thank you.

Right, I can solve this, but the solution is does not qualify as high school
maths. Are you sure that you don't already have a short cut for this problem
in your notes or textbook?

Also its a lot of typing, I will start typing the solution in about 3 hours.

RonL
February 3rd 2006, 09:44 AM
ThePerfectHacker

I am guessing that this has something to do with the Strong Law of Large numbers. Because if it was a fair coin, $p=1/2$ then, as you increase the number of throws by the Strong Law of Large Numbers is $2(1/2)=1$ (this is the answer as you claim in your previous post), which is true.
February 3rd 2006, 10:58 AM
CaptainBlack

Quote:

Originally Posted by ThePerfectHacker

I am guessing that this has something to do with the Strong Law of Large numbers. Because if it was a fair coin, $p=1/2$ then, as you increase the number of throws by the Strong Law of Large Numbers is $2(1/2)=1$ (this is the answer as you claim in your previous post), which is true.

No, these problems are all essentially the same, the trick is to find a
recurrence relation satisfied by some probability related to the task in hand,
solve the recurrence relation then use that to solve the problem.

It's rather more LaTeX than I fancy typing at the moment (I'm suffering from
too much keyboard hammering - its report writing time at work).

RonL
February 3rd 2006, 12:37 PM
CaptainBlack

Quote:

Originally Posted by yiyayiyayo

Given a coin with probability p of landing on heads after a flip, what is the probability that the number of heads will ever equal the number of tails assuming an infinite number of flips?

We have a coin with probability of coming up heads when tossed $p$ .
We want to know the probability in a long string of tosses of the
number of heads equalling the number of tails. In particular we want to
know the limit of this probability as the length of the sequence of
tosses tends to $\infty$ .

Let $k_n$ denote the difference between the number of heads and the number
of tails after $n$ tosses. So we are asking for the probability that

$k_n=0$ ,

for at least one $n>0$ .

Now suppose that at some stage in this sequence the difference between
the number of heads and the number of tails is $k$ . Also let $P_k$ be the
probability that starting from a point where the difference is $k$ , that
at some subsequent point the difference is $0$ . Then clearly:

$P_k=qP_{k-1} + pP_{k+1}$ ,

since with probability $p$ after the next toss the difference will be
$k+1$ , and with probability $q=(1-p)$ it will be $k-1$ .

Now this difference equation is the analog of a second order linear
ordinary differential equation with constant coefficients, and we solve
it in a similar way. I will explain it another time if you want to see
it, but the solution is:

$P_k=(q/p)^k$ , if $p>q$ ,
$P_k=1$ , if $p\le q$ .

Now this does not immediately give our answer as by convention $P_0=1$ ,
as we in fact count the current difference in this process. But after
one toss we have a difference of $1$ with probability $p$ , and a difference
of $-1$ with probability $q$ , and so the probability of the difference ever
returning to $0$ is:

$P_{return}=pP_1+qP_{-1}$ .

So, supposing $p>q$ :

$P_{return}=p.(q/p) +qP_{-1}$ .

Now $P_{-1}$ is equal to $P_1$ , but with $p$ and $q$ interchanged, and so:

$P_{return}=p(q/p)+q \times 1=2q$ .

That is $P_{return}=2 \times \min (p,q)$

RonL
February 4th 2006, 05:54 PM
yiyayiyayo

Thank you

Quote:

Originally Posted by CaptainBlack

Right, I can solve this, but the solution is does not qualify as high school
maths. Are you sure that you don't already have a short cut for this problem
in your notes or textbook?

Also its a lot of typing, I will start typing the solution in about 3 hours.

RonL

I saw the first problem in a magazine not in my textbook,so you can work it out in any ways.And thank you for your later typing.

The second one is from Cambridge College Math Institute and the answer to this problem will not be given untill several months later. Anyone who works it out can send email to puzzlemaster@cambridgecollege.edu with your solution.

Thank you , thank you for your thinking and typing,
and words fail me to say anything others.
:) ;) ;) ;) ;)
February 4th 2006, 06:24 PM
ThePerfectHacker

The problems were very nice problems.
February 5th 2006, 09:48 AM
ThePerfectHacker

I was further thinking about the second problem you gave. I believe I have a simplified version other than I posted previously. I think (not completely proven but close to it) that all number which CANNOT be expressed as the sum of consecutives is of the form $2^n$ .

I will not post my solution now, but later on in a few hours, I do not have enough time now.
February 6th 2006, 02:47 PM
ThePerfectHacker

Let me show my proof to problem 2.

Notice that a number expressed, as $m$ consecutives (odd number), then we have,
$n+(n+1)+(n+2)+...+(n+m-1)$ ,
Thus,
$mn+\frac{m(m-1)}{2}$ ,
Now $m-1$ is even, thus,
$mn+mj$
where $j$ is an integer thus,
$m(n+j)$ .
Thus, if a number can be expressed as a sum of $m$ (odd) consecutives, then it is divisible by $m$ .

Now we prove, the converse (not exactly a converse you will see). That if a number is divisible by $m$ then, we can express it as a sum of consecutives (I did not say $m$ consecutives rather I said it can be expressed as consecutives!). If $m|n$ then there exists $k$ such as $mk=n$ . Thus, instead of $k$ write $m(j+s)=n$ where $j=(m-1)/2$ (as before), thus we can find such an $s$ . The problem is that $s$ can be a negative number. Thus, the number can be expressed as:
$n=s+(s+1)+(s+2)+...+(s+m-1)$ .
The following is the foundation of the proof; observe that if a number is expressed as a sum of consecutives starting from a negative number then it still can be expressed as a sum of consecutives! Because they cancel each other out. Observe,
(-4)+(-3)+(-2)+(-1)+0+1+2+3+4+5+6+7
Now follow with me. A number is expressed as a sum of consecutives from a negative number. Then they cancel each other out, and you are left with,
5+6+7,
still a sum of consecutives.
The problem is of course if they cancel each other out in such a way then you a left with a single number. For example,
(-1)+0+1+2, becomes,
2.
But 2 is not expressing 2 as a sum of consecutives by just 2 (that is trivial).
But to show this does not happen over here is because since $m$ is an odd number, and zero is part of this expansion, thus there are a total of even numbers. Thus, either the number of negatives is more than positives (which is not possible). They are equal (which is not possible). Thus, the number of positives must overtake the number of negatives by and even amount! Thus at least two which is considered a sum of consecutives.

Now we have that ANY number divisible by any odd number CAN be expressed as a sum of consecutives. Thus, if a number IS NOT expressable as a sum of consecutives it must have the form $2^n$ .

Finally, we prove the converse, that if a number has the form $2^n$ then it cannot be expressed as a sum of consecutives, then we have that,
$2^n=a+(a+1)+...+(a+b-1)$
Thus,
$2^n=ab+\frac{b(b-1)}{2}$
Thus,
$2^{n+1}=2ab+b(b-1)$
Thus,
$2^{n+1}=b(2a+b-1)$ .
Since of equality and the fact we are using integers we have that $b$ cannot have odd factors thus,
$b=2^{m}$ ,
Thus,
$2^{n+1}=2^m(2a+2^{m+1}-1)$
But the right factor of the LHS is odd,
Thus an impossibility.
Thus, all and only thus of the form $2^n$ . Cannot be expressed as a sum of consecutives.
Q.E.D.

I hope I did not make a mistake in proof. I think this is a nice problem and I had fun solving it.
February 6th 2006, 06:48 PM
yiyayiyayo

You're very kind,and I really hope too much typing didn't trouble you. Though I want to say something,my poor English frustrated me, sorry.
In one word, your proof is wonderfull.Thank you.

Show 40 post(s) from this thread on one page

All times are GMT -8. The time now is 06:39 AM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.