Une question élémentaire

Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-13 10:36:38
Hypothèse 1 : on considère un ensemble G d'individus.
Hypothèse 2 : on considère une relation C sur GxG t.q. (a,b) appartient à C si et seulement si a connaît b.
Hypothèse 3 : La relation C est antiréflexive, symétrique, et non transitive.
Hypothèse 4 : La relation C est non vide.
Hypothèse 5 : on considère une relation M sur GxG t.q. (a,b) appartient à M si et seulement si a sert la main de b.
Hypothèse 6 : La relation C est incluse à M.

L'hypothèse 4 et l'hypothèse 6 impliquent que M est non vide.
Considérons alors un élément de la relation M. Il s'écrit sous la forme (a,b), élément de GxG.
Par l'hypothèse 3 (puisque C est symétrique), l'élément (b,a) appartient lui aussi à M.
Donc a et b sont deux éléments de G qui serrent la main à un autre élément de G.
Donc il y a toujours deux personnes qui ont serré une main.
CQFD.

EDIT: J'estime avoir répondu à la question, comme l'explique mon commentaire suivant. Toutefois, je donne une autre réponse dans le 3e commentaire, peut-être plus convaincante.
Anonyme
2015-08-13 11:31:44
Ouais mais c'est pas complet, on te demande pas est ce que au moins deux personne se sert la main, mais est ce que le nombre de personne se serrant la main est paire, pour un nombre de main sérrée impaire ^^
Apres j'ai pas vraiment compris puisque si on prend l'exemple de 3personne dans la soirée qui se sert la main entre elles :
3 personne qui se serrent la main, impaire de personnent qui serrent 2 mains, donc ça marche déjà pas
Ou alors une personne en peut pas serrer la main a plusieurs personne?
 
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-13 12:05:45
gars13:Ouais mais c'est pas complet, on te demande pas est ce que au moins deux personne se sert la main, mais est ce que le nombre de personne se serrant la main est paire, pour un nombre de main sérrée impaire ^^


Si je te disais : "Il y a toujours un truc à grignoter dans l'armoire", penserais-tu qu'il n'y en a qu'un ?
Logiquement, cette syntaxe n'est pas suffisante pour établir l'unicité de l'objet considéré.
Tikimoko Tikimoko
Zaguien
Inscrit: 2015-06-11 05:06:17
2015-08-13 12:50:15
Pandaren:

Pensez vous qu'il existe un chemin passant une et une seule fois par chacune des portes de cette maison haute en couleurs ?


le poste date et d'après ce que j'ai lu c'est impossible :'), mais du coup est-ce que ceci est recevable ? J'arrive pas à voir si j'ai oublié une porte où si j'en ai passé une deux fois XD ? Je pars de la porte bleue en bas à gauche.
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-13 13:16:54
Pandaren:Allez petit up avec cette question :

On considère un nombre fini de personnes à une soirée. Certaines se connaissent entre elles, ou sont juste polies et se sont donc serrées la main.

Que pensez vous de cette proposition : "Il y a toujours un nombre pair de personnes ayant serré un nombre impair de mains" ?


Admettons qu'il ait été question de s'interroger sur la parité du nombre exact d'individus qui auraient serré un nombre impair de mains.

Je vais prouver que la proposition est VRAIE en procédant par une preuve par induction.

