A binary coin

Probability Level pending

You have a fair coin with a "1" on one side and a "0" on another side. You decide to flip it until you get a string of "1"s and "0"s that is the binary representation of a number you are thinking of.

e.g. If you pick the number 3, then its binary representation would be "11" and the expected number of flips to get this combination would be 6.

Now for the question:

What is the smallest integer, n n , such that the expected number of flips to get its binary representation is greater than 40

Note: Leading zeros aren't allowed. i.e. The number 5 would be represented by 101, not 0101 nor 00101.

Image credit: www.tes.com


The answer is 21.

Geoff Pilling by Geoff Pilling , 53, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Geoff Pilling
Jul 1, 2016

The binary representation of 21 \boxed{21} is " 10101 10101 " and the expected number of flips for getting this combination is 42 42 , the smallest integer whose expected number of flips is greater than 40 40 .

This is calculated a follows:

Define E n E_n as the expectation value for getting the pattern 10101, given that you are already on the nth digit. i.e. E 2 = E_2 = The expectation value given that you already have " 10 10 " (but not " 1010 1010 ")

So,

  • E 0 = 1 + ( 1 / 2 ) ( E 0 + E 1 ) E_0 = 1 + (1/2)(E_0 + E_1)
  • E 1 = 1 + ( 1 / 2 ) ( E 1 + E 2 ) E_1 = 1 + (1/2)(E_1 + E_2)
  • E 2 = 1 + ( 1 / 2 ) ( E 0 + E 3 ) E_2 = 1 + (1/2)(E_0 + E_3)
  • E 3 = 1 + ( 1 / 2 ) ( E 1 + E 4 ) E_3 = 1 + (1/2)(E_1 + E_4)
  • E 4 = 1 + ( 1 / 2 ) E 0 E_4 = 1 + (1/2)E_0

Solving for E 0 E_0 , you find E 0 = 42 E_0 = \boxed{42} .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...