Mathématiciens

par **lapras** » 15 Mai 2009, 19:45

Bonsoir,
Soit n naturel > 0. On considère trois pays et dans chacun d'eux n mathématiciens. On sait que chacun des mathématiciens d'un pays donné connaît au moins n+1 mathématiciens appartenant à la réunion des deux autres pays.

Montrer qu'il existe trois mathématiciens se connaissant deux à deux.
lapras :happy2:

par **melreg** » 19 Mai 2009, 09:13

Si personne ne répond je pense que c'est parce que personne n'ose s'y risquer... cette énigme est succulente!
Ca sent la théorie des graphes... non?

par **nodjim** » 20 Mai 2009, 05:21

J'ai une solution, pour cette fois très propre et dont je suis assez content. Je la rédigerai ce soir ou demain. :id:

par **nodjim** » 20 Mai 2009, 16:56

Soient les 3 arêtes a, b et c communes à un même sommet d'un cube.
a, b et c sont découpées en n segments 1 à n, de même que les faces du cube ab, ac et bc sont décorées de n*n cases de longueur ce segment.
A un segment "ai" correspond donc les n cases alignées d'abscisse ai de la face ab et les n cases alignées d'abscisse ai de la face ac.
Les arêtes a, b et c sont les pays. Les segments ai, bi, ci sont les mathématiciens.
Quand on établit une relation de connaissance entre 2 mathématiciens, on colle un jeton sur la case correspondante.
Par exemple, un jeton en a3b5 est une relation de connaissance entre le mathématicien 3 du pays a et le mathématicien 5 du pays b.

Quand on a cette double relation: a3b5 et b5c4, la relation a3c4 conduit à une triangulaire, ce qu'il faut en principe éviter.

D'après l'énoncé, à chaque ai correspondent n+1 jetons, répartis entre les 2 faces ab et ac.
A chaque segment, comme le cube à n cases de coté, et qu'il doit y avoir n+1 jetons, il existe au moins 1 jeton sur chaque face contiguë à ce segment.
Donc sur la face ab, il y a au moins 1 jeton au regard de chaque segment de a.
Et aussi sur la face bc, il y a au moins un jeton au regard de chaque segment de c.
Sur la face ac, comme il y a aussi forcément au moins 1 jeton, celui ci arrive en triangulaire des jetons déja présents sur les faces ab et bc.

CQFD

par **Imod** » 20 Mai 2009, 18:10

nodjim a écrit:Sur la face ac, comme il y a aussi forcément au moins 1 jeton, celui ci arrive en triangulaire des jetons déja présents sur les faces ab et bc.

Sorry , I don't understand :doh:

Imod

par **nodjim** » 20 Mai 2009, 18:51

Pas étonnant, moi qui étais content de ma démo, elle est défaillante.. :cry:
Car je ne démontre pas que les jetons sur ab et bc ont le même b pour avoir la triangulation.
C'est donc plus compliqué que ça...

par **Imod** » 20 Mai 2009, 22:13

nodjim a écrit:Pas étonnant, moi qui étais content de ma démo, elle est défaillante..

Pour qui ne propose rien , la critique est facile :zen: Pour ma défense j'ai peu de temps libre en ce moment .

Imod

par **nodjim** » 21 Mai 2009, 19:38

Cette nouvelle version a l'air de mieux marcher, bien qu'elle soit assez peu différente de la 1ère.
Bonne lecture

Soient les 3 arêtes a, b et c communes à un même sommet d'un cube.
a, b et c sont découpées en n segments 1 à n, de même que les faces du cube ab, ac et bc sont décorées de n*n cases de longueur ce segment.
A un segment "ai" correspond donc les n cases alignées d'abscisse ai de la face ab et les n cases alignées d'abscisse ai de la face ac.
Les arêtes a, b et c sont les pays. Les segments ai, bi, ci sont les mathématiciens.
Quand on établit une relation de connaissance entre 2 mathématiciens, on colle un jeton sur la case correspondante.
Par exemple, un jeton en a3b5 est une relation de connaissance entre le mathématicien 3 du pays a et le mathématicien 5 du pays b.

Quand on a cette double relation: a3b5 et b5c4, la relation a3c4 conduit à une triangulaire, ce qu'il faut en principe éviter.

D'après l'énoncé, à chaque ai correspondent n+1 jetons, répartis entre les 2 faces ab et ac.
On peut donc dénombrer le nombre minimum de jetons: n+1 pour chaque segment, 3n segments fois n+1, mais il faut diviser par 2, car on compte à chaque fois 2 faces donc 3n(n+1)/2.

A chaque segment, comme le cube à n cases de coté, et qu'il doit y avoir n+1 jetons, il existe au moins 1 jeton sur chaque face contiguë à ce segment.
Donc sur la face ab, il y a au moins 1 jeton au regard de chaque segment de a.
Et aussi sur la face bc, il y a au moins un jeton au regard de chaque segment de c.
Et aussi pour la 3ème face.
Supposons maintenant 1 jeton en a3b2. Sur la face bc, ligne b2, et sur la face ac, ligne a3, il ne peut pas y avoir 2 jetons sur la même ligne c. Car s'il y avait 1 jeton c5b2 et c5a3, on aurait une triangulaire c5b2a3. Donc le nombre max de jetons sur b2c + a3c est de n.
Comme on a dit que sur une face donnée, il y avait au moins 1 jeton sur chaque ligne et chaque colonne, les 2 autres faces totalisent au maximum n² jetons.
En comptant le nombre total de jetons sur l'ensemble des 3 faces, on arrive à 3n²/2.
Ce qui est en contradiction avec le nombre minimal indiqué au départ de 3n(n+1)/2.

CQFD

par **nodjim** » 22 Mai 2009, 00:17

Cette version devrait mieux marcher.

Soient les 3 arêtes a, b et c communes à un même sommet d'un cube.
a, b et c sont découpées en n segments 1 à n, de même que les faces du cube ab, ac et bc sont décorées de n*n cases de longueur ce segment.
A un segment "ai" correspond donc les n cases alignées d'abscisse ai de la face ab et les n cases alignées d'abscisse ai de la face ac.
Les arêtes a, b et c sont les pays. Les segments ai, bi, ci sont les mathématiciens.
Quand on établit une relation de connaissance entre 2 mathématiciens, on colle un jeton sur la case correspondante.
Par exemple, un jeton en a3b5 est une relation de connaissance entre le mathématicien 3 du pays a et le mathématicien 5 du pays b.

Quand on a cette double relation: a3b5 et b5c4, la relation a3c4 conduit à une triangulaire, ce qu'il faut en principe éviter.

D'après l'énoncé, à chaque ai correspondent n+1 jetons, répartis entre les 2 faces ab et ac.

Supposons un jeton en a3b2. En a3c et cb2, les jetons ne peuvent avoir la même abscisse c, sinon il y aurait triangulaire.
Par exemple, si jeton en a3c5 et b2c5, triangulaire a3c5b2.
Donc le nombre de jetons en a3c+cb2 est au maximum n. card(a3c)+card(cb2)<=n.

Supposons maintenant n=10 donc n+1=11.
Supposons sur la ligne a3b cinq jetons. POur avoir 11 jetons pour a3, il en faut au moins 6 pour a3c.
Si jeton en a3b2, on ne peut mettre au plus que 10-6=4 jetons sur la ligne b2c. Comme il faut 11 jetons pour b2, il en faut au moins 7 sur ab2.
Je passe de 6 jetons pour a3c à 7 jetons pour ab2, c'est à dire 1 de plus.
En continuant ce raisonnemment à partir de b2c (4jetons) on passera de 7 à 8 jetons. etc.
Arrivé à 10, on aura une impossibilité. il faudra soit abandonner n+1 jetons pour un segment, soit autoriser une triangulaire.

par **nodjim** » 22 Mai 2009, 18:12

Plus simple, maintenant que la solution est trouvée:
Soit 3 pays A, B et C et 20 Aliens (habitants de A), 20 Biens et 20 Ciens.
1 Alien a 21 relations, 10 avec B et 11 avec C.
N'importe lequel de ces 10 B ne peut avoir de relations avec l'un des 11 C, sinon il y aurait relation triangulaire ABC.
Donc l'un des 10 B a au maximum 9 relations (20-11) avec C, et donc au minimum 12 avec A, pour faire 21.
l'un des 9 C a donc au maximum 20-12=8 relations avec C et donc au minimum 13 avec A.
Etc...
Il est évident qu'on va arriver à une aberration.

par **Imod** » 23 Mai 2009, 21:10

A première vue je ne suis toujours pas convaincu , mais bon , l'avis de l'auteur ?

Imod

par **lapras** » 24 Mai 2009, 08:45

L'auteur n'a pas de solution à vous proposer.

par **nodjim** » 24 Mai 2009, 09:08

Imod a écrit:A première vue je ne suis toujours pas convaincu , mais bon , l'avis de l'auteur ?

Imod

Bonjour.
Il faudrait tout de même nous dire ce qui te chagrine. ça a l'air assez simple, non ?

par **Imod** » 24 Mai 2009, 11:55

nodjim a écrit:Bonjour.
Il faudrait tout de même nous dire ce qui te chagrine. ça a l'air assez simple, non ?

Assez simple si tu veux mais comme tu laisses beaucoup de pointillés à compléter , en première lecture on ne comprend pas grand chose :doh: Pourquoi 20 puis pourquoi 10 et 11 , ...

Mais bon , et c'est l'essentiel , ton idée est la bonne :zen:

Une autre façon de le dire . Par l'absurde , on choisit

l'un des mathématiciens les plus sectaires ( il a le plus possible de relations dans le même pays ) . On note

son pays et

le pays dans lequel il choisit prioritairement ses amis .

a

amis dans

et au moins

dans

avec

et

maximal . Aucun des amis de

dans

( il en existe au moins 1 ) n'est en relation avec les amis de

dans

donc chacun d'entre eux a au plus

relations dans

donc au moins

dans

: contradiction .

Imod

par **nodjim** » 24 Mai 2009, 13:23

Imod a écrit:Assez simple si tu veux mais comme tu laisses beaucoup de pointillés à compléter , en première lecture on ne comprend pas grand chose :doh: Pourquoi 20 puis pourquoi 10 et 11 , ...

Mais bon , et c'est l'essentiel , ton idée est la bonne :zen:

Une autre façon de le dire . Par l'absurde , on choisit l'un des mathématiciens les plus sectaires ( il a le plus possible de relations dans le même pays ) . On note son pays et le pays dans lequel il choisit prioritairement ses amis . a amis dans et au moins dans avec et maximal . Aucun des amis de dans ( il en existe au moins 1 ) n'est en relation avec les amis de dans donc chacun d'entre eux a au plus relations dans donc au moins dans : contradiction .

Imod

Oui, c'est encore plus court ! :++:

Mathématiciens

Mathématiciens

Qui est en ligne