Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Logiques » Les 97 tableaux ! Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=gasole]J'ai fait une preuve par l'absurde, qui m'a mené à construire une suite [b]strictement[/b] croissante de graphes inclus dans le graphe total, d'où une contradiction puisque ce dernier est fini. Intéressant en tout cas ! Merci. Ça vient d'où ? [u]Notations :[/u] Soit [latex]P=(p_1,...,p_n)[/latex] l'ensemble des personnes, [latex]T=(t_1,...,t_{97})[/latex] celui des tableaux. On note [latex]<p_i,t_j>[/latex] si "[latex]p_i[/latex] a vu [latex]t_j[/latex]" et [latex][p_i,t_j][/latex] sinon. On note [latex]N(p)[/latex] l'ensemble des [u]tableaux[/u] Non vus par [latex]p[/latex], et [latex]V(t)[/latex] l'ensemble des [u]personnes[/u] qui ont Vu [latex]t[/latex]. Tout ça donne un graphe (bipartite) non-orienté : [latex]G=(P,T,U=N\cup V)[/latex]. [u]Hypothèses du problème[/u] : i) [latex]\forall p\in P: N(p)\neq \emptyset[/latex] (personne n'a vu tous les tableaux) ii) [latex]\forall t\in T: V(t)\neq\emptyset[/latex] (tous les tableaux ont été vus) iii) (par l'absurde) : [latex]\not\exist p,p'\in P,t,t'\in T: p\in V(t)\wedge p'\in V(t')\wedge t'\in N(p)\wedge t\in N(p')[/latex] [u]Définition de la suite de graphes croissants[/u] : Par récurrence, on définit [latex]G_i=(P_i,T_i,N\cup V)[/latex] et on assure par construction que chaque [latex]G_i\subset G[/latex] et vérifie l'invariant : [latex]\Phi(i)=\forall j\in\{1,..,i\}: (\forall k\in\{1..j-1\}: [p_j, t_k]\wedge \forall k\in\{j..i\}: <p_j, t_k>)[/latex] En particulier, dans [latex]G_i[/latex], personne n'a vu [latex]t_i[/latex]. [u]Initialisation de la définition[/u] : On commence avec [latex]G_1[/latex]: soit [latex]p_1\in P[/latex] ([latex]P[/latex] est non-vide) et soit [latex]t_1\in N(p_1)[/latex] (un tel [latex]t_1[/latex] existe d'après ii), soit alors [latex]G_1=(\{p_1\},\{t_1\},N\cup V)[/latex], on vérifie facilement que [latex]G_1[/latex] vérifie [latex]\Phi(1)[/latex]. [u]Étape de récurrence[/u] : Hypothèse de récurrence : [latex]G_i[/latex] satisfait [latex]\Phi(i)[/latex] Or [latex]V(t_i)[/latex] ne peut être dans [latex]P_i[/latex] sinon contradiction avec [latex]\Phi(i)[/latex]. Soit donc [latex]p_{i+1}\in V(t_i)[/latex]. On vérifie [b](1)[/b] que [latex]\forall t_j\in T_i: <p_{i+1},t_j>[/latex], donc [latex]N(p_{i+1})\neq \emptyset[/latex]. Soit [latex]t_{i+1}\in N(p_{i+1})[/latex], on l'a vu [latex]t_{i+1}\not\in T_i[/latex] c'est donc un nouveau tableau à considérer. On vérifie [b](1)[/b] que [latex]\forall p_j\in P_i: [p_j,t_{i+1}][/latex] On pose [latex]P_{i+1}=P_i\cup\{p_{i+1}\}[/latex] et [latex]T_{i+1}=T_i\cup\{t_{i+1}\}[/latex] et [latex]G_{i+1}=(P_{i+1},T_{i+1},N\cup V)[/latex] et on conclut que : - [latex]G_i\subset G_{i+1}\subset G[/latex] - [latex]G_{i+1}[/latex] vérifie [latex]\Phi(i+1)[/latex] : donc on peut recommencer, ad nauseam... Or [latex]G[/latex] étant fini, on aboutit à une contradiction. [b](1)[/b] je zappe les détails mais l'idée est que sinon, on trouverait le quadruplet [latex]p,p',t,t'[/latex] qu'on suppose ne pas exister.[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez (numériquement) à la petite énigme suivante : Dans une course, vous doublez le 31ème, en quelle position êtes-vous ? Retour Résumé de la discussion Azdod 30-01-2011 22:56:41 Une groupe de personnes de nombre [latex]n[/latex] ont visité une musée qui comporte 97 tableaux ! On suppose que tous les tableaux ont été vus et qu'il n'existe pas une personne qui a vu tous les tableaux à la fois . Montrez logiquement qu'il existe deux personnes : P1 et P2 et deux tableaux T1 et T2 tels que P1 a vu T1 et n'a pas vu T2 ;et P2 qui a vu T2 et n'a pas vu T1 . Bonne chance ! 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