Hmm, this problem seems familiar

Suppose I have a line of squares, labelled 0, 1, 2, 3, 4, ... and so on. I place a counter on the square 0. On every turn, I roll a fair die (with the numbers 1 to 6) and move forward as follows: if I was on square P P before the roll and I get a x x then I move to square P + x P+x . Let X n X_n be the chance that I land on the square labelled n n , where n n is a positive integer . What is

max ( 1000 X n ) ? ? \lfloor\text{max}(1000X_n)\rfloor? \quad ?

If the maximum doesn't exist, find the infimum of the set of X n X_n .

Notation : \lfloor \cdot \rfloor denotes the floor function .


The answer is 360.

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

For 1 n 6 1 \leq n \leq 6 , X n = k = 1 n N n , k / 6 k X_n = \sum_{k=1}^{n} N_{n,k}/6^k where N n , k N_{n,k} is the number of writing k numbers (from 1 to 6) so that they add up to n n . Since 1 n 6 1 \leq n \leq 6 , this is just the number of k-tuples of positive integers ( a 1 , , a k ) (a_1, …, a_k) such that a 1 + + a k = n a_1 + … + a_k = n . So N n , k = ( n 1 choose k 1 ) N_{n,k} = (n-1 \text{ choose } k-1) (using the usual stars and bars method).

For n > 6 n>6 , note that X n = k = 1 6 X n k / 6 X_n = \sum_{k=1}^{6} X_{n-k} / 6 . We have determined X n X_n and it is straightforward to show that the maximum is attained at n = 6 n=6 with X 6 = 16807 / 46656 X_6 = 16807/46656 . For example, it might be helpful to show that X n = ( 2 + r 1 n + + r 5 n ) / 7 X_n = (2+r_1^n+ … + r_5^n)/7 where r 1 , . . . , r 5 r_1,..., r_5 are the five complex roots of 6 x 6 x 5 x 4 x 3 x 2 x 1 6 x^6-x^5-x^4-x^3-x^2-x-1 which are not one, and note that r i < 1 |r_i| < 1 .

improve more

improve more - 2 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...