Let $P$ be a point in a square whose side are mirror. A ray of light comes from $P$ and with slope $\alpha$. We know that this ray of light never arrives to a vertex. We make an infinite sequence of $0,1$. After each contact of light ray with a horizontal side, we put $0$, and after each contact with a vertical side, we put $1$. For each $n\geq 1$, let $B_{n}$ be set of all blocks of length $n$, in this sequence. a) Prove that $B_{n}$ does not depend on location of $P$. b) Prove that if $\frac{\alpha}{\pi}$ is irrational, then $|B_{n}|=n+1$.
Problem
Source: Iran TST 2007, Day 4
Tags: analytic geometry, graphing lines, slope, trigonometry, geometry, geometric transformation, reflection
28.05.2007 21:48
Omid Hatami wrote: Let $P$ be a point in a square whose side are mirror. A ray of light comes from $P$ and with slope $\alpha$. We know that this ray of light never arrives to a vertex. We make an infinite sequence of $0,1$. After each contact of light ray with a horizontal side, we put $0$, and after each contact with a vertical side, we put $1$. For each $n\geq 1$, let $B_{n}$ be set of all blocks of length $n$, in this sequence. a) Prove that $B_{n}$ does not depend on location of $P$. b) Prove that if $\frac{\alpha}{\pi}$ is irrational, then $|B_{n}|=n+1$. What's a block?!
29.05.2007 15:56
Every block of length $n$ is a $n$-tuple such as $(a_{k},a_{k+1},\dots,a_{k+m-1})$.
30.05.2007 16:02
Omid Hatami wrote: Let $P$ be a point in a square whose side are mirror. A ray of light comes from $P$ and with slope $\alpha$. We know that this ray of light never arrives to a vertex. We make an infinite sequence of $0,1$. After each contact of light ray with a horizontal side, we put $0$, and after each contact with a vertical side, we put $1$. For each $n\geq 1$, let $B_{n}$ be set of all blocks of length $n$, in this sequence. a) Prove that $B_{n}$ does not depend on location of $P$. b) Prove that if $\frac{\alpha}{\pi}$ is irrational, then $|B_{n}|=n+1$. I have proved that : if $\tan\frac{\alpha}{\pi}$ is irrational, then $|B_{n}|=n+1$,So I believe there is a typo. I am sorry that I am not able to post my solution,becuase my english is too bad ,and this is a combinatorics problem.......... @Omid Hatami,Could do please check if there is a typo?And do you have an official solution.Thanks
30.05.2007 17:35
Yes you're right. It is $\tan \frac{\pi}{\alpha}$
18.07.2007 11:17
I guess that $ \alpha$ (the slope) should be irrational, otherwise just take a line parallel to the diagonal and we have $ |B_{n}|=2$. As in most reflection problems, instead of reflecting the path we reflect the square. Thus we construct a lattice grid and for each ray with slope $ \alpha$ we associate the sequence of $ 0$ and $ 1$. Clearly any translation with integer coordinates preserves the sequence so we may consider points which are lattice translates of each other equivalent. a) Assume that $ \alpha$ is irrational. Then the ray $ r$ will pass as close as wanted to a point equivalent to $ Q$ whatever may $ Q$ be. Indeed, if $ P$ has coordinates $ (x,y)$ but $ Q$ has coordinates $ (x',y')$ the ray $ r$ will pass through points of coordinates $ (x+k,y+k\alpha)$. If we take $ k=x'-x+n$ where $ n\in N$ then $ r$ will pass through $ (x'+n, y+(x'-x)\alpha+n\alpha$. As $ \{n\alpha\}$ is dense in $ [0;1]$ this point can be made as close to a point equivalent to $ Q$ as we wish. Now if we have a block of $ n$ digits for $ Q$, if the ray $ r$ passes through a point $ Q'$ close enough to a translate of $ Q$, this block will also appear on ray $ r$, so in the block for $ P$. So the set of blocks is independent of $ P$. Assume that $ \alpha$ is rational. Then if a ray with slope $ \alpha$ meets a lattice point it meets infinitely many lattice points. Draw through each lattice point a ray with slope $ \alpha$. It is easy to see that $ R^{2}$ is then partitioned into infinitely many discrete strips (the region between two lines parallel to $ \alpha$) that do not contain lattice points in the interior. If $ P,Q$ are in the same strip we can move $ P$ to $ Q$ and in the process the sequence of $ 0$ and $ 1$ will not change (it will change if and only if the ray with slope $ \alpha$ passes through a lattice point, but there are no such points inside a strip). So $ |B_{n}|$ is the same for $ P$ and $ Q$. Finally if $ P$ and $ Q$ are in different strips then there exists a lattice translation that maps $ P$ to a point in the same strip with $ Q$ and lattice translations do not significantly affect the (periodic) sequence of $ 0$ and $ 1$. b) As we have proven in a), every sequence of $ 0$ and $ 1$ that may EVER appear for some point $ Q$ appears also for every other point $ P$. So we have to prove there are exactly $ n+1$ differenct sequences of length $ n$. Let $ OACB$ be a unit square. Assume that $ O$ is the origin, $ A$ has coordinates $ (0,1)$ and $ B$ has coordinates $ (1,0)$. We may assume we start counting from a point inside it and that the ray $ r$ with slope $ \alpha$ intersects $ [AC]$ or $ [BC]$ for every such point. It is clear we may move the point on the line $ r$ as long as it remains inside the square so we may assume it is on $ [OA]$ or $ [OB]$. Now let's draw the staircase with alternating horizontal and vertical unit steps connecting the points with coordinates $ (x,y)$ where $ x,y \in \mathbb{N_{0}}$ and $ x+y=n+1$. A ray through $ P$ intersects this staircase at a point $ Q$ and the block of $ n$ digits is uniquely defined by the alternation of horizontal and vertical segments on the segment $ (PQ]$. Now let's move $ P$ continuously from $ B$ to $ O$ then to $ A$. The point $ Q$ will also move continuously from a point $ K$ to a point $ L$ and $ KLAB$ is a parallelogram. Next the sequence changes if and only if $ (PQ]$ passes through a lattice point inside $ KLAB$ (or on the boundary, but not in a vertex). When it does, the change that occurs if of the following type: take a $ 0$ followed by a $ 1$ and exchange their places. Only one counter example: when it passes (once) through the lattice point between $ K$ and $ L$ on the staircase the operation will change the last $ 0$ into $ 1$, and this point is outside $ KLAB$. Thus if we have $ l$ lattice points inside $ KLAB$ we will have $ l+1$ changes so $ l+2$ blocks. These blocks will be different because each change increases by $ 1$ the monovariant which is the sum, for all unities, of $ n+1-p$ where $ p$ is the position of that unity in the block. So we have $ |B_{n}|=l+2$. It only remains to count $ l$. $ KLAB$ is sandwiched between the strip defined by the conditions $ 1\leq x+y\leq n+\delta$ where $ 0<\delta<1$. However, of each set of lattice points whose sum of coordinates is $ k$ ($ 1<k\leq n$) exactly one point belongs to $ KLAB$: this is because thes point lie on a line parralel to $ AC$ and $ KL$ at distances $ \sqrt 2$ apart, whereas $ KLAB$ intersects this line in a nontrivial segment of length $ \sqrt 2$. As $ k$ may take $ n-1$, values, $ l=n-1$ so $ |B_{n}|=n+1$.