Considérons un ensemble G d'individus (de cardinalité d'au moins 2, mais finie (CRUCIAL!)).
Définissons une relation non vide M sur G t.q. (a,b) appartient à M ssi a serre la main de b.
Il s'agit d'une relation symétrique et antiréflexive. (D'où la cardinalité de M est paire.)

Chaque élément de G sera représenté comme un cercle, et un trait lie deux cercles si et seulement si les deux individus que représentent ces cercles se sont serrés la main lors de la soirée (à présent terminée).

J'appelle T-impair tout cercle qui est lié exactement par un nombre impair de traits.
J'appelle T-pair tout cercle qui n'est pas T-impair.

La proposition à prouver est alors équivalente à celle suivante : "Quelle que soit la configuration des cercles et des traits qui les relient, le nombre exact de T-impairs est pair".

Notons qu'il suffit de travailler avec des configurations sans cercle non lié, puisque ceux-ci sont T-pairs.
Puisqu'une configuration se construit, et qu'à chaque étape de sa construction (i.e. ajout d'un nouveau cercle et d'un nouveau trait, ou simplement ajout d'un nouveau trait), nous avons une configuration nouvelle, il suffit de prouver que la proposition est vraie lorsque le nombre de cercles (ici et dans la suite égal au nombre de cercles liés) vaut 2, et que lorsque l'on considère une configuration quelconque avec au moins deux cercles où la proposition est vraie, elle reste vraie par passage à l'étape suivante.


PREUVE.

Cas de base.
Supposons que l'on ait la configuration suivante : deux cercles. Ils sont liés entre eux. Donc ils sont tous deux T-impairs. Le nombre exact de T-impairs est 2. Pair. La proposition est vraie.

Pas d'induction.
Supposons que l'on ait une configuration avec au moins deux cercles où la proposition est vraie.
Deux cas :

1) On dessine un nouveau cercle.
A ce stade, on a dessiné un futur nouveau T-impair.
On relie celui-ci à l'un des cercles déjà dessinés.
Si ce dernier est T-impair, alors il devient T-pair.
On a conservé ainsi le nombre de T-impairs.
Sinon, il devient T-impair.
On a ajouté ainsi 2 T-impairs au nombre de T-impairs précédent.
Comme ce dernier était pair, il est toujours pair.
La proposition reste vraie.

2) On lie deux cercles entre eux.
Si les deux sont T-pairs, alors ils deviennent tous deux T-impairs.
La parité de T-impairs est ainsi conservée.
Si les deux sont T-impairs, alors ils deviennent tous deux T-pairs.
La parité de T-impairs est ainsi conservée.
Si l'un est T-pair et l'autre T-impair, alors l'un devient T-impair et l'autre T-pair.
La parité de T-impairs est ainsi conservée.
La proposition reste vraie.

Ainsi, lorsque l'on se donne un nombre fini de cercles, et qu'on les relie comme on le souhaite, à chaque fois qu'on liera deux cercles, le nombre exact de cercles liés à un nombre IMPAIR de cercles sera TOUJOURS PAIR.
La proposition est donc vraie pour toutes les configurations (finies).

CQFD.
Anonyme
2015-08-13 14:01:57
Tikimoko:
le poste date et d'après ce que j'ai lu c'est impossible :'), mais du coup est-ce que ceci est recevable ? J'arrive pas à voir si j'ai oublié une porte où si j'en ai passé une deux fois XD ? Je pars de la porte bleue en bas à gauche.


Salut Casper !
Tikimoko Tikimoko
Zaguien
Inscrit: 2015-06-11 05:06:17
2015-08-13 16:00:49
SayitRight:
Tikimoko:
le poste date et d'après ce que j'ai lu c'est impossible :'), mais du coup est-ce que ceci est recevable ? J'arrive pas à voir si j'ai oublié une porte où si j'en ai passé une deux fois XD ? Je pars de la porte bleue en bas à gauche.


Salut Casper !


Ah mais voilà c'est ça XD il me semblait bien qu'il y avait un truc que j'avais pas vu, tellement j'avais le nez dessus :') tout va bien c'est pas du tout la honte J'invente des portes imaginaires ^^
Anonyme
2015-08-13 18:58:03
Cornflex oui mais rien avoir avec ton exemple de brioche dans l'armoire.
Tu dis il y a toujours au moins soit nb brioche supérieur a 1, ok c'est cool mais la on dit le nombre est pair et pas nb personne qui serrent la main supérieur a 2
La premiere réponse etait pas suffisante

Par contre je crois avoir compri autrement, en fait la question c'est "le nombre de personne serrant un nombre impair de main, est pair"?
Dans ce cas si je sers la main a x personne, on a x main serré pour x + 1 personne. Si x impaire, alors x + 1 paire.
en regroupant par groupe de gens se serrant la main, on a addition de chiffre pair ce qui donne un chiffre pair non?

Apres je t'avouerais que je me suis levé a 4h du mat donc sur le coup je vais pas chercher a analyser ton truc qui a l'air plus dure ^^, meme si a première vu ça avait l'air juste mais plus complexe :-P
Pandaren Pandaren
Zaguien
Inscrit: 2012-04-23 12:04:00
2015-08-13 21:09:20
Cornflexh:
Admettons qu'il ait été question de s'interroger sur la parité du nombre exact d'individus qui auraient serré un nombre impair de mains.


C'est bien la question posée, et la réponse bien que pédante et pas forcément compréhensible par tout le monde avec les termes techniques est très complète ^^ bravo.



Voici donc une nouvelle énigme : On considère une petite soirée entre amis cette fois, avec seulement 6 personnes.

Le but est de montrer qu'on peut soit trouver un groupe de 3 personnes qui se connaissent mutuellement, soit trouver un groupe de 3 personnes qui ne se connaissent pas deux à deux.
Anonyme
2015-08-13 23:01:24
Ben si il n'y a pas de groupe de 3 personne se connaissant, les personnes se connaissent maximum par 2, soit organisation:

1-personne connaît personne
2-3groupe de 2 personne se connaissant
3-groupe de 2 personne mélangé a d'autre qui ne connaissent personne

1: si personne connaît personne, ben le groupe se fait facilement avec 3 mec random de la soirée.
2: On prend une personne de chaque groupe
3: On prend un mec de chaque groupe et on complete avec des gens qui connaissent personne

J'ai bon?
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-14 01:23:50
Pandaren:Voici donc une nouvelle énigme : On considère une petite soirée entre amis cette fois, avec seulement 6 personnes.

Le but est de montrer qu'on peut soit trouver un groupe de 3 personnes qui se connaissent mutuellement, soit trouver un groupe de 3 personnes qui ne se connaissent pas deux à deux.


PREUVE.

Soit un ensemble G de 6 individus.
Chaque personne sera représentée par un cercle.
Définissons une relation R sur GxG t.q. (a,b) appartient à R ssi a ne connaît pas b (ssi le cercle qui représente a est relié en rouge au cercle qui représente b), en supposant que celle-ci est symétrique.
Définissons une relation V symétrique sur GxG t.q. V := (GxG)backslash R (c.-à-d. (a,b) appartient à V ssi a connaît b (ssi le cercle qui représente a est relié en vert au cercle qui représente b)). Celle-ci est alors elle aussi symétrique.

On a donc 6 cercles dont chacun est atteint par 5 traits de couleur dont au moins 3 sont d'une même couleur.
Notre objectif, c'est d'avoir un "triangle relationnel" d'une même couleur.

Je considère arbitrairement un des 6 cercles.
Il est relié par au moins 3 traits de même couleur.
Je considère les 3 cercles correspondants.
Si un trait de cette même couleur lie deux d'entre eux, alors on a fini.
Sinon, ils sont tous trois deux à deux liés par un trait de l'autre couleur, auquel cas on a aussi fini.

CQFD.

Autrement dit, il faut considérer arbitrairement une personne dans le groupe (n'importe laquelle).
Il y aura bien au moins 3 personnes dans le groupe qu'elle ne connaît pas OU au moins 3 personnes dans le groupe qu'elle connaît.
Les cas étant similaires, admettons qu'on soit dans le premier cas.
Si 2 de ces 3 personnes ne se connaissent pas, alors le tour est joué. (Il faut considérer ces 2-là avec la personne considérée au début.)
Si au contraire ces 3 personnes ne se connaissent pas, alors le tour est également joué. (Il faut considérer ces 3-ci.)
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-14 01:47:52
gars13:Ben si il n'y a pas de groupe de 3 personne se connaissant, les personnes se connaissent maximum par 2, soit organisation:

1-personne connaît personne
2-3groupe de 2 personne se connaissant
3-groupe de 2 personne mélangé a d'autre qui ne connaissent personne

1: si personne connaît personne, ben le groupe se fait facilement avec 3 mec random de la soirée.
2: On prend une personne de chaque groupe
3: On prend un mec de chaque groupe et on complete avec des gens qui connaissent personne

J'ai bon?


Et si 4 d'entre eux connaissent 2 personnes, et les 2 autres, 3 personnes ?
Pandaren Pandaren
Zaguien
Inscrit: 2012-04-23 12:04:00
2015-08-14 13:15:51
Cornflexh:

Autrement dit, il faut considérer arbitrairement une personne dans le groupe (n'importe laquelle).
Il y aura bien au moins 3 personnes dans le groupe qu'elle ne connaît pas OU au moins 3 personnes dans le groupe qu'elle connaît.
Les cas étant similaires, admettons qu'on soit dans le premier cas.
Si 2 de ces 3 personnes ne se connaissent pas, alors le tour est joué. (Il faut considérer ces 2-là avec la personne considérée au début.)
Si au contraire ces 3 personnes ne se connaissent pas, alors le tour est également joué. (Il faut considérer ces 3-ci.)


Bon les mecs, il est mignon et plutôt doué vous attendez quoi ?
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-14 16:02:08
J'attends la prochaine avec impatience.
Anonyme
2015-08-14 18:33:57
Cornflexh:
gars13:Ben si il n'y a pas de groupe de 3 personne se connaissant, les personnes se connaissent maximum par 2, soit organisation:

1-personne connaît personne
2-3groupe de 2 personne se connaissant
3-groupe de 2 personne mélangé a d'autre qui ne connaissent personne

1: si personne connaît personne, ben le groupe se fait facilement avec 3 mec random de la soirée.
2: On prend une personne de chaque groupe
3: On prend un mec de chaque groupe et on complete avec des gens qui connaissent personne

J'ai bon?


Et si 4 d'entre eux connaissent 2 personnes, et les 2 autres, 3 personnes ?


Oh oui certe j'avais oublié ça,
ben appelons B ceux qui en connaissent 3, et A ceux qui en connaissent 2
1: Les B se connaissent pas, ils connaissent 3 A, soit 2 A sont connus pas les 2 B, leurs seuls connaiscance sont les deux B. Ces deux A + un autre A = 3 personne qui se connaissent pas.
2: Les B se connaissent, aucun A n'est connu par les 2 B. On prend les A1 = les deux A qui connaissent B1 + un A2 et ça marche
3:Les B se connaissent, un A est connu, pareil en plus facile car on peut prendre le A connu par les deux déjà

Bon apres c'est plus la démonstration de l'abscence de contre exemple, ce qui est pas tres mathématique et pas du tout rigoureux mais dans un petit truc comme ça comme le nombre de cas est assez limité ( ouais je sais j'en ai oublié un mais n'importe ), ça peut se montrer assez facilement sans chercher a faire de raisonnement vraiment mathématiques . Au pire on fait un shéma et ça démontre que ça marche dans tout les cas, si on arrive a trouver tout les cas of course
Pandaren Pandaren
Zaguien
Inscrit: 2012-04-23 12:04:00
2015-08-14 21:35:01
Cornflexh:J'attends la prochaine avec impatience.


Un petit panda décide de marcher 10 km vers le sud. Il fait ensuite 10 km vers l'est et 10 km vers le nord. Il constate alors qu'il est revenu à son point de départ.

Ou se trouve-t-il sachant qu'il n'est pas au pôle nord ?
Anonyme
2015-08-14 21:49:34
Pandaren:
Cornflexh:J'attends la prochaine avec impatience.


Un petit panda décide de marcher 10 km vers le sud. Il fait ensuite 10 km vers l'est et 10 km vers le nord. Il constate alors qu'il est revenu à son point de départ.

Ou se trouve-t-il sachant qu'il n'est pas au pôle nord ?


S'il n'est pas au pôle Nord, on va prendre la latitude où il est possible de faire le tour de la Terre en dix kilomètres, on a deux cas (un par pôle), mais on exclus celui du Pôle Nord car ça ne colle pas. Maintenant, si on prend le parallèle de longueur dix kilomètres, on peut partir d'un point situé dix km au Nord de ce cercle, ainsi, si on va dix km au sud on tombe sur ce cercle, dix km à l'Est on fait le tour et on se retrouve au même point, dix km au Nord on se retrouve au point de départ. Donc la réponse c'est le parallèle dix km au Nord de celui près du pôle sud qui fait dix km de longueur.
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-15 00:27:49
Sur une latitude ? 10 km au nord de celle qui mesure 10 km de circonf?rence dans l'h?misph?re sud.
Cornflexh Cornflexh
Zaguien
Inscrit: 2012-10-07 04:10:14
2015-08-15 00:30:40
Mon ordi n'veut plus s'allumer, grr.