Dynamics of Tilings. Solutions to Problems 1-10 Notation: #A is the number of elements in the set A. {x} is the fractional part of x. Problem 1a Answer: 15. Consider the possible “boundary cases” of out line that intersects the square. In these cases, the whole square is contained in one of the half-planes determined by the line, and exactly one of its vertices (0; 0) and (1; 1) belongs to the line. y O x Therefore, the sought lines are the ones lying between 6x + 8y = 0 and 6x + 8y = 14. Thus, the corresponding integer values of c are all the integers in the segment [0; 14]. Problem 1b Consider the three possible cases: 1. The line intersects the square at only one vertex. In this case, the intersects the square in a zero length segment. There are two such lines: 6x + 8y = 0 and 6x + 8y = 14. 2. The line meets opposite edges of the square (and probably passes through a vertex). Each of 5 those lines intersects the square in a segment of length . We will now compute the number 4 of such lines. We start shifting the line 6x + 8y = 0 increasing the constant term. Consider the first moment when the line meets opposite edges of the square. At that moment, the line passes through the point (1; 0) and is defined by the equation 6x + 8y = 6. At the last such moment, it passes through the point (0; 1) and is defined by 6x + 8y = 8. So, the sought lines lie between the lines 6x + 8y = 6 and 6x + 8y = 8. Thus, we obtain that there 5 are only three lines intersecting the square in a segment of length . 4 3. The line meets a pair of adjacent edges. Consider the first moment, when the line meets a pair of adjacent edges. At that moment, we have c = 1. This line cuts off a triangle T from the square. Clearly, T is right-angled, and its legs are of the length 61 and 18 , respectively. The length of its hypotenuse equals q 1 + 812 , by the Pythagorean theorem. Thus, the line 6x + 8y = 1 intersects the square in 62 5 the segment of length . 24 Consider the other lines intersecting adjacent edges. Each of them divides the square into a triangle and a pentagon. Note that all the triangles obtained this way are similar to the triangle T , and the similarity ratio is a natural number. Let us compute the largest possible similarity ratio. Consider the first line that meets a pair of opposite edges of the square. The largest triangle is cut off by the previous line, which is defined by 6x + 8y = 5. Thus, we obtain that the lines lying between the lines 5 5 5 5 , , , 6x + 8y = 0 and 6x + 8y = 6 intersect the square in the segments of length 24 12 8 6 25 and , respectively. Each of those values occurs as a length of one other segment that is the 24 intersection of the square with one of the lines lying between 6x + 8y = 8 and 6x + 8y = 14. 5 5 5 5 25 5 , , , , (each of these values occurs twice), 24 12 8 6 24 4 (this value occurs three times). The total number of the pairwise different lengths is 7. Answer. The possible lengths are 0, Important notation. Let F be a set in the plane. The fractional part {F } of F is the set of the points of the form ({x}; {y}), where (x; y) ∈ F . Problem 2a Let the given line ` have an equation ax + by = c. We will determine the answer for all (not necessarily integer) values of c. We will assume that • gcd(a, b) = 1, otherwise one may divide the equation by gcd(a, b). • a ≥ b > 0. The cases a = 0 and b = 0 are left for the reader; the other cases can be obtained via refections in the coordinate axes and swapping of the coordinates. At the end of the solution, we will rewrite the answer for the general case (keeping the only restriction ab 6= 0). Let L = {`}. Then L consists of several half-open intervals in the unit square [0, 1)2 . Let us collect some information about the points of L lying on the x-axis. These c points correspond to the points of ` with integer ordinate. Thus their abscissae have the form a + n − ab , where n is integer. Since ab is an irreducible fraction, there are exactly a points under consideration, and the set of all these points coincides with the set X of points of the form {c} + ka (k ∈ Z) lying a in [0, 1). Similarly, L contains b points on the y -axis. So the total number ofpoints of L lying on the axes is a + b − φ, where φ = 0 if ` does not contain integer points, and φ = 1 otherwise. This number is also the number of intervals in L. However, some of these intervals may be congruent. Let us investigate how often this may happen. The ideas of 1b show that there are only the following two opportunities for that. (i) All the segments connecting two opposite sides of the square are congruent. Since a ≥ b, all these sides are horizontal. The number of such segments equals the number of points of X on the segment 0, 1 − ab , i. e., this number is a − b + φ. (ii) Two segments symmetric to each other with respect to the center of the square. Such pair appears as soon as ` contains a point with half-integer coordinates, as shown in 3e further (the referred solution does not implement the rationality of the line). 2 Therefore, if (ii) does not arise (hence φ = 0), then the total number of tile lengths equals a + b − (a − b − 1) = 2b + 1 if a > b, and 2 if a = b(= 1). If (ii) arises, then the total number of segments which are not mentioned in (i) is (a + b − φ) − (a − b + φ) = 2(b − φ), and these segments split into pairs of congruent segments. All in all, the number of distinct lengths is b − φ + 1, if there is a segment satisfying the conditions of (i), and b − φ otherwise, where the last case appears only if a = b and φ = 0; so the answer in this case is b). Now the answer in the general case can be formulated as follows. Answer. If a line passes through some integer point, and |a| = 6 |b|, then the number of tile min(|a|, |b|) . lengths is gcd(|a|, |b|) If the line contains a half-integer point but does not contain an integer point, and |a| 6= |b|, then min(|a|, |b|) the number of tile lengths is + 1. gcd(|a|, |b|) If the line does not contain a half-integer point, and |a| 6= |b|, then the required number is 2 min(|a|, |b|) + 1. gcd(|a|, |b|) Finally, if |a| = |b|, then the number of the lengths is 2, except for the case when the line contains a half-integer point but not an integer one. In the case, all the tiles are congruent. Remark 1. The condition that the line ax + by = c passes through a half-integer point is equivalent to the condition of 2c being divisible by gcd(a, b). In turn, this is equivalent to the fact that 2c is divisible by gcd(a, b). Remark 2. The answer shown above still holds even for the case ab = 0. Problem 2b We work under the same assumptions as in 2a. We start with presenting some (possibly, nonminimal) period. Notice that the shift by vector (−b,√ a) preserves both the line and the grid. This means that the tiling is also preserved; thus d = a2 + b2 is a period. It remains to learn whether it is minimal (and resolve the situation when it is not). The answer depends again on what happens with the cases appearing in the solution of 2a. It also depends on whether there exist short tiles which are not listed in (i) (i.e. the tiles meeting two adjacent sides of a square at points distinct from its vertices). If there are no short tiles (which happens exactly√when a + b − φ = a − b + φ, that is, b = φ = 1), then the period equals the length a2 + b 2 of the tile, i.e., . a Assume now that short tiles exist. If (ii) does not appear, then each short tile arises once on each length d segment. Thus there cannot be a period less than d. Conversely, if (ii) appears, then each short tile appears twice, which yields that the minimal period can be either d or d/2, and in the latter case each short tile appears once on each length d/2 segment. Since any two such tiles are symmetric with√respect to a semi-integer point, and the semi-integer points occur with some period divisible by a2 + b2 /2, it follows that the period for semi-integer √ points has to be equal to a2 + b2 /2. The latter implies that there exists a unique short tile, that is, we again obtain b = 1. Now, as one can see, the period can be shorter only when a = b = 1, if c is a semi-integer that is not integer. It remains to understand when the latter √is the case. Note that in this case successive semi-integer points lie on the line ` at the distance a2 + b2 /2. If a short segment exists, then such segments lie exactly in the middle of semi-integer points (otherwise the period cannot equal d/2). However, it is not hard to show that another short segment must be adjacent to a short accent. The latter implies that this case is possible only if |a| = |b| = 1, and c is a semi-integer which is not integer. 3 √ Answer. a2 + b 2 , except the following cases: gcd(a, b) √ • If a = b, c does not divide a, while 2c does, then the period is 1/ 2; √ • If a is divisible by b and the line passes through a lattice point, then the period is a2 +b2 a . Problem 2c Let us assume that the side lengths A and B are coprime (the other cases are obtained by scaling). We also assume that B < A. Let us “straighten” the ball trajectory in the following way. At each moment when the ball bounces at some side of the table, we reflect the table (and the ball) in the line containing this side. So the ball trajectory becomes a line y = x in the plane with a grid consisting of A × B rectangles. Next, apply to our plane the following transform. “shrink” eveything horizontally with ratio 1/A, and also vertically with coefficient 1/B (thus each point (x, y) is mapped to (x/A, y/B)). After that, we get the plane with the usual grid of unit squared, and the new line ` has the equation By = Ax. This way, each segment between two successive bounces corresponds to a tile on the line ` situated between the origin and the next integer point on ` (which appears to be (B, A)). There are A + B − 1 tiles on this segment. Each bounce of the ball corresponds to a common endpoint of two such tiles, so there are A + B − 2 bounces. It remains to find the maximal and minimal distances between the bounces. Under our transform, the ratios of lengths of the segments under discussion do not change. Thus it suffices to find the longest and the shortest tile in the tiling of `. The longest tile is, e.g., the leftmost one (when the ball comes from the corner to the opposite side). The shortest distance is min(A, B) times smaller. So, in the eneral case we get the following answer. A+B − 2. The longest distance between two successive Answer. The number of bounces is gcd(A, B) √ √ bounces is 2 · min(A, B), the shortest one is 2 · gcd(A, B). The solution for Problem 3 is presented after that for Problem 4. Problem 4a We will show that for a given ε > 0, there exists a pair of terms of the sequence which are at a distance less than ε from each other. Let the sequence (xn ) be bounded below and above by b−a some numbers a and b, respectively. Choose n ∈ N such that < ε. Divide the interval into n n equal parts. By the Pigeonhole Principle, at least two of the terms x1 , x2 , . . . , xn+1 belong to b−a the same part. Thus, the distance between them does not exceed < ε. n Problem 4b If {kλ} = {mλ} for some k 6= m, then the number (m − k)λ is integer, hence λ is rational, which cannot be the case. Therefore, the terms in the sequence do not repeat. Consider an arbitrary interval [α; β] ⊆ [0; 1]. We will prove that it contains a number of the form {kλ}. To do this, using Problem 4a we find the terms {kλ} and {mλ} (for some k > m) that are at a distance less than β − α; denote their difference µ = {kλ} − {mλ}; then, we have |µ| < β − α. Note that the sequence contains a subsequence of numbers of the form 4 {nµ} = {n(k − m)λ}. The first [1/µ] terms of this new sequence divide the interval [0; 1] into subintervals of length less than |µ| < β − α each. Therefore, the whole interval [α; β] cannot be contained in any of those subintervals. Hence, the interval [α; β] contains a separating point of the form {nµ} = {n(k − m)λ}. Problem 4c A winding of a square by a line ax + by = c is defined to be the fractional part of the line ax + by = c (see the notation introduced before 2a). Without loss of generality, assume that ab < 0. Take an arbitrary interval I that is not parallel to the line `. Project I along ` onto the positive rays of the coordinate axes; the projection is either a segment or a union of two segments. For definiteness, we may assume that the projection contains a segment J of the x-axis. It suffices to show that this segment contains a point of the winding (then, the winding segment passing through this point meets I ). The points of the winding that belong to the x-axis are exactly the points of the form ac + n − ab }. Since ab is irrational, Dirichlet’s lemma implies that one of those points belongs to J . QED Problem 3 By a tile of the winding we mean the fractional part of a tile on the line. Problem 3a Answer. Yes. For example, we can take a line that passes through an integer point A. Then the two tiles containing A are symmetric with respect to this point (moreover, any two tiles symmetric with respect to A have equal lengths). See also the next problem. Problem 3b Answer. There always is an infinite amount of tilings of equal length. k 1−k Let k be the slope of our line; without lose of generality we have 0 < k < 1. Consider the winding of [0, 1]2 with our line. According to 4c, there are infinitely many tiles of the winding that pass through the points of the form (0, y), where 0 < y < 1 − k (because there are infinitely many segments with empty pairwise intersections that lie inside (0, k)). The other endpoints of these tiles have the form (1, y + k). Corresponding tiles with such endpoints have equal lengths. Problem 3c Answer. There cannot be exactly three tiles of equal length. Assume the contrary: there are exactly three tiles of length d. How can they be placed in the winding of the line? There are two cases. (i) The endpoint of one of these tiles lie on opposite sides of the square. It has been shown in 3b that there are infinitely many tiles of this length. This is a contradiction. (ii) Each of the three tiles has endpoints on adjacent sides of the square. There are exactly two length d sections of the square by a line parallel to our one; these sections are symmetrical 5 to each other with respect to the center of the square. Therefore, at least two of our three tiles of the winding coincide. But this is impossible for an irrational line. Problem 3d Answer. There are always infinitely many tiles of pairwise different lengths. Assume again that the slope k of our line lies in (0, 1). Then, according to 4c, there are infinitely many tiles of the winding with endpoints on the lower side of the unit square. All these tiles have pairwise different lengths. Problem 3e Answer. There exist exactly two tiles of equal lengths if and only if the line contains a half-integer point (i.e. a point such that its coordinates are integers divided by 2). Suppose that the line ` passes through a half-integer point (u/2, v/2). If a point (x, y) belongs to `, then the point (u−x, v −y) also lies on `. Therefore, for any tile of the winding of [0, 1]2 with `, the segment symmetric to it with respect to the center of the square also lies in the winding with our line (we assume here that the tiles of the winding do not contain their endpoints, i. e. they lie in (0, 1)2 ). So, if the winding contains a tile of length d connecting adjacent sides of the square, then the winding (an hence the line) contains exactly two such tiles. Conversely, assume that there are exactly two tiles of length d. Due to the solution for 3c, there are infinitely many tiles which connect opposite sides of the unit square, and all of them are of the same length. So, each of the two tiles connects adjacent sides of the square. These tiles of the winding must be symmetric around the center of the square [0, 1]2 . This implies that for some x, y ∈ [0, 1) our line contains points (k1 +x, `1 +y) and (k2 −x, `2 −y), where ki , `i ∈ Z. Therefore, the midpoint of the segment connecting these points also belongs to our line. It remains to notice 2 2 and `1 +` . that this midpoint has half-integer coordinates k1 +k 2 2 Problem 5 Observe that in any open interval containing a there is a subinterval of form Oε (a) = (a − ε, a + ε) for some ε > 0. Therefore, we can consider only such intervals. We call such interval a εneighborhood of a. Problem 5a Fix ε > 0. Choose a positive N greater than 1ε (for instance, we can take N = 1ε + 1). 1 integer For all n > N we have n − 0 < N1 < ε. This implies that all terms of the sequence, except possibly the first N terms, are contained in Oε (0) = (−ε, ε). Problem 5b Suppose that the sequence an converges to some a. Take ε = 21 . For all n we have |an −an+1 | = 2. This yields that no two consecutive terms of the sequence may belong to an interval of length 1. Thus there are infinitely many terms of our sequence outside of O1/2 (a), which is a contradiction. Problem 5c Take any ε > 0. By definition, there exists a number N such that for all n > N the numbers an and bn belong to ε/2-neighborhoods of a and b, respectively. In other words, |an − a| < ε/2 and |bn − b| < ε/2. Therefore, |cn − (a + b)| ≤ |an − a| + |bn − b| < ε/2 + ε/2 = ε. So, for the same values of n the number cn lies in Oε (a + b). Problem 5d Take any ε > 0. By definition, there exists a number N such that for all n > N the numbers an and bn lie in Oε (a), i.e., a − ε < an ≤ cn ≤ bn < a + ε. Thus, for the same values of n the number cn also lies in Oε (a). 6 Problem 6 First of all, we perform the same modifications as in 2c: we “straighten” the trajectory of the ball into a line and “shrink” the whole plane by A1 horizontally and by B1 vertically. Now we have a plane split into unit squares and a line ` determined by the equation Ax = By . The line ` is irrational, so the only integer point lying on it is (0, 0). The ball moves along ` with velocity 1 1 √1 , . 2 A B Problem 6a Notice that limn→∞ [an] = a by the squeeze lemma (since a − n1 = an−1 ≤ [an] ≤ an = a). n n n n The bounce moments correspond to the moments whenthe ball moving along the line meets the T T √ √ grid lines. During the first T minutes, this ball meets A 2 vertical and B 2 horizontal grid lines. Consequently, the average number of bounces is T 1 1 1 T T T 1 1 √ + √ √ + lim √ = √ + √ . = lim lim T →∞ T →∞ T →∞ T T A 2 T B 2 A 2 B 2 A 2 B 2 Problem 6b We will assume that A < B , the other case being similar. After straightening the trajectory, the doublets correspond to the situations when ` intersects two opposite sides of some unit grid square. Since the slope of ` is less than 1, the line cannot intersect successively two horizontal segments of the grid. Choose some T . As we have already mentioned, just before each of BT√2 “horizontal” meetings there is a “vertical” one. After each of the remaining D = AT√2 − BT√2 “vertical” meetings there is another “vertical” meeting (if the former is not the last one). So, the amount of doublets occurred in T minutes is no bigger than D and no smaller than D − 1, i.e. it lies between T T √ − √ −2 A 2 B 2 T T √ − √ + 1. A 2 B 2 √ 1 1 √ By the squeeze lemma, the frequency of doublets is B 2 − A 2 (this formula works in the case A > B as well). and Remark. One can also solve this problem using Weyl’s theorem. Take a look at problem 8 for similar solutions. Problem 7a Recall that the ceiling dxe of a real number x is the smallest integer greater than or equal to x. Take a positive irrational number λ < 21 . Now we pick terms of our sequence {a + nλ} until they “pass around” the segment [0, 1], i.e. until nλ exceeds 1. The number N of terms we have taken this way is equal to d1/λe, i.e. λ is between N1 and N1−1 . Now we will prove that if we take λ small enough (and N , therefore, is going to be big), then the statement of the problem holds true. Let S be the set of first N terms of our sequence and let k be the number of elements of S which lie in I . The frequency of hits, which is Nk , can be estimated in terms of λ: since N1 < λ < N1−1 , we have (k − 1)λ < Nk−1 6 Nk < kλ. −1 Moreover, the length |I| can also be estimated in terms of λ. The set S determents a partition of segment [0,1] (elements of S are endpoints of segments of the partition). Each segment of the partition is no longer than λ, and k + 1 of these segments cover the segment I . Therefore, |I| < (k + 1)λ. No more than three segments of the partition could be shorter than λ: namely, the 7 two boardering segments and the one that starts at {a + N λ}. These observations imply that I contains at least k −2 segments of length λ, so |I|¿(k −2)λ. To sum up, (k −2)λ < |I| < (k +1)λ. Comparing the estimates we have made for the frequency Nk and for the length |I|, we conclude that they differ by no more than 2λ. Finally, if we choose λ < ε/2 and N =d1/λe, then the problem requirements are satisfied. To solve problems 7b–7d, we will use the following lemma, which can be proved by a direct computation. Lemma 1. Let A be the frequency of hits of a sequence a1 , . . . , ak in a segment I , let B be the frequency of hits of a sequence b1 , . . . , bm in the same segment, and let C be the frequency of hits of the sequence a1 , . . . , ak , b1 , . . . , bm in the same segment. Then C is equal to the weighted kA + mB avarage . k+m Corollary 1. Let A be as defined in Lemma 1. Assume that it differs from the length |I| by less than ε, and that B differs from |I| by less than δ . Then C differs from |I| by less than the kε + mδ of these errors. weighted avarage k+m Remark 1. If we know that the first error ε is very small (say, 0.001), and the weight m of the second error is significantly smaller than the weight k of the first one (say, 1000 times), then the is also very small, even if the second error δ is not very small (for weighted avarage error kε+mδ k+m δ < 1 the weighted avarage is less than 0.002). Problem 7b In problem a we saw that if we take N and λ such that N1 < λ < N1−1 , then the frequency of hits of the sequence {a + λ}, {a + 2λ}, {a + 3λ}, . . . , {a + N λ} in the segment I differs from the length |I| by less then 2λ. Let us show that a similar estimate can be made for the frequency of hits of the sequence {a + λ}, {a + 2λ}, {a + 3λ}, . . . , {a + M λ} in I when M is large enough. Divide this sequence into subsequences of length N and a “remainder” of length r < N : {a + λ}, {a + 2λ}, {a + 3λ}, . . . , {a + N λ} {a + (N + 1)λ}, {a + (N + 2)λ}, {a + (N + 3)λ}, . . . , {a + 2N λ} ......... {a + (pN + 1)λ}, {a + 2λ}, {a + 3λ}, . . . , {a + (pN + r)λ} In fact, we divide M by N with remainder: M = pN + r . According to problem a, the frequency of hits of each of the first p subsequences in I differs from the length of the segment by less than 2λ. The frequency of hits of the“remainder” cannot be estimated better than that it is between 0 and 1, so it differs from |I| by less than 1. Therefore, we can apply Corollary 1 to get that |I| differs from the frequency of hits of {a + λ}, {a + 2λ}, {a + N p · 2λ + rδ 1 3λ}, . . . , {a + M λ} in the segment by less than , which is less than 2λ + λM . For Np + r big enough M (greater than 1/λ2 ) this number is less that 3λ. So to conclude, for all big M (greater than 1/λ2 ), the difference between |I| and the frequency of hits of {a + λ}, {a + 2λ}, {a + 3λ}, . . . , {a + M λ} is less than 3λ. In particular, if we take λ < ε/3, then for all M > 1/λ2 the freqeuncy of hits is different from the length of the segment by less than ε. Problem 7c 8 Applying the Dirichlet Lemma to the segment [0, δ] and the sequence {nλ}, we find some q such that {qλ} < δ . Set µ={qλ}. Observe that the Weyl progression {a}, {a + λ}, {a + 2λ}, . . . splits into alternating Weyl progressions with difference µ and first terms a, a+λ, a+2λ, . . . , a+(q−1)λ. Indeed, we just divide n by q with remainder: n = mq + r , so {a + nλ} = {(a + rλ) + mµ}. Problem 7d Pick some number δ > 0. According to problem c, we can (and will) split our Weyl progression {a}, {a + λ}, {a + 2λ}, . . . into q progressions with difference µ < δ . Let P1 , P2 , . . . , Pq denote these progressions, and let P denote the initial progression. According to problem b, if we choose more than 1/µ2 first terms of Pi , then their frequency of hits in I differs from |I| by less than 3µ. According to Corollary 1, if we pick more than q/µ2 + q first terms of P , than their frequency of hits in I also differs from |I| by less then 3µ, since this set of > q/µ2 + q first terms of P splits into sets of > 1/µ2 first terms of P1 , . . . , Pq . We now need to take a value of δ such that 3µ is greater than ε. To achieve it, we can take δ = ε/3. Then for more than q/µ2 first terms of progression P the frequency of hits in I differs from the length |I| by less than 3µ < 3δ < ε. Problem 8 Let A and B be plane figures. Recall that A ∪ B and A ∩ B stand for the union and the intersection of A and B , respectively. Problem 8a Consider an irrational line ` defined by ax + by = c. For every T > 0, by ST we denote the length T segment of ` with left endpoint at (0, cb ). Let I ⊂ [0, 1]2 be a segment that is not parallel to `. Definition. The frequency of intersections of the segment I with the winding of [0, 1]2 corresponding to the line ` is the limit #({ST } ∩ I) lim . T →∞ T Problem 8bc Assume first that the segment I is contained in the segment [0, 1] of the y -axis. Then, the intersection points of the winding and the segment [0, 1] of the y -axis generate the Weyl’s sequence c a un = b + n − b . By definition, what we have to compute is the frequency of its elements that are contained in I . Warning!!! Before using Weyl’s theorem (see Problem 7), note that while we √ travel with unit a2 + b 2 minutes speed along the line ax + by = c, we meet a vertical line of the grid every |b| (nothing but the length of a line segment between two neighboring vertical lines of the grid). √ 2 a + b2 Therefore, it takes minutes to obtain each new element of the sequence (un ). |b| Thus, Weyl’s theorem and the observation above together imply that the sought frequency of |I||b| intersections for I equals √ . A similar argument works for I contained in the segment a2 + b 2 |I||a| [0, 1] of the x-axis and yields the answer √ . a2 + b 2 Now, let I be an arbitrary segment in [0, 1]2 . If ab < 0, then project I along ` onto the lower left angle of the square. Otherwise, project I onto the upper left angle. This projection in general is a union of a vertical segment IV and a horizontal segment IH contained in the corresponding edges of the square. One can easily show that the following statement is true: 9 Let τ be a tile such that {τ } 63 (0, 0). Then, the fractional part {τ } meets I if and only if it meets exactly one of the segments IV and IH . Note that for each value of T , a length T segment of the line ax + by = c contains no more than one tile such that {τ } 3 (0, 0). Therefore, for every T > 0 we have: 0 6 #({ST } ∩ IV ) + #({ST } ∩ IH ) − #({ST } ∩ (IV ∪ IH )) 6 1. Let us consider the largest T0 < T such that the right endpoint of ST0 is contained in a vertical or a horizontal line of the grid. It is obvious that 0 6 #({ST0 } ∩ (IV ∪ IH )) − #({ST } ∩ I) 6 1. Thus, as T approaches infinity, we have #({ST } ∩ I) − #({ST0 } ∩ IV ) − #({ST0 } ∩ IH ) → 0. T |IH ||a| + |IV ||b| √ . a2 + b 2 A straightforward computation implies that, for an arbitrary vertical/horizontal segment I ⊂ [0, 1]2 , the frequency of intersections is the same as for its copy contained in the corresponding |I||b| edge of the square, which yields the answer to Problem 8b. That is, √ for I being vertical a2 + b 2 |I||a| for I being horizontal. and √ a2 + b 2 Hence, the answer to Problem 8c is Problem 9a This problem is a special case of Problem 8c. Indeed, choose I to be the diagonal of the square [0, 1]2 that intersects all the fractional parts of the tiles contained in the line ax+by = 0. Then, for each tile τ contained in the line segment of length T , its fractional part {τ } meets I . Therefore, since, for every T > 0 the difference between the number of points in {S(T )} ∩ I and the number of tiles on S(T ) does not exceed 1, the sought limit coincides with the frequency of intersections of the winding with the interval I , and we can use Problem 8c to compute it. Thus, the sought |a| + |b| , since in this case |IV | = |IH | = 1. density equals √ a2 + b 2 Problem 9b Note that the numerator in the formula for the tile density coincides with the denominator in the formula for the average length√of tiles. Moreover, the difference between the numerator in the latter and T does not exceed 2, which is the greatest possible length of a tile. Obviously, as T approaches infinity, so√does the number N (T ) of tiles on a line segment of length T , so, we have the equality limT →∞ N (T2 ) = 0. Thus, the sought limit is the multiplicative inverse of the limit in √ a2 + b 2 Problem 9a, hence the answer is . |a| + |b| Problem 9c This problem is yet another special case of Problem 8c with I being the diagonal different from the one considered in Problem 9a. Indeed, this diagonal is also a diagonal of the parallelogram P ⊂ [0, 1]2 containing the fractional parts of the maximum length tiles. This observation implies that, for a tile τ , its fractional part {τ } meets I if and only if τ is of the maximum length. b Hence, to obtain the answer, it remains to use Problem 8c: if > 1, then the projection of I a |b| − |a| along the line ax + by = 0 is a vertical segment of length . Hence, by Problem 8c, the |b| 10 b |b| − |a| sought frequency equals √ . The case with < 1 can be considered analogically: the a a2 + b 2 |a| − |b| projection of I along the line is a horizontal segment of length , thus, by Problem 8c, the |a| |b| − |a| |a| − |b| frequency of intersections is equal to √ . So, the total answer is √ . a2 + b 2 a2 + b 2 Problem 10a A plane α in the 3-dimensional space is divided into pieces (tiles) by the faces of the standard 3-dimensional grid. This yields a tiling of α. Problem 10b Since a cube contains only 6 facets, a tile can have no more than 6 sides (thus, no more than 6 angles). As an example, take the cross section of the cube [0, 1]3 by the plane x + y + z = 32 . Problem 10c The argument is similar to the one for Problem 2a and yields the following answer. Suppose that |A| + |B| + |C| we have |A| 6 |B| 6 |C|. If |A|+|B| > |C|, then the sought number is equal to . 2 Otherwise, it equals |A| + |B|. Problem 10d Obviously, the origin O belongs to any plane α defined by an equation of the form Ax+By+Cz = 0. If α contains no other lattice points, then the first statement is the case. Otherwise, take P = (p1 , p2 , p3 ) ∈ α – an arbitrary lattice point such that P 6= O and consider −→ the line ` spanned by the vector OP . Each of the points in ` is of the form λP = (λp1 , λp2 , λp3 ) for some λ ∈ R. For any λ ∈ R we have: Aλp1 + Bλp2 + Cλp3 = λ(Ap1 + Bp2 + Cp3 ) = 0. Hence, ` is contained in α. Take d = gcd(p1 , p2 , p3 ) and consider the lattice point P0 = d1 P . We shall prove that, for any lattice point Q ∈ `, we have Q = kP0 for some k ∈ Z . Take an arbitrary lattice point Q ∈ `. Then, we have Q = λP0 , where λ ∈ Q. Represent λ k and assume that m 6= 1. On the other hand, it easily follows as an irreducible fraction λ = m that the coordinates of P0 are all divisible by m, while, by definition of P0 , their gcd equals 1. Thus, we have m = 1. Therefore, if the plane α contains no other lattice points, then, the second statement is the case. Otherwise, let N = (n1 , n2 , n3 ) ∈ α be a lattice point that is not contained in `. Substituting the coordinates of N and P into the equation Ax + By + Cz = 0, we obtain a linear system of two equations in the variables A, B, C with integer coefficients. Let p1 = λn1 , λ ∈ Q, then, consider the point P − λN = (0, p2 − λn2 , p3 − λn3 ) ∈ α with at least one nonzero coordinate. Substituting it into the equation Ax + By + Cz = 0, we obtain that B = µC for some rational µ. Thus, from the equation Ap1 + µCp2 + Cp3 = 0, we get A = νC for some ν ∈ Q. Thus, the system has a rational solution, hence, the third condition is the case. 11

© Copyright 2021 Paperzz