Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 24-06-2011 20:08:48

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Pour ceux qui ne sont pa nuls. 3

Tirée des olympiades smile

Dans un plan on donne [latex]n[/latex] points ([latex]n \ge 4[/latex]). On suppose que la distance entre deux quelconques de ces points est un entier.
Montrer qu'au moins un sixième de ces [latex]C_n^2 [/latex] distances sont divisible par 3.

A tous et surtout à daftpunk bonne chance, ce n'est pas facile. J'ajouterai des indices si besoin.

Merci à Halloduda de m'avoir fait corriger une énorme erreur. Maintenant c'est bon.

Avec plaisir j'espère, Shadock wink



Annonces sponsorisées :

"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
  • |
  • Répondre

#0 Pub

 #2 - 25-06-2011 17:41:02

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Pour ceux qui ne sont pas nuls.. 3

Indice 1 : Spoiler : [Afficher le message] Supposez l'exercice résolu
pour n = 4 et fait le calcul pour n points. 


Indice 2 aide dans le cas général : Spoiler : [Afficher le message]
Au total combien y a t-il de distances entières ?
Une paire de point {A,B} apparaît dans combien de  quadruplets ? Ce nombre de quadruplets donne le nombre de fois maximale que chaque distance est comptée. Je vous laisse deviner la suite... wink


J'ajouterai un indice tous les 24h

Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #3 - 27-06-2011 00:05:02

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Poour ceux qui ne sont pas nuls. 3

Pas d’intéressé ? sad


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #4 - 27-06-2011 00:34:54

karibou
Habitué de Prise2Tete
Enigmes résolues : 48
Messages : 26

Pour ceux qui e sont pas nuls. 3

Je bugue sur l'énoncé:

On suppose que la distance entre deux quelconques de ces points est un entier.

est ce que ça veut dire

"il existe deux points a et b tels que d(a,b) soit un entier"

ou "quelquesoit deux points a et b alors d(a,b) est un entier"


[url=http://www.deathnote-lejeu.com/?player=karibou] Death note-le jeu[/url]

 #5 - 27-06-2011 00:46:20

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Pour ceux qui ne sont pas nlus. 3

On suppose que la distance entre deux quelconques de ces points est un entier.

Cela veut dire que quelque soit a et b deux point alors [latex]||\vec{ab}||[/latex] ou [latex]||\vec{ba}||[/latex] soit un entier.

Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #6 - 27-06-2011 02:12:34

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1987
Lieu: Paris

Pour cexu qui ne sont pas nuls. 3

shadock a écrit:

Cela veut dire qu'il existe au moins deux points a et b tels que [latex]||\vec{ab}||[/latex] ou [latex]||\vec{ba}||[/latex] soit un entier.

Ca ne veut pas plutôt dire :

Quels que soient deux points a et b, [latex]||\vec{ab}||[/latex] ou [latex]||\vec{ba}||[/latex] est un entier.

Parce que sinon les 4 sommets d'un carré de côté 1 répondent à ta définition, et pourtant aucune des distances n'est divisible par 3 ...

 #7 - 27-06-2011 02:28:57

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Pour ceux qui ne sont pas nul. 3

Oui L00ping007, je ne vois pas trop la subtilité ! Et je rappelle que c'est tirée des olympiades et que la correction elle m'arrache les yeux, mais je trouvais l'énigme intéressante.

Mais tu peux t'en sortir sans faire comme tu dis. Prends 4 points quelconques dans le plan mais évite les figures géométriques smile Je pense que c'est plus simple ainsi.

Si besoin de plus de précisions ma boîte à MP est grande ouverte.

Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #8 - 27-06-2011 02:32:50

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1987
Lieu: Paris

pour ceux qui ne sony pas nuls. 3

La subtilité réside dans le fait que dans le premier cas, il y a au moins 2 points dont la distance entre eux est entière (il peut n'y en avoir qu'un). Dans le second cas, toutes les distances sont entières.
C'est juste une subtilité de langage mathématique sur les "il existe" et "quel que soit" smile

Pour le problème, j'ai essayé d'y réfléchir vite fait, mais effectivement il n'a pas l'air simple !

 #9 - 28-06-2011 17:29:14

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

pour ceux qui ne sobt pas nuls. 3

Finalement l'étape la plus épineuse est de démontrer que si les points ne sont pas alignés, ils sont forcément en nombre limité...

 #10 - 01-07-2011 16:23:33

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Pour ceux qqui ne sont pas nuls. 3

Je me doutais que c'étais vraiment très difficile. Voici leur solution :

Première partie

Commençons par remarquer que tout se ramène au cas [latex]n = 4[/latex]. Supposons l'exercice résolu pour [latex]n = 4[/latex] et donnons-nous [latex]n[/latex] points dans le plan vériant les conditions de l'énoncé. On sait que chaque choix de quatre points parmi les [latex]n[/latex] retenus détermine au moins une distance entière. On obtient [latex]\binom{n}{4}[/latex] distances entières, mais bien sûr chacune d'entre elles peut-être comptée plusieurs
fois. Cependant, une paire de points {A,B} apparaît dans exactement [latex]\binom{n-2}{2}[/latex] quadruplets, et donc chaque distance entière est comptée au plus [latex]\binom{n-2}{2}[/latex] fois. Au finall, on trouve au moins [latex]\frac{\binom{n}{4}}{\binom{n-2}{2}}=\frac{1}{6}\binom{n}{2}[/latex] distances entières comme on le souhaite.

Deuxième partie

Reste donc à traiter le cas où [latex]n=4[/latex]. Notons A, B, C et D les quatre points et supposons qu'ils se répartissent comme sur la figure ci-dessous :
http://img4.hostingpics.net/pics/705531points.png

On a les relations d'Al-Kashi :
[TeX]BC^2=b^2+c^2-2bc\text{ }cos(\alpha)[/TeX]
[TeX]CD^2=c^2+d^2-2cd\text{ }cos(\beta)[/TeX]
[TeX]BD^2=b^2+d^2-2bd\text{ }cos(\alpha+\beta)[/TeX]
Elles impliquent que l'on peut écrire : [latex]cos(\alpha)=\frac{x}{D}[/latex], [latex]cos(\beta)=\frac{y}{D}[/latex], [latex]cos(\alpha+\beta)=\frac{z}{D}[/latex] avec [latex]x,y,z \in \mathbb{N}[/latex] et [latex]D=2bcd[/latex]

On raisonne à présent par l'absurde en supposant qu'aucune des distances
n'est multiple de 3. Alors [latex]b^2 \equiv c^2 \equiv d^2 \equiv 1[/latex](mod 3) et par les relations précédentes, on obtient [latex]dx \equiv by \equiv cz \equiv 1[/latex](mod 3).

On utilise à présent la relation qui relie les cosinus. Elle donne :
[latex]Dz=D^2*cos(\alpha+\beta)=D^2cos(\alpha)cos(\beta)-D^2sin(\alpha)sin(\beta)=xy-D^2sin(\alpha)sin(\beta)[/latex] d'où on déduit : [latex]A=D^2sin(\alpha)sin(\beta)=xy-Dz=xy-2bcdz \equiv xy+bd[/latex] (mod 3)

En particulier [latex]A^2 \equiv x^2 y^2 + b^2 d^2 \equiv 1[/latex] (mod 3). Mais on a d'autre part [latex]D^2sin^2(\alpha)=D^2(1-cos^2(\alpha))=D^2(D^2-z^2) \equiv 0[/latex] (mod 3) ce qui implique [latex]A^2 \equiv 0[/latex](mod 3) et est donc incompatible avec ce que l'on a trouvé précédemment. Ceci constitue notre contradiction et termine l'exercice.

A une prochaine fois avec quelque chose de plus ludique smile
Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete