Cercle contenant 2018 points

Bonsoir,
Je crois que les données 2017, 2018 et 2019 ont pour but de parasiter ta réflexion et de te faire croire que le problème est difficile, mais je peux me tromper..

Face à ce genre de problèmes, une démarche heuristique peut être l'étude de situations semblables avec des nombres plus petits pour mettre en place un raisonnement.

Est-il possible de jeter 5 points distincts dans le plan tels qu'aucun cercle ne contienne exactement 3 d'entre eux ?

Après une petite étude, je pense qu'il s'agit d'un problème de géométrie, plutôt que de logique.
je propose de renommer le fil

Cercle contenant 2018 points

et de le déplacer dans le forum Géométrie...
D'accord ?

Salut nizar13,
idée : considère l'ensemble des médiatrices de deux points quelconques de E. Recouvrent-elles tout le plan ? Sinon, que penses-tu des cercles centrés en un point situé hors de ces médiatrices (et hors de E) ?

Salut jacquot,
En choisissant un point C hors des médiatrices et hors de E, les distances de C aux points de E sont toutes distinctes, et il est donc trivial de construire un cercle de centre C dont le disque ouvert contient exactement n pointrs de E, pour n de zéro à card E. Il suffit de choisir un rayon inférieur à la premiere distance pour n=0, de rayon compris entre la nième distance et la n+1ème distance pour n de 1 à card E - 1, et enfin un rayon supérieur à la nième distance pour n = card E.

Ah, OK.
Quant au choix de C (mais je ne sais pas si ça intéresse encore nizar13 :-) ), il est facile aussi :

Les directions des médiatrices sont en nombre fini. Il suffit donc de prendre une droite d'une direction différente et sur cette droite de choisir un point C hors de E et hors des intersections (en nombre fini) de cette droite avec les médiatrices.


Par ailleurs, le fait que nizar13 ait pu penser que c'était un problème de logique, alors que bien évidemment c'est un problème de géométrie, est révélateur, à mon avis, d'une tendance propagée par certains qui voudraient nous convaincre que les maths, c'est de la logique appliquée, alors que la logique n'est, et ne sera toujours qu'une servante des maths (et de la pensée plus généralement). :-)

Bonjour.
Lorsque quelqu'un vient nous raconter que "les mathématiques ne sont que de la logique appliquée", on peut toujours faire semblant de croire que le but poursuivi est de nous persuader d'un truc aussi peu crédible. Alors que le coeur du message est "croyez-m'en, moi qui suis un grand sachem intergalactique de la logique, per secula seculorum, amen".

Cela étant dit, il reste le problème suivant. Une fois que l'on dispose des nombres entiers, on peut construire la logique autour de ou(x,y)=x+y-x*y, et(x,y)=x*y et du quotient modulo le carré de chaque variable. Tout vient tout seul, quasiment gratuitement... A part une réponse à la question: comment fait-on pour raisonner avant de disposer des nombres entiers ?

Cordialement, Pierre.

@ GG
Oui, ce problème est un problème de géométrie, on pourrait dire de géométrie combinatoire, et non de logique.
Tout à fait d'accord pour refuser l'idée que toutes les mathématiques sont de la logique appliquée. Mais il ne s'ensuit pas que la logique ne soit qu'une servante des mathématiques. C'est une discipline mathématique parmi d'autres, tout aussi légitime et féconde que d'autres. Sa particularité, c'est que ses rudiments sont indispensables pour le reste des mathématiques, c'est en ceci que réside son caractère de « servante », mais ce ne sont que les rudiments, par exemple ce qu'enseignent les professeurs de classes préparatoires comme Jean-Louis Rouget, de Marseille http://math.unice.fr/~frapetti/analyse/Logique.pdf ou bien d'autres.
Pour le reste il y a tout un développement spécifique, dont je parle par ouï-dire, car je ne maîtrise pas cette discipline, au-delà des rudiments que j'ai dits, développement qui semble bien intéressant, mais hélas que je ne puis que contempler de loin.
Bonne journée.
Fr. Ch.

[Activation du lien. AD]

@Blueberry,
Oui, c'est le même principe, on projette parallèlement sur une droite selon une direction différente de celles des droites qui relient deux points du nuage, et on partage les points en deux.

@Georges Abitbol,
Oui, j'ai oublié de préciser qu'étant donné un ensemble fini de directions (classes d'équivalence des droites du plan pour la relation du parallélisme ), on peut toujours en trouver une autre :
On prend le représentant de chaque direction passant par un point fixe O arbitraire. Ce faisceau de droites rencontre une droite d ne passant pas par O en un nombre fini de points (au plus le nombre de directions) et on choisit un autre point X sur d. La direction de la droite OX répond à la demande.

@Chaurien,
Oui, réduire la logique au rôle de servante était un peu exagéré et provocateur de ma part :-) Je suis bien conscient que la logique mathématique est une discipline mathématiques à part entière. Par contre, claironner que les maths, c'est de la logique appliquée ... je ne l'accepterai que sous la torture :-)

@ GG
Cela semble simple comme ça, mais comme j'ai dit je ne suis pas parvenu à le rédiger correctement.

Mon post peut paraître dévier du sujet, mais je pense que c'est important, sinon je ne vous embêterais pas.

@GG et Blue : Je me faisais l'avocat du diable.
je suis d'accord que ça a un sens de déplacer le fil dans le forum Géométrie, ne serait-ce que pour qu'il soit lu par des personnes intéressées. Par contre, GG semble dire que c'était une erreur de considérer que c'était un exercice "de logique" plutôt qu'un exercice "de géométrie". Je n'aime pas cette idée.
A mon avis, l'idée que les maths ne seraient que de la logique appliquée, ce n'est pas une querelle de chapelle (personne n'aime être l'appliqué ou l'appliquée de quelqu'un), c'est juste du bon sens, et même, pire encore, un enfonçage de porte ouverte.
D'autre part, si certains énoncés peuvent avoir une "saveur" géométrique, ou algébrique, ou que sais-je encore, c'est plus une question de psychologie - intéressante, en plus - que de maths. Ta première intervention, à ce sujet, GG, me semble pouvoir être de comprise d'une mauvaise façon : le fait de dire qu'un exercice est "de logique" ou "de géométrie", ce n'est pas une prescription de moyens, c'est tout au plus une indication. Si on dit à une personne qu'on va lui donner un exercice de géométrie, c'est un coup de pouce sur la direction où chercher ; par contre, si on lui dit que c'est un exercice de logique, on n'est pas en train de lui tendre un piège, c'est juste moins précis.

En l'occurrence, un point clef est que pour tout ensemble fini de droites du plan, il existe un point qui n'est pas dedans. C'est, à mon avis, un point qui est subtil. Si on souvient que $\mathbb{R}$ est infini, on fait un grand bond ! Et pourtant, je trouve que cet énoncé n'a pas vraiment une saveur géométrique.

Je vais donner un exemple d'un "danger" que je vois, par ailleurs, dans cette démarche de "découpage" des maths. Le problème de Sylvester-Gallai s'énonce dans le plan et ne parle que de droites et de points. On peut donc se dire, a priori, que c'est un exercice de géométrie plane. Pourtant, pour le résoudre, on doit utiliser strictement plus que ça (par exemple, l'existence d'une distance). Ce que je veux dire par là, c'est qu'on ne peut pas savoir, avant de l'avoir résolu, si un exercice est de tel ou tel domaine des maths ; et donc, on ne peut pas dire que nizar13 se soit trompé de section.

Pour finir, je vous donne un exercice amusant que je copie-colle depuis le site de quelqu'un (je peux dire qui par MP si ça vous intéresse) :

Les punaises sont des animaux ponctuels qui vivent dans le plan. Il y a des punaises mâles et des punaises femelles. Un accouplement entre un mâle situé en un point $M$ et une femelle située en un point $F$ consiste simplement à tracer le segment $[FM]$, et cet accouplement ne peut avoir lieu que sous la condition d'intimité suivante : aucun segment tracé par un autre accouplement ne doit croiser le segment $[FM]$.

On donne une population de 5 millions de punaises femelles et 5 millions de punaises mâles, en «position générale» (jamais plus de 2 punaises sur une même droite). Prouver qu'il est possible de réaliser $5$ millions d'accouplements simultanément !

Bonjour,

Petit débriefing:
La demande initiale de nizar13 présentait deux volets:
1) L'exercice cercle contenant 2018 points
2) De quel genre est-il, quelle méthode pour les exercices de ce genre ?

Pour autant que je connaisse nizar13, c'est un(e) étudiant(e) qui essaye de s'attaquer à des problèmes de type olympiades.
Or l'originalité de ces exercices est souvent d'être multi-genres ou tans-genres si je peux me permettre.
Je rejoins donc Georges sur l'idée que l'on ne peut classer un exo qu'après l'avoir résolu, et que ce classement reste discutable.

Ma première réaction (de modérateur) a été de me demander si cette question était à sa place dans "Logique et Fondements", sachant que pour les lycéens ou les jeunes étudiants la notion de logique n'est pas encore bien précise : ils disent souvent "c'est logique" dès qu'ils ont à peu près compris.
Ensuite, j'ai essayé de faire l'exo, puisque la question me semblait intéressante et j'ai eu assez rapidement l'idée d'une récurrence.
Dans ce sens, il pouvait rester dans le tiroir L & F , mais cette récurrence s'articulait sur un argument bien géométrique qui permettait à la récurrence de fonctionner d'où ma question sur l'éventuel déplacement.

Je craignais aussi qu'un changement d'intitulé et de tiroir présentait le risque que nizar13 ne retrouve plus la discussion qu'il avait initiée.

Voici donc ma solution par récurrence, qui est bien plus maladroite et moins puissante que celle de GG. Que neige pensé aux médiatrices !
La récurrence donne une suite de cercles $(\mathcal C_n)$ telle que chaque $\mathcal C_n$ contient $n-1$ points $(P_k)_{k<n}$ et passe par un unique point $P_n$. Le cercle $\mathcal C_{n+1}$ doit contenir tous les $(P_k)_{k\leqslant n}$ et ne passer que par un seul point $P_{n+1}$ qu'il faudra éventuellement distinguer parmi plusieurs candidats $Q_i$. Ainsi le cercle $\mathcal C_{2019}$ délimitera un disque ouvert contenant $2018$ points exactement.

Amicalement. jacquot

@Chaurien,

Cela semble simple comme ça, mais comme j'ai dit je ne suis pas parvenu à le rédiger correctement.

Tout dépend de ton niveau d'exigence de rigueur.
Je propose ceci:

Lemme 1: Deux droites concourantes en O déterminent quatre secteurs angulaires (saillants) opposés deux à deux. La demi-droite opposée à une demi-droite de sommet O qui appartient à un secteur (ouvert), appartient au secteur opposé, et la droite support partage les deux autres secteurs, i.e. est la frontière de deux demi-plans qui contiennent chacun un des deux autres secteurs opposés.

Lemme 2: Tout nuage fini de points est contenu dans un disque ouvert.

Lemme 3: Tout nuage fini de points contenu dans un demi-plan ouvert est à l'intérieur d'un cercle de ce demi-plan.

Lemme 4: Étant donné deux demi-plans ouverts $\alpha $ et $\beta $ de frontière f et un nuage de n points dans $\beta $ tel qu'aucune droite joingnant deux de ses points ne soit parallèle à f, on peut construire une droite d qui soit la frontière d'un demi-plan ouvert contenant exactement k points du nuage (k de 0 à n), et telle que l'autre demi-plan contiennent les autres points du nuage ainsi qu'$\alpha $.

Lemme 5: Étant donné deux disques (fermés) séparés par une droite, i.e. qui est la frontière de deux demi-plans ouverts contenant chacun un des disques, on peut construire une autre droite concourante qui sépare également les deux disques.

Lemme 6: Soit $\Gamma $ un cercle de centre O et de rayon k, et $\Delta $ un cercle passant par O et contenu dans le disque ouvert de $\Gamma$. L'inversion f de centre O et de puissance k², qui est involutive, transforme $\Delta $ privé de O en une droite d qui est frontière de deux demi-plans ouverts dont l'un contient $\Gamma$ et l'autre est l'image de l'intérieur de $\Delta $ par f.

Théorème de nizar13 : Soit E un ensemble fini quelconque de n points du plan. Pour tout k de 0 à n, on peut construire un disque ouvert contenant exactement k points de E.

Dém (idée de Chaurien!) :
Soit $\Delta $ un cercle dont le disque ouvert contienne E, et dont l'existence est garantie par le lemme 2.
Soit O un point de $\Delta $ et k un réel supérieur au diamètre de $\Delta$. Soit $\Gamma $ le cercle de centre O et de rayon k. D'après le lemme 6, l'inversion f de centre O et de puissance k² transforme $\Delta $ privé de O en une droite d frontière d'un demi-plan ouvert $\alpha $ qui contient $\Gamma $ et d'un demi-plan ouvert $\beta $ qui contient f(E).

Garanti par le lemme 3, soit $\Lambda $ un cercle de $\beta $ dont l'intérieur contient f(E). d partage donc $\Gamma $ et $\Lambda $. D'après le lemme 5, on peut construire une droite e coupant d et séparant $\Gamma $ et $\Lambda $. Soit P leur point de concours. Nommons Pd₁ et Pd₂ les demi-droites opposées de d de sommet P, ainsi que Pe₁ et Pe₂ celles de e, de telle manière que $\Gamma $ soit dans le secteur angulaire Pd₁e₁, et $\Lambda $ dans le secteur opposé Pd₂e₂.

Soit Q un point de Pd₁ distinct de P, et R un point de Pe₂ distinct de P. Considérons maintenant toutes les droites passant par P et parallèles aux droites joignant deux points de f(E). Elles coupent le segment QR en un nombre fini de points. Soit H un point de QR distinct de tous ces points. D'après le lemme 1, la droite PH sépare $\Gamma$ et $\Lambda $. Il suit donc du lemme 4 qu'il existe une droite s parallèle à PH qui sépare un nombre arbitrare de points de f(E) et $\Gamma$.

f(s) est le cercle cherché. CQFD

Parmi ces lemmes, relativement triviaux, lesquels penses-tu mériter la rédaction d'une démonstration ?

@Georges Abitbol,
Je propose l'idée suivante : Je choisis un point O de l'enveloppe convexe des punaises qui soit hors des droites joignant deux d'entre elles. Tout droite passant par O (et ne passant pas par une punaise) partage donc les punaises en deux parties non vides. En faisant tourner une telle droite arbitraire autour de O, on amène un demi-plan sur l'autre, et s'il y a un excès de mâles dans l'un (par exemple), il se transforme en son opposé dans l'autre. Il passe donc par zéro (il ne peut changer que d'une unité à la fois) et il existe donc une droite partageant les punaises en deux groupes ayant chacun exactement autant de mâles que de femelles, que l'on peut apparier séparément.

Qu'en penses-tu ?

Oui, oui, bien sûr !

Un exemple donné par Connes dans je ne sais plus quel entretien sur F Culture :

On casse en deux morceaux une plaque de chocolat de 5 × 8 carrés. Puis on recommence jusqu'à n'avoir plus que des carrés isolés. Combien de cassures ? :-)

Tiens !... Là, ce n'est plus de la géométrie, ni de la logique, ... mais de l'arithmétique ! Encore du boulot pour toi, jacquot ! :-)

Oui, sauf qu'il n'y a pas "d'au mieux". Une plaque de n carrés de dimensions quelconques (pas forcément rectangulaire d'ailleurs) nécessite exactement n - 1 cassures en deux morceaux pour être débitée, où que soient les positions de ces cassures. C'est ça qui est rigolo. On casse la plaque de 40 carrés n'importe comment. On tombe sur 39. On se dit : tiens, c'est du hasard ? On mange les morceaux et on recommence différemment avec une deuxième plaque. Tiens, toujours 39. On veut en avoir le coeur net, et on finit à l'hôpital. Finalement on découvre la récurrence et on meurt l'âme en paix !

Bonjour à tous .

Pour le problème des punaises il y a une solution complètement évidente en utilisant l'inégalité triangulaire . On relie les mâles et les femelles n'importe comment et on considère la somme des longueurs des segments tracés . Si deux segments se coupent on les décroise et on diminue strictement la somme . Comme il y a un nombre fini de somme possible il va bien falloir s'arréter .


Domi

Effectivement, solution étonnamment simple ::o (et élégante!)

L'évidence est dans la compréhension de la preuve pas dans sa découverte :-D

Domi

@Georges Abitbol,
De rien ! J'ai l'impression qu'il y a un peu le même phénomène avec le problème des punaises. Pour le problème de Sylvester, Coxeter mentionne la démonstration de Kelly qui utilise la distance, et donne la démonstration la plus économique (est-ce le premier à le faire ?) en n'utilisant que les axiomes d'ordre du plan. Ici aussi, Domi s'appuie le caractère métrique du plan euclidien, alors que je pense que ce n'est qu'un problème d'ordre (mais je bute sur l'existence d'un point de l'enveloppe hors les droites pour adapter mon argument).

Admiration particulière pour Domi!

Bonjour à tous,

Je tente une preuve moins géométrique. Elle utilise, certes, du vocabulaire géométrique mais je pense que c'est mon incompétence qui m'y contraint.

Soit $n$ naturel.

Soient $n$ punais et $n+1$ punaises qu'on enfile aléatoirement. Dans cette brochette (supposable horizontale) il y a toujours au moins une punaise (on la dira "distinguée") à la gauche de laquelle il y a autant de punais que de punaises. A sa droite c'est bien sûr pareil.

Soient $n+1$ punais et $n+1$ punaises en position générale et $p$ un quelconque des punais. On trace un cercle de centre $p$ et on y projette radialement les $n$ autres punais et les $n+1$ punaises. On obtient un cercle où sont distingués repérés exactement $2n+1$ points (à cause de la "position générale"). Brisons-le n'importe où sauf en ces $2n+1$ points. Il devient brochette. On repère une punaise distinguée dans cette brochette.On contraint à l'accouplement cette distinguée punaise et le malheureux (?) $p$.

Les punais et punaises à gauche (sur la sus-dite brochette) de la sus-dite distinguée punaise continuent de gérer leurs désirs collectivement avec les contraintes de Georges Abitbol; de même à droite.

Amicalement
Paul

Edit: correction d'un potentielle ambiguité