H6X9H


Reduction

Figures with small values for N and D are quite simple, comparable to situation a). On the other hand, figures with big values may become fairly complex. But one can observe that such complex figures have roughly simpler forms with some small pattern on top of it. In the sequel we will show how complex figures relate mathematically to simpler figures.
Consider situation b) at the Analysis section. The chunk
RK LK can be considered as a small pattern inside the figure. The position before and after drawing this pattern might be changed, but the orientation remains the same. However, the other 2 types of chunks do change the orientation to the right (for RK+1 LK) or to the left (for RK LK+1). A new, reduced figure can be constructed by ignoring the chunks RK LK, and by replacing chunk RK+1 LK with a single direction R, and similarly replacing RK LK+1 with L. This new figure has a recipe with N’ = E directions.
We will prove, with some geometrical support, that the new denominator D' equals D mod (2*N’), and that the replaced chunks correspond to the recipe based on pair (N’, D’).
Consider a 2-
dimensional coordinate system with a horizontal x-axis and a vertical y-axis. Define the points (t*D, t*D) where t runs from 0 to N . The first N points correspond to the points for constructing the recipe. All these points lie on a straight line at equidistant pieces. Along the x-axis we focus on multiples of D. Therefore, we can scale the points to (t, t*D). Along the y-axis we focus on multiples of N. Also this axis is scaled, but now by a factor N, yielding points (t, t*D/N) . The points still lie on a straight line at equidistant pieces running from (0,0) to (N,D). (Note the analogy of drawing a line on a graphics display.) Consider the D rows between coordinates y and y+1 where y runs from 0 to D-1. Each row covers either K points or K+1 points from the line. A row with even y-coordinate contains points that yield an R direction, and a row with odd y-coordinate contains points yielding an L direction. An even row and an odd row together relate to a chunk; so, it is clear that a recipe has D/2 chunks.
The rows cut the line in equal parts. Each part has a length along the x-axis of N/D = K + E/D
. The right hand side has 2 terms: K is the minimum number of points that are always present in a row; the term E/D is responsible for the (K+1)th points after accumulation of some rows. Considering N = N(K) as a function of K, the row location of the additional point does not depend on K, because E/D and K are independent. So, we can take K=0, and consider the problem of the E additional points (t, t*D/E) that are located equidistant on a line from (0,0) to (E, D). Now, the line is transformed, such that from each point the y-value t*2 is subtracted. This is possible since E<D/2 . All the transformed points remain equidistant at a straight line. Furthermore, a point at an even row lands again in an even row, and the same holds for the odd rows. So, the directions of the points are preserved. The end coordinate of the line becomes (E, D-2*E) . The transformation is repeated until the end coordinate becomes (E, D mod (2*E)), being the end coordinate (N’, D’) of the reduced line. The configuration of the line from (0,0) to (N’, D’) is analoguous to the configuration of the original line from (0, 0) to (N, D) . Therefore, we conclude that the reduced line corresponds to a figure based on the numbers N’ and D’.

Now, consider situation c) being a bit trickier because the reduced number of directions N’ equals (F+1)/2 + (F-1)/2 = F . We will show that the reduced value D’ equals D mod (2*F). For this proof the line configuration is transformed extensively. As in situation b) the line can be reduced to: (0, 0) -> (E, D) . Subtract the line (0, 0) -> (E, 2*E), so that all directions are preserved. This gives (0, 0) -> (E, D-2*E) with an end point below the x-axis. So, add the constant 2*E-D to all y-coordinates yielding (0, 2*E-D) -> (E, 0) . Applying a mirror transformation with respect to x = E/2 results again in a line through the origin: (0, 0) -> (E, 2*E-D). Since E> 2*E-D we can reduce this line, just as we reduced the original line by subtracting D from N . This gives the line (0, 0) -> (D-E, 2*E-D). From the endpoint's y-coordinate we can subtract multiples of 2*(D-E) . Since we can also add once 2*(D-E), the y-coordinate can be reduced to D mod (2*(D-E)) = D mod (2*F).

The conclusion is that we can reduce a figure with N and D to a reduced figure with N’ and D’ as follows. Define E = N mod D, so that: