[Guest]

I saw this puzzle the other day and after spending all of English class solving it, thought it was so cool that I had to post it... good luck

Starting at number zero, you throw a coin.

Tails means you go down one (therefore equaling -1)

Heads means you go up one (therefore equaling 1)

You repeat this procedure infinite times, so here's an example variation:

0, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 7.........

Question is: how many times on average would 0 have been 'hit' if you threw the coin N times?

[Guest]

I saw this puzzle the other day and after spending all of English class solving it, thought it was so cool that I had to post it... good luck

Starting at number zero, you throw a coin.

Tails means you go down one (therefore equaling -1)

Heads means you go up one (therefore equaling 1)

You repeat this procedure infinite times, so here's an example variation:

0, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 7.........

Question is: how many times on average would 0 have been 'hit' if you threw the coin N times?

1/2N but it can't be that simple

[Guest]

1/2N but it can't be that simple

the answer would be 1/2N example.

0TH=0TH=0TH=0TH=0TH=0-1+1=0 therefore on average every two times the coin is flipped it would result in 0.

Edited April 14, 2011 by JDM13

[curr3nt]

N/2 (rounded down) would be the max it could be since odd tosses can not equal 0.

Just because there is a 50-50 chance in a toss doesn't mean there is a 100% chance N flips will be split 50-50.

Take N = 4

There are 16 possible combinations with scoring

HHHH :  1  2  3  4

HHHT :  1  2  3  2

HHTH :  1  2  1  2

HHTT :  1  2  1  0

HTHH :  1  0  1  2

HTHT :  1  0  1  0

HTTH :  1  0 -1  0

HTTT :  1  0 -1 -2

THHH : -1  0  1  2

THHT : -1  0  1  0

THTH : -1  0 -1  0

THTT : -1  0 -1 -2

TTHH : -1 -2 -1  0

TTHT : -1 -2 -1 -2

TTTH : -1 -2 -3 -2

TTTT : -1 -2 -3 -4

Out of 64 scorings 14 were zero. If the first 0 is counted then there is 80 scorings with 30 zeros.

edit - added code tags

So average for N = 4 is 7/32 or 3/8 depending on if the first 0 is counted.

Edited April 14, 2011 by curr3nt

[curr3nt]

I am getting for even values of N (counting the first 0)

2^N + 2^N * 1/2 + 2^N * 1/2 * 3/4 + 2^N * 1/2 * 3/4 * 5/6 + 2^N * 1/2 * 3/4 * 5/6 * 7/8 + ...

So that number divided by the total count of scorings 2^N * (N + 1)

4 : ( 16 + 8 + 6) / (16 * 5)

6 : ( 64 + 32 + 24 + 20) / (64 * 7)

8 : (256 + 128 + 96 + 80 + 70) / (256 * 9)

uhm... wait... that is the chance a given scoring will be 0

Edited April 14, 2011 by curr3nt

[curr3nt]

Average count of zeros

2 = 1.5

4 = 1.875

6 = 2.1875

8 = 2.4609375

So that leads to 1 + 1 * 1/2 + 1 * 1/2 * 3/4 + 1/2 * 3/4 * 5/6 + 1/2 * 3/4 * 5/6 * 7/8 + ... + 1 * 1/2 * ... * (N-1)/N

[plainglazed]

nice solve curr3nt. really enjoyed this puzzle magician! and appreciate your hard work in English class. thanks for posting.

[curr3nt]

Didn't prove it though. I just gave an educated guess based upon evidence from a few scenerios.

[curr3nt]

Start with 0

This is where the 1 comes from

Next is 2

HH - 1 +0 leaving score of 1

HT - 1 +1

TH - 1 +1

TT - 1 +0 leaving score of -1

Here is 1/2 average being added

Roll 2 more times to get to 4 rolls

HH +1 to average if previous score was -2

HT +1 to average if previous score was 0

TH +1 to average if previous score was 0

TT +1 to average if previous score was 2

So from the result of 2 we get the following for 4

HH - 1 +1, 2 +0 leaving a score of 2, 1 +0 with a score of 4

HT - 2 +1, 2 +0

TH - 2 +1, 2 +0

TT - 1 +1, 2 +0 leaving a score of -2, 1 +0 with a score of -4

Of the half that were 0 from 2 rolls, half are +1 to the average. 1/2 * 1/2

Of the half that were +/-2 from 2 rolls, 1/4 are +1 to the average. 1/2 * 1/4

(1/2 * 1/2) + (1/2 * 1/4) = 1/2 * (1/2 + 1/4) = 1/2 * 3/4

Roll 2 more times to get to 6 rolls

HH +1 if previous score was -2

HT +1 if previous score was 0

TH +1 if previous score was 0

TT +1 if previous score was 2

From the results of the 4 rolls

Of the (1/2 * 1/2) that were 0, half are +1. 1/2 * 1/2 * 1/2

Of the (1/2 * 1/2) that were +/-2, 1/4 are +1. 1/2 * 1/2 * 1/4

Of the (1/2 * 1/4) that were 0, half are +1. 1/2 * 1/4 * 1/2

Of the (1/2 * 1/2) that were +/-2, 1/4 are +1. 1/2 * 1/2 * 1/4

Of the (1/2 * 1/4) that were +/-4, 0 are +1 but 1/4 are +/-2 now.

(1/2 * 1/2 * 1/2) + (1/2 * 1/2 * 1/4) + (1/2 * 1/2 * 1/4) + (1/2 * 1/2 * 1/4)

= 1/2 * ( (1/2 * 1/2) + (1/2 * 1/4) + (1/2 * 1/4) + (1/2 * 1/4) )

= 1/2 * 1/4 * (1 + 1/2 + 1/2 + 1/2) = 1/2 * 1/4 * 5/2 ( * 3 / 3 )

= 1/2 * (1 * 3)/4 * 5/(2 * 3)

= 1/2 * 3/4 * 5/6

Each 2 rolls added a smaller and smaller percentage of the scores are in the +2, 0 or -2 range that can be turned into 0 and adding to the average 0's.

I can continue demonstrating...but how to prove that each additional two roll adds 1/2 * 3/4 * ... * (N-1)/N to the average?

Edited April 15, 2011 by curr3nt

[Guest]

but not sure it adds.

that is, it's not 1 +1 *1/2 +1* 1/2 *3/4 +1* 1/2 *3/4 *5/6

it's simply 1 *1/2 *3/4 *5/6 ... *(n/2 -1)/(n/2))

that is if you have 32 flips, you would have

1 *1/2 *3/4 *5/6 *7/8 *9/10 *11/12 *13/14 *15/16

= 0.1964 percent zeros on average, or 32*.1964 = 6.28 zeros on average.

[Guest]

edit: sorry didn't get it in time

but not sure it adds.

that is, it's not 1 +1 *1/2 +1* 1/2 *3/4 +1* 1/2 *3/4 *5/6

it's simply 1 *1/2 *3/4 *5/6 ... *(n -1)/n)

that is if you have 32 flips, you would have

1 *1/2 *3/4 *5/6 *7/8 *9/10 *11/12 *13/14 *15/16 *17/18 *19/20 *21/22 *23/24 *25/26 *27/28 *29/30 *31/32

= 0.1399 percent zeros on average, or 32*.1399 = 4.47 zeros on average.

[Guest]

I actually used a construction very similar to Pascal's triangle for this problem.

note: I didn't count the starting zero.

it looked something like this:

-5 -4 -3 -2 -1 0 1 2 3 4 5

0

1 0

1 01 0

1 122 001 0

I started at positive 1 to skip a step because whichever the first coin flip is is actually irrelevant.

The values only go up by one and only when at 0. the number of possible outcomes that lead to 0 at each even step is (2n) C n

From this, the solution can be defined recursively: a₀=1, a_n=4*a_n-2+(2n) C n

and the expected number of zeros is a_n/2ⁿ

[curr3nt]

Question is: how many times on average would 0 have been 'hit' if you threw the coin N times?

I took this meaning how many times there would be a scoring of 0 at any point of time during the tosses, not the final scoring of 0.

If you want finally scoring then

use what I added to the total at that toss. In which case we agree.