ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 14 (2018) 359-373 https://doi.org/10.26493/1855-3974.982.6d6 (Also available at http://amc-journal.eu) Congruent triangles in arrangements of lines Carol T. Zamfirescu * Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium Received 27 November 2015, accepted 18 July 2017, published online 30 September 2017 We study the maximum number of congruent triangles in finite arrangements of i lines in the Euclidean plane. Denote this number by f (i). We show that f (5) = 5 and that the construction realizing this maximum is unique, f (6) = 8, and f (7) = 14. We also discuss for which integers c there exist arrangements on i lines with exactly c congruent triangles. In parallel, we treat the case when the triangles are faces of the plane graph associated to the arrangement (i.e. the interior of the triangle has empty intersection with every line in the arrangement). Lastly, we formulate four conjectures. Keywords: Arrangement, congruent triangles. Math. Subj. Class.: 52C10, 52C30 1 Introduction A problem from mathematical folklore asks for bounding four congruent triangles with six matchsticks. This is easily done, and left to the reader. Quite naturally, one can ask whether more congruent triangles may be formed by using the same six matchsticks. It seems that this particular problem has not been treated in the literature. Our main focus lies on constructing planar arrangements in which a fixed number i of lines bound as many congruent triangles as possible. For an excellent overview on arrangements and spreads, see Griinbaum's [11]. The results presented in this article are complementary to work of Erdos and Purdy [4, 5] on sets of n points—see also [6]. In this paper, everything happens in R2. An arrangement (of lines) A shall be a finite family of i lines Li,..., L. In the following, we will ignore the case when there exists a point common to all lines, and thus assume that i > 3. Denote by A the set of all arrangements of i lines. * My research is supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). I thank Benjamin Grothe, Iulia Mihai, and Tudor Zamfirescu for their helpful suggestions. Finally, I am grateful to the anonymous referees, who have dramatically improved the quality of this manuscript with their helpful comments. E-mail address: czamfirescu@gmail.com (Carol T. Zamfirescu) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 359 Ars Math. Contemp. 14 (2018) 267-284 We associate to A G A£ a graph T^: the vertices of correspond to the intersection points of lines from A and the edges of correspond to the line-segments between these vertices. is a plane graph. The vertices, edges, and faces of are also said to belong to A. A triangle in A G A£ shall be the convex hull of the set of intersection points of three non-concurrent pairwise non-parallel lines in A. Denote by FA the set of all triangles in A. Whenever Ai, A2 G FA are congruent we write Ai ~ A2. Let Ff4,..., Fp4 be the equivalence classes with respect to ~ such that | F-^ | > ... > |Fp41. Here, |M| denotes the cardinal number of M. We call a triangle A g Fa facial if it is a face of rf, i.e. L n int A = 0 for all L G A. Let GA c FA be the set of all facial triangles in A, and, as before, let Gf,..., Gf be the equivalence classes with respect to ~ such that |GA| > ... > |GA|.Put f(¿) = max |F1A| and o(^) = max |Gf| . v ' AeaJ 1 1 yw AeaJ 1 1 We shall also be considering restrictions relative to a certain arrangement A G A£, namely, for k < fA(k) = max |F1b| and g^(k) = max |Gf| . w BcA, Be aj 11 w BcA, Be aj 11 We call an arrangement A G A£ f -optimal (g-optimal) if |Ff| = f (¿) (|GA | = g(^)). If A is both f -optimal and g-optimal, we simply write optimal. A triangle from FA or GA is said to be good. Note that FA and GA need not be unique. In that case, one makes a choice clearly defining FA and GA. The edges and angles of a good triangle will be called good, too. An arrangement is simple if no three lines are concurrent. The lines of an arrangement are in general position if no two lines are parallel and no three lines are concurrent. Two arrangements A and B are combinatorially equivalent if their associated graphs Ta and rB are isomorphic. (Note that, as mentioned above, we do not consider line arrangements in which all lines meet in a single point.) A G A£ is c-unique if there exists no B G A£ such that A and B are (a) not combinatorially equivalent and (b) |Hf| = |#B |, where H is F or G. In the same vein, we say that two arrangements A G A£ and B g A£ are g-equivalent if A can be obtained from B by translation, rotation, reflection, and scaling. A G Ai is g-unique if there exists no B G A£ such that A and B are (a) not g-equivalent and (b) |Hf| = |Hb |, where H is F or G. A few examples: Three lines in general position yield an arrangement that is c-unique, but not g-unique; any arrangement on four lines that forms exactly two congruent triangles is not c-unique (and thus cannot be g-unique); finally, as we shall see in Theorem 3.5, the f-optimal arrangement from Figure 2 (b) is g-unique (and thus c-unique). F(¿) (G(^)) is defined as the set of all integers u such that there exists an arrangement on I lines having exactly u congruent triangles (congruent facial triangles). We write [s..t] for the set of all integers u with s < u < t, put H for F or G, and h = |f if H = F, g if H = G. Whenever H(¿) = [0..h(^)], we say that H(¿) is complete. In the following, we will tacitly use the fact that G(^) c F (¿). We call an arrangement A G A £ 1-extendable if there exists a line L such that |HfUL| = |Hf| + 1. C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 2 Preparation We briefly concern ourselves with the following question, since it will shorten later arguments. What if we drop the condition that the triangles need to be congruent? Kobon Fu-jimura asked in 1978 in his book "The Tokyo Puzzle" [8]—see also [10, pp. 170-171 and 178]—what the maximum number K(i) of facial (not necessarily congruent!) triangles realisable by i lines in the plane is. (Griinbaum treated this problem before Fujimura, but he might have only been interested in arrangements in the projective plane [6].) Recently, Bader and Clement [1], improving upon a result of Tamura, showed the following. Lemma 2.1 (Bader and Clement). where I denotes the indicator function. Many arrangements have been constructed in order to find solutions to Fujimura's problem. Fujimura himself gave an example which shows that K(7) > 11, although it was thought for many years that K(7) = 10. In 1996, Grabarchuk and Kabanovitch [13] gave two 10-line, 25-triangle constructions, whereas Lemma 2.1 gives K(10) < 26. Whether K(10) is 25 or 26 is unknown. Other 10-line, 25-triangle arrangements were found independently by Grunbaum [12, p. 400], Wajnberg, and Honma (see [15] for more details). Good overviews of the best (i.e. the greatest number of triangles for a fixed number of lines) known arrangements can be found in [14] and [15]. Bader-Clement bound 1 2 5 7 11 15 21 26 33 39 Best known arrangement 1 2 5 7 11 15 21 25 32 38 Furedi and Palasti [9] construct an arrangement proving K(i) > i(i - 3)/3. See also the article of Forge and Ramirez Alfonsin [7]. We continue with a series of lemmas. Lemma 2.2 is stated without its straightforward proof, but we present the heptagonal case in Figure 1 and its caption. Lemma 2.2. The i lines bounding a regular i-gon determine exactly 2i congruent triangles if i > 7, and therefore 2i e F (i) and f (i) > 2i. With the same construction we obtain for i > 5 that i e G(i) and g(i) > i. Lemma 2.3. Let A e A and h e {f, g}. Then, for 3 < k < i — 1, t(t — 2) K(t) < -3- — :(£ mod 6)e{0,2}}(^)1 Table 1: Bounding K(t) for t < 12. 3 4 5 6 7 8 9 10 11 12 Mt) < t(t — 1)(t — 2) k(k — 1)(k — 2) ■ Mk). Proof. We observe that every subset of k < t lines within the arrangement A cannot have more than hA(k) good triangles (good in A). Counting all together, there are at most 155 Ars Math. Contemp. 14 (2018) 267-284 Ck) good triangles, each appearing several times. Since each of them lies in (l_33) sub-arrangements of k lines, we obtain hA(0 * ^ U-3/ Thus, for each k we obtain an upper bound for Ha(î). □ Figure 1: Seven lines bounding a regular heptagon. This arrangement contains fourteen congruent triangles: abe, acd, and their symmetric counterparts obtained by rotating around the barycentre of the heptagon by 2nk/7 for k = 1,..., 6. This arrangement proves that f(7) > 14. Lemma 2.4 is a direct consequence of Lemma 2.3. Lemma 2.4. Let h G {f, g}. Then h(£) < min e(f - 1)(/ - 2 • h(k). V ' < 3 h(£) + h(k). Proof. We scale B to B' such that the good triangles of B' are congruent with the good triangles of A. Consider the convex hull Ca (Cb> ) of the intersection points of A (B'). Let PA (Pb> ) be an intersection point of A (B') lying on the boundary of the convex polygon Ca (CB>) and incident with a good angle a a (aB>) of A (B') such that a a = aB>. Denote with ¿A and ¿A (LB and LB ) two of the lines of A (B') intersecting at pa (pB>) and forming the angle a a (aB>). We can now identify ¿A with LB and with LB such that an arrangement C is obtained in which, seeing A and B' as sub-arrangements of C, no good triangle lies in both A and B'. (Note that the number of good triangles in C may be larger C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 than the sum of the number of good triangles in A and B', see e.g. Figure 8, in which the arrangements from Figures 1 and 5 (b) are joined: the original arrangements have 14 and 8 good triangles, respectively, but the new arrangement has 26.) □ We write /(¿) if we consider the values of / (¿) only for arrangements whose good triangles are not right triangles. Proposition 3.2. /(^ +1) < /(¿) + 3^ - 1) and /(^ +1) < /(¿) + 4^ - 1). Proof. Let L be a line being added to A G A^ .If A has the property that |FA| = |F2a|, then consider henceforth only the triangles in Ff4, as well as their edges, to be good. We denote the lengths of good edges with a, b, and c. There are at most ¿ - 1 triangles with an edge of length a on L: there are at most ¿/2 lines of one of the two lines needed to make a good triangle with an edge on L, each of these lines is part of at most two triangles with an edge of length a on L, and it is impossible for there to be exactly ¿/2 of them each of which is part of exactly two triangles. Since this can be applied analogously for edges of length b and c, we have / ^ +1) = / (¿) + 3^ -1). For good triangles that are right triangles, we argue in the same manner and obtain that for each of the three types of good edge (i.e. of length a, b or c) there are at most 4^ -1)/3 triangles with a good edge of that type on L. □ Proposition 3.3. /(¿) < ¿^ - 1) and /(¿) < 4¿(¿ - 1)/3. Proof. The idea is the same as the one used in the proof of Proposition 3.2. In the case of non-right triangles, we have established that on each line in A there are at most 3^ - 1) good edges. By multiplying this with ¿, we obtain an upper bound for the number of good edges in A. Now we divide by three (as there are three edges to each triangle) and have the desired bound. The case of right triangles is settled analogously. □ All angles in A G A^ equal to one of the angles of a good triangle which is not a right triangle will be called non-right angles. Proposition 3.4. / (¿) < 2¿(¿ - 2)/3 for simple arrangements. Proof. Consider a simple arrangement A on ¿ lines admitting a good triangle which is not a right triangle. Let V(r^) = V, and write Vk for the set of vertices of degree k. As no three lines are concurrent, in there exist only vertices of degree 2, 3, or 4. Trivially, around a vertex of degree 2 at most one non-right angle resides. Around a vertex of degree 3 likewise (as n/2 is a right angle, and the sum of two non-right angles must be strictly smaller than n), and around a vertex of degree 4 there may be at most two non-right angles. Thus, in A, we have as an upper bound for the maximum number of non-right angles |V2| + |V3| + 2 • |V41 = |V| +1V41. We have |V| < ¿^-1)/2. Also |V4| < |V|-¿, because on every line the first and the last vertex belong to V2 U V3, but any such vertex may appear as first or last vertex on two lines of A. Thus, the bound is ¿2 - 2¿. For odd ¿ > 5, this bound is best possible: for the ¿ lines bounding a regular ¿-gon we have | V21 = ¿, | V31 = 0, and | V41 = ¿^ - 3)/2. One non-right angle cannot lie in more than two triangles which are not right triangles, and every triangle requires three angles, whence, the final bound. (In fact, no good angle can lie in more than two good triangles.) □ 157 Ars Math. Contemp. 14 (2018) 267-284 3.2 I < 5 We have f (3) = g(3) = 1 and f (4) = g(4) = 2, and F(3), G(3), F(4), and G(4) are complete. We leave the easy proofs to the reader, but mention that in the 4-line case there exist exactly three combinatorially different solutions with two congruent triangles (these coincide for the g-optimal and the f-optimal case): one with three concurrent lines, one with two parallel lines, and one in general position. We now focus on the first interesting case: I = 5. Figure 2: (a) shows a 5-line arrangement with four congruent triangles constructed as follows. Two lines L1, L2 orthogonal to a third line L3 are considered. Let the intersection points be p1 and p2, resp. A fourth and fifth line are considered such that their intersection point is the midpoint of the line-segment p1p2 and the angle each forms with L3 is n/4. (b) depicts the five lines bounding a regular pentagon. This arrangement contains ten triangles, distributed among two congruence classes of size 5 each. Theorem 3.5. (i) We have f (5) = g(5) = 5 while F(5) and G(5) are complete. Furthermore, the arrangement from Figure 2 (b) is (ii) optimal, and (iii) g-unique among f -optimal and g-optimal 5-line arrangements. Proof. Figure 2 (b) shows that g(5) > 5 (whence, f (5) > 5), with which Lemma 2.1 implies g(5) = 5. f (5) = 5 follows from Lemma 2.4 (with k = 4). We now discuss G(5). We have G(4) = [0..2] c G(5). Consider the four lines bounding a square and add the two lines containing the square's diagonals. By removing one of the four original lines, we have shown that 3 G G(5). Together with the arrangements from Figure 2, we have that G(5) is complete since g(5) = 5. Thus, (i) is proven. (ii) follows directly from (i). We now prove (iii). First, we show that the arrangement from Figure 2 (b) is c-unique. We use the database provided in Christ's Dissertation [3, Chapter 3.2.5]. (A visualisation of Christ's results is available in [2]. Note that this does not coincide with Griinbaum's isomorphism types of arrangements given in [11, p. 5], since Grunbaum discusses the issue in the projective plane, while here we treat the situation in the Euclidean plane.) Among arrangements of five lines in general position, there are exactly six combinatorially different ones, shown in Figure 3. The arrangement in Figure 2 (b) belongs to the combinatorial class (A). Only the arrangements in (A) contain five facial triangles, i.e. triangles which are faces in the associated graph. We leave to the reader the straightforward proof that among arrangements with five lines not in general position (i.e. containing two parallel lines or three C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 concurrent lines), there is none featuring five facial triangles. Note that the occurrence of more triangles is impossible due to Lemma 2.1. We now turn to the case in which triangles are not facial. Let us denote a line-segment between two points x, y with xy and its length with L(xy). We will use the following. Remark. The sum of the measures a and ft of two good angles is n if and only if a = ft = n/2. We write Aijk for the triangle with vertices pi, pj, pk. We will tacitly make use of the fact that if in a given arrangement a triangle A is strictly contained in a triangle A', then A ^ A' and so A and A' cannot lie in the same congruence class. (B) We have A012 C A149 n Am (so A149 ^ A012 ^ A136), A345 c A149 n A248, A569 c A136 n A237 n A578, A578 c A237, A067 c A237, A089 c A248 n A237 n A067. Due to these inclusion relations, only the following set of triangles may form a congruence class of size 5: {A149, A136, A248, A578, A067}. Assume it is indeed a congruence class. Thus, all angles around p6 are right. We apply the Remark to the angles surrounding p6. Combining this with A136 ~ A067 and p0p6 c p1p6, we have L(p6p7) = L(p1p6), L(p0p6) = L(p3p6), and L(p0p7) = L(p1p3). p^ is the hypothenuse in Am, but as p1p4 is an edge of A149 and A149 ~ A136 we obtain a contradiction, since L(p1p4) > L(p1p3). (C) We have A012 c A134 n A268 n A378, A134 U A239 c A378, A457 U A056 c A158, A049 c A158 n A239 n A378 n A056, A679 c A158 n A268 n A457. There is no congruence class of size 5. 159 Ars Math. Contemp. 14 (2018) 267-284 (D) We have A012 C A149 c A156, A234 C A039 c A378, A457 U A068 C A258, A679 C A258 n A457 n A068. Once more, all congruence classes have size at most 4. (E) We have A129 C A138 C A145, A237 C A246, A034 C A058 C Aoe7, A789 C A237 n A246 n A569. As above. (F) We have A012 C A139 C A145, A238 U A056 C A246, A678 C A579 C A347, A089 C A238 n A246 n A056. As above. Let us show that in a 5-line arrangement A containing two parallel lines or three concurrent lines, no more than four congruent triangles can be achieved. We first assume that A contains parallel lines L1, L2. If there exists a line L3 parallel to L1, we are done, as in A there are only at most three triples of lines forming triangles. Thus, w.l.o.g. we are in the situation that a third line, L3, intersects L1 and L2. Now assume that a fourth line, L4, is parallel to L3. Note that L1, L2, L3, L4 bound zero triangles. In this situation, a fifth line generates at most four new triangles. Thus, L4 cannot be parallel to L3. We have proven that a 5-line arrangement containing three parallel lines or two parallel pairs of parallel lines cannot have more than four congruent triangles. Denote the open strip bounded by L1 and L2 with S, and the complement of its closure by T. Also, let T and T2 be the connected components of T. In the light of above paragraph, there are three cases (see Figure 4): either (a) L4 is concurrent with L1 and L3 in a point x lying in the closure of T\, (b) L4 intersects L3 in S, or (c) L4 intersects L3 in T2. Denote with L5 the fifth line of A. We know that L5 is not parallel to any of the existing four lines. We write Aijfc for the triangle bounded by the lines Li; Lj, Lk. Figure 4: Cases (a)-(c) occurring in the proof of Theorem 3.5. (a): If x g L5, then the five lines would bound only three triangles, so we can assume x G L5. Case 1: L5 intersects both L3 and L4 in S. We have six triangles, but A345 = A234 n A145 and A245 C A235, so the maximum number of congruent triangles is three. Case 2: L5 intersects L4 in S and L5 intersects L3 in T1U T2. Six triangles appear. Subcase 2.1: L3 and L5 intersect in ï\. But then we have A135 C A345 C A235. Subcase 2.2: L3 and L5 intersect in T2. Here, A235 C A345 C A135, so once more five congruent triangles cannot occur. (If L5 intersects L3 in S and L4 in T2, then we are, combinatorially, in the situation treated in Subcase 2.2.) Case 3: L5 is concurrent with L2 and L3. Subcase 3.1: All intersection points lie in the closure of S. Five triangles appear, but among them one is a subset of another. Subcase 3.2: L4 and L5 intersect in T2. We apply the same argument as before. Subcase 3.3: L4 and L5 intersect in T1 . Once more five triangles occur, but one is contained in another. C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 Case 4: L5 intersects L3 and L4 in points p and p', respectively, which do not lie in S (since this was covered in Cases 1 and 2). Subcase 4.1: If p and p' lie in Ti, six triangles appear, but A345 c A135 c A235. Subcase 4.2: If p and p' lie in T2, again six triangles occur, but A245 c A235 c A135. Subcase 4.3: If p G T1 and p' G T2, six triangles are present in the arrangement, but A245 c A145 c A345, so at most four triangles are congruent. Case 5: L5 is concurrent with L2 and L4. Subcase 5.1: All intersection points lie in the closure of S. Subcase 5.1 coincides with Subcase 3.1. Subcase 5.2: L3 and L5 intersect in T2. But then we are in the same situation as Subcase 3.2. (b) Let L3 and L4 intersect in y. We know that L5 is not parallel to L1. If y G L5, we obtain six triangles. However, either A135 U A145 = A134 and symmetrically A235 u A245 = A234 or A134 U A145 = A135 and A245 U A234 = A235. In either case, the largest congruence class has cardinality at most four. We have treated the cases when L5 is concurrent with L1 and L3, L1 and L4, L2 and L3, or L2 and L4 in (i). We split the remaining cases into four cases according to where the intersection points of L5 with L3 and L4 lie. In each situation, inclusions are given which make the occurrence of a congruence class of cardinality at least five impossible. Case 1: Both intersection points lie in S. However, we then have A135 c A145, A345 = A134 n A235, and A234 c A245. Case 2: The intersection points of L5 with L3 and L4 lie in T1 and T2, respectively. Then A135 U A245 c A345, A135 U A234 c A235, and A134 U A245 c A145. Case 3: The intersection points of L5 with L3 and L4 lie in T\ and S, respectively. We have A135 c A345 c A235, A245 c A234, and A134 c A145. Case 4: Both intersection points lie in Ti. Then A234 c A235, A135 = A235 n A145, and A134 c A145 c A245. As situation (c) uses very similar arguments, we skip it. We have shown that no two lines in A are parallel. Assume now that three lines L1; L2, L3 of A intersect at a point q. If L4 contains q as well, the largest congruence class which may be formed by a fifth line has size 2. So q G L4 and L4 is not parallel to any of L1; L2, L3. W.l.o.g. let the intersection point of L4 with L2 lie between the intersection point of L4 with L1 and the intersection point of L4 with L3. If there are two coincidences (of three lines)—it is easy to see that there cannot be more—we have three combinatorially different cases. W.l.o.g., in each of them L1; L4, and L5 shall be concurrent. We denote this intersection point with a, and the intersection point of L5 with L2 and L3 with b and c, respectively. We differentiate the three cases by the order in which the intersection points occur on L5. Case 1: a - c - b (or equivalently b - c - a): Eight triangles occur. However, we have A124 U A234 = A134 c A345 and A135 U A235 = A125 c A245. Thus, no five triangles can be congruent. Case 2: b - a - c (or equivalently c - a - b): Again, eight triangles appear, but A245 U A124 = A125, A125 U A135 = A235, A234 U A124 = A134, and A134 U A135 = A345. Case 3: a - b - c (or equivalently c - b - a): A124 n A135 = A125, A235 c A234, and A245 c A345. Furthermore, every triangle is contained in A134. We are left with the case that there is exactly one coincidence of three lines (namely in q). Once more, several cases occur. We leave them to the reader—treating them is a straightforward task in exactly the same spirit as above paragraphs. 161 Ars Math. Contemp. 14 (2018) 267-284 Finally, we prove that the construction from Figure 2 (b) is indeed g-unique. Consider five lines bounding a pentagon P such that we obtain an arrangement A in combinatorial class (A). This implies that no two lines in A are parallel. Combinatorially, there are two types of triangles in P: those sharing exactly two vertices (and thus an edge) with P, and those sharing exactly one vertex with P. Due to straightforward inclusion arguments, all triangles in a congruence class of size 5 are of the same type. Consider the first type, and let A be one of these five congruent facial triangles. Denote the angles of A incident with a vertex of P with a and fi. Applying successively the fact that no two lines in A are parallel, we obtain that a = fi, so A is isosceles. This implies that all angles of P must be equal, and since P is a pentagon, the angles of P measure 3n/5 each. Thus a = 2n/5—in particular, A is not equilateral. Hence, the sides of P must have equal length, so P is a regular pentagon. We treat the second case. We see each triangle of the second type as the union of three faces (of r^): the pentagon P, which lies in all five triangles, and two facial triangles. Since certain pairs of triangles of the second type share a facial triangle, there are at most two congruence classes C1 and C2 of facial triangles. Assume C1 = C2. Thus, there exists a triangle A of second type containing a facial triangle in Ci and a facial triangle in C2. By considering all five congruent triangles of second type, a contradiction is obtained, since necessarily one of these triangles will contain only triangles from either C1 or C2 and thus, it cannot be congruent to A. We have proven that all facial triangles are congruent. Now we may argue as in the preceding paragraph. □ 3.3 I = 6 (a) (b) Figure 5: (a) This arrangement is due to Tudor Zamfirescu and shows that 7 G F(6). To the five lines bounding a regular pentagon a sixth line is added which is parallel to one of the five lines such that seven congruent triangles are present. (b) This arrangement proves that 8 G F(6) and f (6) > 8. In Theorem 3.6 we show that in fact f (6) = 8. The arrangement is obtained by considering six of the seven lines bounding a regular heptagon. Theorem 3.6. We have f (6) = 8, 6 < g(6) < 7, F(6) is complete, and [0..6] c G(6). Proof. The arrangement from Figure 5 (b) proves that f (6) > 8. Theorem 3.5 (iii) states that there is exactly one f-optimal arrangement on five lines, shown in Figure 2 (b). We C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 call this arrangement P. We now show that one cannot produce an arrangement on six lines which has P as a sub-arrangement and features eight (or more) congruent triangles. Assume there exists such an arrangement A. Denote the lines of P by Li;..., L5, and the line added to P in order to obtain A by L. First we prove that the addition of L cannot create a "new" congruence class (i.e. a class the triangles of which are non-congruent to every triangle present in P) of congruent triangles of cardinality at least 8. At least one of the angles n/5, 2n/5, 3n/5, 4n/5 is good in both P and A, since every triangle bounded by L has at least one angle in P. Among all angles in A, each of the aforementioned four angles appears at least ten times in five pairs of opposite angles, since P is a sub-arrangement of A. Thus, L forms at least three copies of the angle a with the lines Li,..., L5, where a G {n/5, 2n/5, 3n/5,4n/5} is fixed. But since the Lj's are pairwise non-parallel, this is only possible if L is parallel to some Lj. But then the addition of L to P yields at most six new triangles—too few. Take the two congruence classes Fp and Ff such that the triangles in Ff are facial in P, and notice that FP = Ff U Ff and |Ff | = |Ff | = 5. Thus, L must add at least three triangles to Fp or Ff. As n/5 belongs to triangles in Fp as well as triangles in F2P, n/5 is a good angle in A, so L makes this angle with a line of P, whence, L is parallel to some Lj, say Li. Among all possible positions of L, only three provide new triangles congruent either to a good triangle in Fp or to a good triangle in Ff, see Figure 6. The number of those new triangles is 1, 1,2, respectively. Figure 6: The three essentially different arrangements of five lines bounding a regular pentagon together with a sixth line parallel to one of the five lines forming at least six congruent triangles. We conclude that in an arrangement on six lines which is f -optimal, every sub-arrangement on five lines contains at most four good triangles. With this in mind, by applying Lemma 2.3 (with k = 5), we obtain the desired f (6) = 8. Lemmas 2.1 and 2.2 yield the bounds on g(6). Theorem 3.5 (i) and the Star of David (which proves that 6 G G(6)) imply that [0..6] c G(6). Together with the arrangements from Figure 5, we are done. □ Among arrangements on six lines bounding exactly six congruent facial triangles, we found three combinatorially non-equivalent ones. (It is unknown whether these are all.) 163 Ars Math. Contemp. 14 (2018) 267-284 In the general case, the solution from Figure 5 (b) seems to be unique; see Conjecture 4.1 (which states that g(6) = 6) in the final section. 3.4 I = 7 Theorem 3.7. We have f (7) = 14, 9 < g(7) < 11, [0..10] U {14} c F(7), and [0..9] c G(7). Proof. By Theorem 3.6, f (6) = 8. Thus, by Lemma 2.2 and Lemma 2.4 (with k = 6), f (7) = 14. For g(7), the lower bound is given by the construction in Figure 7 (a) (by deleting the line marked h), the upper bound by Lemma 2.1. Since the Star of David is 1-extendable, we have 7 g G(7). Removing the line marked h in Figures 7 (a) and (b) shows that 9 g G(7) and 8 g G(7), resp. Thus, [0..9] c G(7). By considering seven of the eight lines bounding a regular octagon, we obtain 10 g F(7). Together with Lemma 2.2, we have [0..10] U {14} c F(7). □ (a) (b) (c) Figure 7: (a) An arrangement proving 12 g G(8). Deleting the line marked h shows that 9 g G(7). (b) An arrangement showing 11 g G(8). Deleting h yields 8 g G(7). (c) This arrangement proves that #(10) > 20. 3.5 I = 8 Theorem 3.8. We have 16 < f (8) < 22, 12 < g(8) < 15, [0..16] \ {13} c F(8) and [0..12] c G(8). Proof. Lemma 2.2 implies the lower bound for f (8), Theorem 3.7 and Lemma 2.4 (with k = 7) the upper bound. For g(8), the lower bound is given by the arrangement from Figure 7 (a), the upper bound by Lemma 2.1. Figures 7 (a) and (b) show that {11,12} c G(8). This, Theorem 3.7 and the fact that the arrangement from Figure 7 (a) minus the line marked h is 1-extendable (which proves that 10 g G(8)) yield [0..12] c G(8). Applying Lemmas 2.2 and 2.4, we obtain [0..16] \ {13} c F(8). □ 3.6 9 < I < 12 As the techniques for proving the following results are very similar to what has been shown, we skip them. A notable exception is the construction from Figure 8. C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 Theorem 3.9. We have 18 < f (9) < 33,15 < g(9) < 21, [0..18] C F(9), [0..15] C G(9), 21 < f (10) < 48, 20 < g(10) < 26, [0..21] C F(10), [0..20] C G(10), 26 < f (11) < 66, 23 < g(11) < 33, [0..26] C F(11), [0..23] C G(11), and 32 < f (12) < 88, 26 < g(12) < 39, [0..28] U {32} C F(12), [0..26] C G(12). Figure 8: An arrangement proving f (11) > 26. It is obtained by joining the two arrangements from Figures 1 and 5 (b) with the technique described in the proof of Proposition 3.1, i.e. such that the two arrangements share a pair of lines (forming the same good angle) in the new arrangement. Deleting the line marked h, one obtains f (10) > 21. By completing the left regular heptagon, we obtain f (12) > 32. 3.7 Summary Consider I < 12 lines in the Euclidean plane, and let f (¿) and g(^) be defined as in the Introduction. Then we have the following bounds. Table 2: Bounding f (¿) and g(^) for t < 12. t 3 4 5 6 7 8 9 10 11 12 f(t) > 1 2 5 8 14 16 18 21 26 32 f(t) < 1 2 5 8 14 22 33 48 66 88 g(t) > 1 2 5 6 9 12 15 20 23 26 g(t) < 1 2 5 7 11 15 21 26 33 39 We were also able to prove that f (13) > 37, f (14) > 44, f (15) > 50, f (16) > 56, and f (17) > 61. 165 Ars Math. Contemp. 14 (2018) 267-284 4 Conjectures Conjecture 4.1. g(6) = 6. If Conjecture 4.1 is true, we would have g(7) < 10. Conjecture 4.2. g(7) = 9. If Conjecture 4.2 is true, we would have g(8) < 14. Conjecture 4.3. The f -optimal arrangements on 6 and 7 lines (consider Figures 5 (b) and 1, resp.) are g-unique. Conjecture 4.4. (a) F(7) is not complete, but (b)for every I, G(t) is complete. References [1] J. Bader and G. Clement, Tighter upper bound for the number of Kobon triangles, 2007, draft version, http://www.tik.ee.ethz.ch/sop/publicationListFiles/ cb2007a.pdf (accessed on 16 September 2017). [2] T. Christ, Database of Combinatorially Different Line Arrangements, http://www.inf. ethz.ch/personal/christt/line_arrangements.php (accessed on 15 June 2016). [3] T. Christ, Discrete Descriptions of Geometric Objects, Ph.D. thesis, ETH Zurich, 2011, doi: 10.3929/ethz-a-007018092. [4] P. Erdos and G. Purdy, Some extremal problems in geometry III, in: F. Hoffman (ed.), Proceedings of the 6th Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic University, Boca Raton, Florida), Utilitas Mathematica, 1975 pp. 291-308. [5] P. Erdos and G. Purdy, Some extremal problems in geometry IV, in: F. Hoffman (ed.), Proceedings of the 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State University, Baton Rouge, Louisiana), Utilitas Mathematica, 1976 pp. 307322. [6] P. Erdos and G. Purdy, Extremal problems in combinatorial geometry, in: R. L. Graham, M. Grotschel and L. Lovasz (eds.), Handbook of Combinatorics, The MIT Press, Cambridge, Massachusetts, volume 1, 1995 pp. 809-874. [7] D. Forge and J. L. Ramirez Alfonsin, Straight line arrangements in the real projective plane, Discrete Comput. Geom. 20 (1998), 155-161, doi:10.1007/pl00009373. [8] K. Fujimura, The Tokyo Puzzles, Charles Scribner's Sons, New York, 1978. [9] Z. Furedi and I. Palasti, Arrangements of lines with a large number of triangles, Proc. Amer. Math. Soc. 92 (1984), 561-566, doi:10.2307/2045427. [10] M. Gardner, Wheels, Life and Other Mathematical Amusements, W. H. Freeman & Co., San Francisco, California, 1983. [11] B. Griinbaum, Arrangements and Spreads, volume 10 of CBMS Regional Conference Series in Mathematics, American Mathematical Society, Providence, Rhode Island, 1972, http: //bookstore.ams.org/cbms-10. [12] B. Grunbaum, Convex Polytopes, volume 221 of Graduate Texts in Mathematics, Springer, New York, 2nd edition, 2003, doi:10.1007/978-1-4613-0019-9. [13] V. Kabanovitch, Kobon triangle solutions, Sharada (publication of the Russian puzzle club Diogen) 6 (1999), 1-2. C. T. Zamfirescu: Congruent triangles in arrangements of lines 361 [14] N. J. A. Sloane, Sequence A006066 (formerly M1334) in The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org. [15] E. W. Weisstein, Kobon Triangle, from MathWorld—A Wolfram Web Resource, http:// mathworld.wolfram.com/KobonTriangle.html.