A dynamic geometry system approach to analyse distance geometry problems based on partial Latin squares

A dynamic geometry system approach to analyse distance geometry problems based on partial Latin squares Raúl M. Falcón Department of Applied Mathematics I, University of Seville, Sevilla, Spain ABSTRACT Partial Latin squares constitute an interesting approach to improve the teaching of different subjects in the mathematics classroom. This paper delves into this topic by introducing the use of a Dynamic Geometry System to deal with these combinatorial structures as a source of loci of points in the Euclidean plane. It is assumed to this end that the distance matrix among all these points contains a zerodiagonal symmetric partial Latin square with at least one non-zero filled cell per row. ARTICLE HISTORY Received 19 December 2018 KEYWORDS Distance geometry problem; dynamic geometry system; partial latin square 2010 MATHEMATICS SUBJECT CLASSIFICATIONS 05B15; 97D40 1. Introduction Apartial Latin square of order nis an n×narray whose cells are either empty or contain an element from a finite set of nsymbolssothatnotwoidenticalsymbolsappearwithin any given row or column. This is a Latin square if all its cells are non-empty. It is said that a partial Latin square P=(pij)can be completed to a Latin square L=(lij)having the same order than Pif pij =lij, for all non-empty cell (i,j)within P. Thus, for instance, the wellknown puzzle called Sudoku consists of a partial Latin square of order nine that can be uniquely completed to a Latin square of the same order so that the 81 cells of the latter are partitionedintonine3×3 subsquares, all of them containing the nine distinct symbols under consideration. One can find different studies in the literature about how partial Latin squares in general, and Sudokus and similar puzzles in particular, can be implemented to improve mathematics teaching [1–8]. As such, they support the importance of using Discrete mathematics in the mathematics classroom [9,10].Thispaperdelvesintothistopicbyfocusingonanew dimension of the usability of partial Latin squares as a source of loci of points that can be studied by means of a Dynamic Geometry System (DGS) [11]. It consists of a two- and/or three-dimensional graphical user interface with a geometric constraint solver that enables one to construct loci in a dynamic and parametric way [12–14]. This paper makes use in particular of the open source GeoGebra [15], which has arisen as a useful DGS in the mathematics classroom to develop skills concerning the study of loci of points [16–18]. CONTACT Raúl M. Falcón [email protected] Department of Applied Mathematics I, University of Seville, Avenida 295 InordertoendowpartialLatinsquareswiththementioneddynamism,theDistance Geometry Problem (DGP) [19,20]arisesasaninterestingapproach.Thisproblemconsists of determining the existence of a set of points within a given k-dimensional space so that the distance matrix among all these points holds certain constraints. Due to the NP-hard computational complexity of the DGP, Saxe [21]suggestedtoputemphasison highly constrained distance matrices. In this regard, the requirement of non-repetition of symbolswithinanyroworcolumnofapartialLatinsquareestablishesaseriesofgeometric constraints that make any of these combinatorial structures to constitute an interesting distance matrix to be considered [22,23]. The paper is organized as follows. Section 2deals with some preliminaries concepts and resultsonpartialLatinsquaresthatareusedthroughoutthepaper.Section3focuses on the descriptionof the problem, whose assumptions are illustrated by making use of GeoGebra to analyze the DGP related to partial Latin squares of order n∈{3, 4}. The study of higher orders is illustrated in Section 4by making use of the so-called scanner method to deal with a partial Latin square of order six. 2. Preliminaries ThissectiondealswithsomebasicconceptsandresultsonpartialLatinsquaresthatare used throughout the paper (see [24] for more details about this topic). From here on, let [n]:={0, 1, ...,n−1}be the set of symbols on which every partial Latinsquare ofordernis based. Moreover, all the rows and columns of any such an array are assumed to be naturally indexed by that set. In this way, every non-empty cell is uniquely determined by a triple (r,c,s)∈[n]×[n]×[n], where rand care the respective indices of the row and the column in which the cell is situated, and sis the symbol appearing within such a cell. The set of all triples related to the non-empty cells of a partial Latin square L constitutes its set of entries, which is denoted E(L). Example 2.1: The set of entries of the following partial Latin square of order five L≡ 0 2 3 4 1 2 3 3 4 1 4 2 1 is E(L)={(0, 0, 0),(0, 2, 2),(0, 3, 3),(0, 4, 4),(1, 0, 1),(1, 4, 2),(2, 1, 3),(3, 0, 3),(3, 2, 4),(3, 4, 1),(4, 0, 4),(4, 1, 2),(4, 3, 1)}. Two partial Latin squares Land Lare said to be strongly isotopic if there exist two permutations fand gon the set [n]suchthatE(L)={(f(r),f(c),g(s)):(r,c,s)∈E(L)}.That is, the map fpermutes the rows and columns of the partial Latin square L,whilethemap gpermutes its symbols. The pair (f,g)is called a strong isotopism from Lto L.Iff=g, then Land Lare said to be isomorphic and the permutation fis called an isomorphism from Lto L. To be strongly isotopic or isomorphic are equivalence relations among partial Latin squares. The distribution of partial Latin squares into isomorphism classes is known [25–27], for order n≤6. 296 R. M. FALCÓN Example 2.2: The permutation (02143)is an isomorphism from the partial Latin square Lin Example 2.1 to the partial Latin square L≡ 3 0 4 0 0 1 2 3 4 3 1 4 1 In order to prove this fact, let us see how the isomorphism (02143)acts on each one of the triplesofthesetofentriesE(L)todefinethesetofentriesE(L). E(L)→E(L)E(L)→E(L)E(L)→E(L) (0, 0, 0)→(2, 2, 2) (1, 4, 2)→(4, 3, 1) (3, 4, 1)→(0, 3, 4) (0, 2, 2)→(2, 1, 1)(2, 1, 3)→(1, 4, 0) (4, 0, 4)→(3, 2, 3) (0, 3, 3)→(2, 0, 0)(3, 0, 3)→(0, 2, 0) (4, 1, 2)→(3, 4, 1) (0, 4, 4)→(2, 3, 3)(3, 2, 4)→(0, 1, 3) (4, 3, 1)→(3, 0, 4) (1, 0, 1)→(4, 2, 4) Now, suppose the symbols of each cell in Lto be transformed by means of the permutation (01)(23)(4). Then, the triple (Id, (01)(23)(4)), where Id is the trivial permutation on the set {0, 1, 2, 3, 4}, is a strong isotopism from Lto the partial Latin square L ≡ 2 1 4 1 1 0 3 2 4 2 0 4 0 . Similarly, Land L arestronglyisotopicbymeansofthestrongisotopism((02143),(01)(23) (4)). From here on, let Lndenote the set of partial Latin squares L=(lij)of order nsatisfying the following three conditions: (1) It is zero-diagonal.Thatis,lii =0, for all i∈[n]. (2) It is symmetric.Thatis,lij =lji, for all i,j∈[n]. (3) There exists at least one non-zero filled cell per row (or, equivalently from the just imposed symmetry, per column). The order of every Latin square in Lnis even. This is not, however, a requirement for partial Latin squares in general, as one can observe with the partial Latin square 0 1 1 0 2 2 0 ∈L3. 297 3. Description of the problem From here on, let R2denote the Euclidean plane, and let d(P,Q)denote the Euclidean distance between two given points P,Q∈R2. The following problem is introduced to endow zero-diagonal symmetric partial Latin squares with a dynamism that can be dealt with by means of a DGS. Problem 3.1: Let L∈Ln,wheren≥2. Does there exist an ordered set of ndifferent points {P0,...,Pn−1}⊂R2and an ordered set of n−1 different positive real numbers {d1,...,dn−1}⊂Rso that d(Pr,Pc)=d(Pr,Pc)=ds, for all {(r,c,s),(r,c,s)}⊆E(L)? Problem 3.1 constitutes a DGP associated with the partial Latin square L∈Ln.From hereon,thisisdenotedDGP(L). Further, the ordered sets of points and distances previously described constitute a solution of such a DGP. The case n=2istrivial,becauseevery pair of different points in the Euclidean plane is a solution of DGP(L2),wheretheLatin square L2≡0 1 1 0 is the only element in the set L2. In order to deal with higher orders, the following result enables one to ensure that solving this kind of problem only depends on the strong isotopism class of the partial Latin square under consideration. Lemma 3.1: Let L,L∈Lnbe two strongly isotopic partial Latin squares. Then,any given solution of DGP(L)can be reordered to obtain a solution of DGP(L). Proof: Let Sbe a solution of DGP(L)formed by an ordered set of points {P0,...,Pn−1}⊂ R2and an ordered set of distances {d1,...,dn−1}⊂R.Moreover,let(f,g)be a strong isotopism from Lto L. Then, keeping in mind that both fand gare permutations of the set [n], we can reorder the two sets of Sby replacing each point Piby the point Pf−1(i), and each distance diby the distance dg−1(i). In this way, we get a new ordered set of points {P 0,...,P n−1}⊂R2and a new ordered set of distances {d 1,...,d n−1}⊂R,whereP i= Pf−1(i), for all i∈[n], and d i=df−1(i), for all i∈[n]\{0}.Inordertoseethatthesetwo orderedsetsconstituteasolutionofDGP(L),supposethat {(r,c,s),(r,c,s)}⊆E(L). By definition, since (f,g)is a strong isotopism from Lto L,wehavethat {(f−1(r),f−1(c),g−1(s)),(f−1(r),f−1(c),g−1(s))}⊆E(L). As a consequence, since PisasolutionofDGP(L),wehavethatd(Pf−1(r),Pf−1(c))= d(Pf−1(r),Pf−1(c))=dg−1(s).Equivalently,d(P r,P c)=d(P r,P c)=d s.Hence,thenew pair of ordered sets describes a solution of DGP(L). 298 R. M. FALCÓN Thus,forinstance,thesetL3is distributed into two strong isotopism classes, whose representatives are L3,1 ≡ 0 1 1 0 2 2 0 and L3,2 ≡ 012 1 0 2 0 Hence, the case n=3consistsoftwoDGPs,forwhichonehastofindtwopositivereal numbers d1,d2>0 and three different points P0,P1and P2such that DGP(L3,1)≡d(P0,P1)=d1= d2=d(P1,P2) or DGP(L3,2)≡d(P0,P1)=d1= d2=d(P0,P2). Both DGP(L3,1)and DGP(L3,2)have solution, whatever the distances d1and d2are. Constructively, once a point P0is fixed in the Euclidean plane, let P1be any point of the circle of centre P0and radius d1. Then, a solution of DGP(L3,1)(respectively, DGP(L3,2)) is determined by taking P2as any point of the circle of centre P1(respectively, P0)andradiusd2. Figure 1illustrates both constructions. Ingeneral,theuseofcirclesisanaturalwaytodealwithProblem3.1fromageometric point of view. It involves every DGS to be an interesting tool not only to solve constructively this problem but also to determine certain loci of points associated with it. In order to see it, let C(P,r)⊂R2denote from here on the circle in the Euclidean plane that has a given point P∈R2as its centre, and a given positive real number r>0 as its radius. Thus, for instance, it is clear that the concentric circles C(P0,d1)and C(P0,d2),whichhavepreviouslybeen used to solve DGP(L3,2), are the respective loci of the points P1and P2once the point P0is fixed. Similarly, the circle C(P0,d1)is the locus of the point P1once the point P0is fixed to solve DGP(L3,1). But, what about the locus of the point P2concerning this last problem? GeoGebra is a DGS that can be used to answer this question. It offers the possibility of showingthetracethatisleftbyanyalreadyconstructedobjectthatismovedaroundthe Euclidean plane according to certain geometric constraints. In this regard, once both points P0and P1are drawn in the graphics view of the software, the locus of the point P2can be obtained after activating the trace of the circle C(P1,d2),andmovingthepointP1around the circle C(P0,d1)(see Figure 2). Figure 1. Constructive methods to solve DGP(L3,1) and DGP(L3,2). 299 Figure 2. Loci of points related to DGP(L3,1). Figure 3. Detail of the construction to determine the radii of the annulus in Figure 2. Figure 2shows that the locus under consideration is an annulus. Moreover, GeoGebra also enables one to ensure that the inner and outer radii of such an annulus are determined by the intersection of the straight line containing both points P0and P1,andthecircle C(P1,d2)(see Figure 3). That is, the annulus has inner radius |d1−d2|and outer radius d1+d2.Itisneveradisk,becaused1= d2. Now, let us delve into the use of DGSs to deal with the case n=4. Remark to this end that the set L4isdistributedinto10strongisotopismclasses,havingasrepresentativesthe following partial Latin squares. 0 1 1 0 0 1 1 0 L4,1 0 1 1 0 0 2 2 0 L4,2 0 1 2 1 0 2 0 1 1 0 L4,3 0 1 2 1 0 2 0 3 3 0 L4,4 0 1 2 1 0 2 2 0 1 2 1 0 L4,5 0 1 2 1 0 2 2 0 3 2 3 0 L4,6 0 1 2 3 1 0 2 0 3 0 L4,7 0 1 2 3 1 0 2 0 1 3 1 0 L4,8 0 1 2 3 1 0 2 2 0 1 3 2 1 0 L4,9 0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 L4,10 From a constructive point of view, both DGP(L4,1)and DGP(L4,2)are solved similarly to DGP(L2), because every feasible solution of the former consists of two pair of points satisfying the latter. The only difference between them is given by the extra constraint in DGP(L4,1) about the equality of distances between each pair of points. For m∈{3, 4, 5, 6},eachDGP(L4,m) consists of imposing some extra constraints to those ones describing DGP(L3,2) in order to include a fourth point P3in the feasible 300 R. M. FALCÓN Figure 4. Construction of loci of points in DGP(L4,3). solution. For m∈{3, 4}, the only constraint to be added is referred to the distance d= d(P2,P3).Ithastobeequaltod1,ifm=3, or take a third different value d3,ifm=4. Both problems are feasible, whatever the distance dis. To see it in GeoGebra, it is enough to consider a solution of DGP(L3,2)andselectthepointP3from the circle C(P2,d).Thetrace that this circle leaves by moving the point P2around the circle C(P0,d2)gives rise to a new annulus of inner radius |d2−d|and outer radius d2+d. See in this regard Figure 4,where it is shown the loci of the points P1,P2and P3in DGP(L4,3)oncethepointP0is fixed. Imposing the constraint d(P1,P3)=d(P0,P2)to DGP(L4,3)andDGP(L4,4)gives respectively rise to DGP(L4,5)andDGP(L4,6). In both cases, once a solution of DGP(L3,2) is determined in GeoGebra, the point P3is selected from the intersection of the circles C(P1,d2)and C(P2,d).Figure5illustratesthisconstructionforDGP(L4,5), where two candidates P3and P 3are indicated for the fourth point. GeoGebra also shows that the trace that both points P3and P 3leave by moving the point P1around the circle C(P0,d1)is the circle C(P2,d),whereasitisthecircleC(P2,d1) in case of moving the point P2around the circle C(P0,d2).Further,Figure6shows how this DGS can also be used to determine the loci of both points P3and P 3concerning any possible value of both distances d1and d2in DGP(L4,5). Finally, Figure 7illustrates as a dashed line the locus of the intersection point of both segments P0P1and P2P3in the solution shown in Figure 5, by moving the point P1around the circle C(P0,d1). The consideration of this kind of locus is interesting to deal with DGPs associated with moving architecture and adaptive structures [28]. Figure 5. Constructive method to solve DGP(L4,5). 301 Figure 6. Loci of points related to DGP(L4,5) according to the distances d1(left side) and d2(right side). Figure 7. Locus of an intersection point associated with DGP(L4,5). Figure 8. Constructive methods to solve DGP(L4,m), for m∈{7, 8, 9, 10}. SimilarconstructionscanbedonetodealwithDGP(L4,m), for m∈{7, 8, 9, 10}.Figure8 shows some possible constructions in this regard. Segments have been drawn therein to visualize those non-empty cells within the corresponding partial Latin squares. This set of segments constitutes a conformation of the corresponding DGP. 4. The scanner method In order to determine the loci of points verifying certain geometric constraints, Losada [29] described an interesting implementation of both tools Trace and Dynamic Colours in GeoGebra, which is known as the scanner method. It consists of defining a set of points 302 R. M. FALCÓN Figure 9. Vertical scanner in GEOGEBRA. with the same coordinate that is close enough to seem a vertical line that sweeps the screen once the mentioned coordinate is associated with a slider (see Figure 9). The original idea of Losada comes up from the activation of the trace of all these points after providing them with dynamic colours that depend on certain geometric constraints under consideration. After a sweep is completed, one can observe an image on the screen that represents in a visual and precise way the corresponding locus. The scanner method is useful to deal with DGPs associated with partial Latin squares. Figure 10 shows, for example, a locus of points related to DGP(L4,10)oncethefirsttwo points P0and P1are fixed. More specifically, in a grey-scale referred to the approximation of an optimal solution of the problem, the image represents the locus of points where the third point P2can be placed in order to exist a fourth point P3such that the set of points {P0,P1,P2,P3}constitutesasolutionoftheproblem.Thewhitelinesconstituteindeedthe locus of the point P2to get a feasible solution. Figure 10. Scanned image of a locus of points associated with DGP(L4,10).