Grenier D., Payan C. (1998) Discrete mathematics in relation to learning and teaching proof and modelization. First CERME international conference.
	Abstract The article presents the bases of a research aimed in the long run towards the construction of an " ambiant environment " for discrete mathematics, a construction which would not only facilitate first acquaintance to this mathematical field, but would also provide an alternative approach to some transversal concepts, such as proof and modelization. First, we study their status and role in pupils'curricula and manuals ans we show that this mathematical field is in fact most often approached in a casual and unofficial manner, in combination with other mathematical knowledge and thus diverted from its real significance. We then develop our thesis on possibilities offered by discrete mathematics as a tool for the learning of proof and modelization. In order to support our thesis, we investigate some specificities of proof practice in discrete mathematics, especially from the viewpoint of truth checking and validation.
© Denise Grenier & Charles Payan

1. What are discrete mathematics? Discrete Mathematics is not well known in France, even by mathematics teachers. However, this mathematical field has a different status in other countries, such as Hungary or United States. The subjects and the aims of Discrete Mathematics are to study configurations which can be described by some finite or countable relations (in a one-to-one relation with N). This mathematical field also develops its own specific objects and methods, for example, the decomposition/recomposition method, or structuration by coloration, or modelization by a graph. We are particularly concerned with two characteristics : first, Discrete Mathematics is the mathematics of natural numbers, related to Peano axioms, and second, most classical problem statements in Discrete Mathematics are easy to understand, even by non specialists. Didactical research about this mathematical field concerns almost only " counting " questions.(1) 2. Didactical transposition of discrete mathematics in France In France, Discrete Mathematics is taught only in rare courses (e.g. optional courses, or Mathematics for economics), or after the Fifth year in the University. The only exception is found in some chapters called " counting " or " combinatorics analysis " for 17 year pupils, where symbols such as , , n!, np are introduced. One can also find, in some parts of secondary schoolbooks, a few particular tools given to solve specific problems : graphs and trees. Unfortunately, these objects, which are complex concepts of Graph Theory, are usually given without any of their essential mathematical properties. As a consequence, not much can be done with them !    Our analysis of schoolbooks shows that one can find, from time to time, discrete mathematics exercises, but it seems that the problematics of discrete mathematics have not often been recognized by the authors. Here are two examples. Example 1 The problem (2) consists in partitioning the large square minus the small square, in five equal parts, of identical shape and area. The squares are " drawn " by matches, and the partition has to be realized with " 10 matches ".    The authors indicatted that " reflections are very useful to solve this problem ".   A mathematical analysis shows in fact that reflections are not useful to find the solution. The context under which the problem is posed is not very relevant : neither the number of matches nor their nature are useful. What knowledge, which notions are involved here ? What can pupils learn in such a situation ?    Yet, this problem can be formulated as a particular case of the following fundamental problem : " Tile a polymino with a basic polymino. " Here, the polymino to tile is a 4x4 square, with a deleted square cell, and we have to tile it with identical triminos. This new formulation brings a real mathematical interest to the above problem. We analyse it later. Example 2 : Euclid's rectangle We can find the following situation in teachers'practices in the secondary school (13-15 year pupils). It has been studied from a didactical viewpoint by Arsac (Arsac et alii, 1992, pp.89-104). Draw a rectangle ABCD so that AB = 8 cm and BC = 5 cm. Take a point E on [AC] so that AE = 3 cm. Draw the line parallel to (AD) passing through E ; it intersects [AB] at a point N and [DC] at a point L. Draw the line parallel to (AB) passing through E ; it intersects [AD] at a point M and [BC] at a point K. Which of the two rectangles EMDL and ENBK has the larger area ?   To solve this problem, it is necessary to make an " exact " calculation, using Pythagoras or Thales theorems. But the more economical solution consists in analysing the figure in sub-figures, and comparing their areas. This solution is usually not taken into consideration. Yet, the " combinatorial " point of view allows to reach minimal hypotheses in an easier way : in fact, the answer does not depend on measures and, on the other hand, the condition " ABCD is a parallelogram " is sufficient in itself. 3. Global research questions One of our research aims is to induce changes in the teachers' and pupils' knowledge in discrete mathematics. Indeed, discrete mathematics problems can play a specific role towards learning proof and modelization.    Yet, in France, proof appears essentially in geometry and from only two aspects : simple deductive reasoning and syntactical proof writing. Pupils have to learn how one can deduce given or evident conclusions from given and " true " hypotheses. There is no real place for questioning about truth, nor for raising conjectures. It is explicitly said in curricula that teachers have to use only those properties which are in the textbooks or given in the course, or given in an official program list. On the other hand even though curricula specify that modelization is important, it has no place in teachers' practices and in classes. 4. Proof and modelization Let us consider the following problem : " Is it possible to tile, with dominos, a given odd polymino with a deleted square ? ". If it is possible to find a tiling, the question is solved, but only for the given particular occurrence. However, in general cases, after several unsuccessful attempts, a proof is needed. 4.1. Induction In discrete mathematics, proofs by induction are very often constructed as follows, through " reasoning by contradiction " : suppose there is a conter-example at one step n ; take a minimal conter example (step n0) ; n0 exists because of the Peano axiom : a non empty sub set of N has a first element ; from this minimal configuration, the proof proceeds to producing another smaller one : we then have a contradiction. Often, the smaller one is obtained in splitting the minimal one. This scheme of proof gives, in the same time, an algorithm to construct the objects and the initialization of the induction. Example 3 The problem given in example 1 is a particular case of the following problem : " Is it possible to tile, by L-shaped triminos, a 2n-size polymino, with a deleted square ?"   An inductive proof does of course exist : a) for n=0, the conclusion is obviously positive ; b) for n>0, splitting the square in four parts, and putting a trimino in the center of the square, as below, we obtain four 2n-1 size polyminos, each with a deleted square, which are, by hypothesis, tiled by L-shaped triminos.   This proof moreover gives a tiling algorithm, which is easy to use on any given example and, in the same time, which validates the proof. 4.2. Modelization Modelization is not a usual activity in French schools : most often, to a particular situation is associated only one mathematical model, and the role of the problem is only to get pupils to learn how the appropriate model should work. In discrete mathematics, the large variety of basic models makes the modelization work necessary. Example 4 Let us consider the following problem : " What is the number of all different configurations, when n identical balls are to be painted with at most k colours ? "    We can, without modelization, find solutions for particular cases. However, it is difficult to find a solution for each n and each k. A modelization approach allows a better investigation of the question : first, colour can be numbered e.g. 1, 2, etc... A representation of a configuration is then :   An appropriate modelization consists in establishing a one-to-one relation between a configuration and a word made with n " 0 " and k-1 " 1 ", such as : O O / O / O O O / / O   or   0 0 1 0 1 0 0 0 1 1 0. The problem can then be reformulated as : " What is the number of different words with n " 0 " and k-1 " 1 " ?". Now, it is easy to answer. Example 5 : Kœnigsberg bridges   " Is it possible to a person to walk across each bridge, once and only once ? " A first step in modelization consists in changing the banks, islands, rivers, etc.. by a set of regions, here four regions, linked by bridges. The model for this situation is a graph G, as above.    Although this model looks rather natural, especially since pupils happen to figure out similar representations, it may often raise a few difficulties : the isomorphism between a countryside stroll and a walk in a graph is not necessarily obvious.    A work on the model will help to understand the essential condition which decides for the existence or non-existence of a walk passing over each bridge once and only once, namely the parity of the number of edges reaching each vertex.  Pigeonholes This is a very elementary principle which plays an important role in numerous reasonings in discrete mathematics. The so called "pigeonholes" principle simply asserts that when there are less holes than pigeons, there should be at least one hole where two pigeons have to settle.    Let us illustrate the strength of this "obvious" principle with a problem of combinatorial geometry : what is the smallest equilateral triangle in which k disks of diameter 1 can fit ? Let us mention that this problem is solved only for small values of k and for triangular numbers, namely whole integers of the form k=q(q+1)/2.       On the above left figure, 6 disks of diameter 1 fit in an equilateral triangle of edge length 2+ˆ3. Can one put 5 disks (or maybe even 6) in a smaller equilateral triangle ? By a translation of 1/2 unit towards the interior of the triangle, in a perpendicular direction to the edges, one gets an equilateral triangle of length 2 which contains all circle centres. The question is thus reduced to the following one : find the smallest equilateral triangle containing 5 points with the property that any two of them are distant by at least 1 unit of length. Let us show that such a triangle cannot have an edge length less than 2. If it were the case, divide the triangle in four homothetic ones in the ratio 1/2, by joining the edge middle points. One of these triangles would contain at least two of the points. The distance between these two points would be less than the smaller triangles edge length, thus less than 1, which is a contradiction. Conclusion In this article, we have tried to illustrate the strength of some combinatorial models and tools which are likely to be alive in other taught domains of mathematics. Last but not least, these tools and models are easily apprehended and do not require sophisticated prerequisites. For example, the pigeons' holes principle can be used to solve problems of a very different nature. In a more fundamental way, we have tried to present a few "simple" situations in which meaning and truth become central to the cognitive and teaching process. Notes (1) For example, following researches : Le Calvez F., Urtasun M , Giroire H., Tisseau G., Duma J, Les machines à construire . Des modèles d'interaction pour apprendre une méthode constructive de dénombrement, actes des 5èmes journées EIAO de Cachan, 1997 ; and Batanero C., Godino J.D., Navarro-Pelayo V., Effect of the implicit combinatorial model on combinatorial reasoning in secondary school pupils, ESM, 32, pp.181-199, 1997. [Back] (2) in " Magnard ", 3ème, 1989, rubrique " Casse-tête " [Back] Bibliographie Appel K., Haken W. (1977) Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21, 429-490. Appel K., Haken W., Koch J. (1977) Every planar map is four colorable. Part II. Reducibility, Illinois J. Math.21, 491-567. Arsac G. (1990) Les recherches actuelles sur l'apprentissage de la démonstration et les phénomènes de validation en France, Recherches en Didactique des Mathématiques. 9(3) 247-280. Arsac G. et al. (1992) Le raisonnement déductif au collège, Presses Universitaires de Lyon. Audin P., Duchet P. (1992) La recherche à l'école : Math.en.Jeans, Séminaire de Didactique des Mathématiques et de l'Informatique. n°121, Grenoble, 107-131. Balacheff N. (1987) Processus de preuve et situations de validation, Educational Studies for Mathematics, vol.18, n°2, 147-176. Berge C. (1973) Graphes et Hypergraphes, Bordas. Chevallard Y. (1985) La transposition didactique : du savoir savant au savoir enseigné, La Pensée Sauvage, Grenoble Duchet P. (1995) Modélisation Combinatoires, Structures et méthodes, Cours de DEA ouvert au télé-enseignement, Université Paris 6, Paris 1995. Grenier D. (1995) Savoirs en jeu dans des problèmes de combinatoire. in: Arsac G., Gréa J., Grenier D., Tiberghien A. (eds.) Différents types de savoirs et leur articulation (pp.235-251). La Pensée Sauvage, Grenoble. Legrand M. (1996) La problématique des situations fondamentales, Recherches en Didactique des Mathématiques 16/2, 221-280. Payan Ch. (1995) La géométrie entre les lignes, Cahier du séminaire DidaTech., Université Joseph Fourier, ed. IMAG, Grenoble. Payan Ch. (1997) Empilement de cercles égaux dans un triangle équilatéral. A propos d'une conjecture d'Erdös-Oler, Discrete Mathematics, 165/166 (1997), 555-565. Rolland J. (1995) Le rôle ambigu des problèmes de combinatoire dans les manuels de troisième, Mémoire de DEA de Didactique des Mathématiques, IMAG, Université de Grenoble. Stewart I. (1994) C'est du billard ! Compactage optimal de billes dans un triangle équilatéral, Pour la Science n° 205 (nov. 1994), 96-100.