Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A pair of positive integers $x_0$ and $y_0$ are selected and further pairs are generated according to the following rule:

After the values of $x_n$ and $y_n$ have been found, a coin is tossed. If it lands heads, then $x_{n+1} = x_n −1$ and $y_{n+1} = x_n$. Otherwise, if it lands tails, then $x_{n+1} = y_n − 2$ and $y_{n+1} = x_n + 1$.

The process ends when a non-positive value of $x$ or $y$ is generated. Is there a choice of initial values for $x_0$ and $y_0$ and sequence of coin toss outcomes for which the sequence of $x$’s and $y$’s does not terminate?

share|improve this question
    
By the "Q2" in the original post, and the lack of motivation I have added the [homework] tag, if this is not actually a homework question feel free to remove it. –  Asaf Karagila Jan 28 '12 at 21:05
    
No (probability) here. –  Did Jan 30 '12 at 18:35

1 Answer 1

The process ends for every starting point and every sequence of moves.

Call $h:(x,y)\mapsto(x-1,x)$ and $t:(x,y)\mapsto(y-2,x+1)$. For every $x$, let $u_x=(x,x+1)$. Call $U$ the set of points $u_x$ and $x$ the rank of the point $u_x$.

Then $t\circ t:(x,y)\mapsto(x-1,y-1)$ hence if one uses $t$ only, the process ends. As soon as one uses $h$, the result is $h(x,y)=u_{x-1}$ hence one lands in $U$.

Now, $h(u_x)=u_{x-1}$, $t\circ t(u_x)=u_{x-1}$ and $h\circ t(u_x)=u_{x-2}$, hence, from this moment on, one stays in $U$ every one or two steps. The sequence of the ranks is decreasing hence the ranks cannot stay positive forever.

It seems that no path starting from $(x,y)$ with length at least twice the maximum of $x$ and $y$, lies entirely in the positive orthant.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.