Dessins et croisements - Collège Villey Desmeserets (Caen)

Dans ce problème, on étudie des dessins de mathématicien. Du point de vue du mathématicien, un dessin est un ensemble de points (•) et des traits qui relient ces points. Dans notre vision, un seul trait peut relier deux même points, et les traits peuvent se croiser sans problème, sans pour autant former un nouveau point. Supposons cependant que nous essayons de limiter les croisements dans le dessin. Pour un nombre c de croisements, quel est le plus grand nombre de traits que l’on puisse dessiner tout en limitant le nombre de croisement à au plus c ?
On pourra aussi s’intéresser à des dessins qui interdisent un schéma. Par exemple, le schéma le plus simple consiste en trois points • tous reliés deux à deux (un parcours utilisant trois traits et qui revient au point de départ, ce qu’on pourrait appeler un triangle). Quel est le plus grand nombre de traits que l’on peut dessiner dans une figure ayant un nombre de points donné sans avoir un triangle ? On pourra enfin se poser la même question si l’on interdit une autre forme, par exemple quatre points reliés selon un cycle ? quatre points tous reliés deux à deux ?