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 - 30-01-2011 22:56:41

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

kes 97 tableaux !

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 !



Annonces sponsorisées :

"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"
  • |
  • Répondre

#0 Pub

 #2 - 31-01-2011 03:11:44

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Les 97 tablleaux !

J'ai fait une preuve par l'absurde, qui m'a mené à construire une suite strictement 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ù ?

Notations : 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 tableaux Non vus par [latex]p[/latex], et [latex]V(t)[/latex] l'ensemble des personnes qui ont Vu [latex]t[/latex].

Tout ça donne un graphe (bipartite) non-orienté : [latex]G=(P,T,U=N\cup V)[/latex].


Hypothèses du problème :
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]


Définition de la suite de graphes croissants :
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 :
[TeX]\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>)[/TeX]
En particulier, dans [latex]G_i[/latex], personne n'a vu [latex]t_i[/latex].

Initialisation de la définition :
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].

Étape de récurrence :
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 (1) 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 (1) 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.

(1) 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.

 #3 - 31-01-2011 14:01:28

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Le s97 tableaux !

Azdod, tu as une solution simple ne faisant pas appel à un résultat "connu" ?

 #4 - 31-01-2011 14:05:38

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Les 97 tableau x!

gasole : je crois que c'est possible avec le denombrement ! ta demonstration est géniale !


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #5 - 31-01-2011 14:28:20

debutant1
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 116

Les 97 tableax !

soit p1 l"ensemble des personnes ayant vus t1.

une personne de p1 n'a pas vu t2

soit p2 l'ensemble des admirateurs de t2.

si la proposition est fausse p2 est inclus dans p1.

on recommence avec tous les tableaux non vus par des personnes de p1 et conclusion, tous les ensembles pn sont donc inclus dans p1.

comme tous les tableaux sont vus par au moins une personne ,on voit que tous le monde appartient à t1. ce qui est contraire à l’hypothèse. donc la proposition est juste pour au moins une personne.

 #6 - 31-01-2011 14:31:17

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Les 9 7tableaux !

@azdod : ... malgré quelques abus de notation à des fins d'allègement smile

mais où as-tu trouvé ça ? je m'en resservirai et mes étudiants vont te maudire smile

 #7 - 31-01-2011 14:36:42

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Les 97 tbleaux !

big_smile Lol dans un concours des olympiades des maths que j'ai deja passé ! mais dommage que je n'ai pas réussi a la résoudre ce jour là sad


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #8 - 31-01-2011 15:31:30

logan
Passionné de Prise2Tete
Enigmes résolues : 47
Messages : 90

Les 97 tableauxx !

Bon ben moi j'utiliserais bien un raisonnement par récurrence

Au niveau 1 (ie. deux personnes)
- On sait qu'autant des deux n'a vu tous les tableaux
- Que tous les tableaux ont été vu
-> chacun des visiteur n'a pas vu au moins un tableau et ça ne peut pas être le même --> la condition est respecté

Faisons l'hypothèse que c'est vrai pour N personnes, est ce vrai pour N+1 personnes ?
Si vrai au niveau N on a un couple (Arnold et Willy) de deux personnes qui vérifié la condition. Avec une personnes en plus (un retardataire LOL) on aura toujours le même couple de personne (toujours Arnold et Willy) pour qui la condition est respectée.

Voila voila (je ne suis pas trop sûr de moi mais bon)

 #9 - 31-01-2011 17:05:23

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

led 97 tableaux !

Une petite démo par l'absurde:

Alors supposons par l'absurde que qu'il n'existe pas 2 personnes P1 et P2 et deux tableaux T1 et T2 tels que P1 a vu T1 et pas T2 et P2 a vu P2 mais pas P1.
Soit <= la relation d'ordre sur l'ensemble des personnes telle que:
Si P1 et P2 deux personnes telles que P1<=P2, alors P2 a vu (au moins) tous les tableaux qu'a vu P1.
Grâce à ce qu'on a supposé par l'absurde, <= est une relation d'ordre totale.
Il existe donc dans l'ensemble fini des personnes un élément maximal pour <=.
Comme tous les tableaux ont été vus, l'élément maximal a vu tous les tableaux. Contradiction!

Ainsi 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 .

 #10 - 31-01-2011 17:50:51

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

les 97 tablezux !

Tant que chaque tableau a été vu par au moins deux personnes, je vire une personne.
Au bout d'un moment, au moins un tableau T1 n'a été vu que par une seule personne P1.
Cette personne n'a pas pu vu au moins un autre tableau T2 qui a été vu par une des autres personnes restantes P2.

 #11 - 31-01-2011 18:53:00

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Les 97 tablaux !

http://www.prise2tete.fr/upload/gwen27-ensembles.jpg

Premier cas possible: je trouve deux personnes ayant vu des tableaux différents l'un de l'autre ou bien deux personnes ayant vu des tableaux en commun mais pas tous. ( voir les deux premiers dessins) Alors, il est facile de trouver T1 et T 2.

Imaginons que ce ne soit pas le cas... Alors chacun des n visiteurs appartient à une des deux autres configurations.

Second cas possible donc: L'ensemble des tableaux vu par P1 comprend l'ensemble des tableaux vus par P2 ( ou le comprend exactement ).
Dans ce cas, il existe une personne qui a vu le plus de tableaux Pn Mais dans cette configuration, soit Pn a vu tous les tableaux, soit tous les tableaux n'ont pas été vus : cas impossible.

Il existe donc au moins deux personnes correspondant au premier cas étudié.

 #12 - 31-01-2011 19:16:39

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

les 97 tabkeaux !

bravo à tous big_smile chacun a démontré de sa façon encore un bravo smile


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #13 - 01-02-2011 19:50:09

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

les 97 tavleaux !

Je vais essayer... Même si encore une fois je trouve que j'ai fait bien compliqué.
Pour l'instant je ne me préoccupe pas de la valeur de n.

Je prends le tableau T1. Il a été vu au moins une fois, notons P1 une des personnes qui l'a vu.
P1 n'a pas vu tous les tableaux, donc il existe T2 tableau que P1 n'a pas vu.
Et comme T2 a été vu au moins une fois, il existe P2 qui a vu T2

Maintenant, 2 possibilités :
- P2 n'a pas vu T1, et on a trouvé nos P1,P2,T1,T2
- P2 a vu T1

C'est là que j'utilise un tableau qui prend en entrée les tableaux et les personnes, et un 1 signifie que P a vu le tableau T, un 0 le contraire :

      T1  T2
P1   1    0
P2   1    1

On continue : P2 n'a pas vu tous les tableaux, donc il existe T3 que P2 n'a pas vu

      T1  T2  T3
P1   1    0
P2   1    1    0
Si P1 a vu T3, on conclut avec P1,P2,T2,T3
Si P1 n'a pas vu T3, alors T3 n'a été vu ni par P1, ni par P2. Mais comme il a été vu au moins une fois, on a une P3 qui a vu T3
Si P3 n'a vu T1 (ou pas vu T2), on conclut avec P1 (ou P2), T1 (ou T2), P3, T3
Reste donc le cas où P3 a vu et T1 et T2

      T1  T2  T3
P1   1    0    0
P2   1    1    0
P3   1    1    1

De la même manière, il existe T4 que P3 n'a pas vu

      T1  T2  T3  T4
P1   1    0    0   
P2   1    1    0
P3   1    1    1    0
On peut conclure sauf si T4 n'a été vu par aucun des P1,P2,P3
On se retrouve alors avec
      T1  T2  T3  T4
P1   1    0    0    0
P2   1    1    0    0
P3   1    1    1    0

On itère le processus, jusqu'à épuiser soit les tableaux soit les n personnes
Si n >= 97
       T1  T2  T3  T4  ...  T97
P1    1    0    0    0  ...    0
P2    1    1    0    0  ...    0
P3    1    1    1    0  ...    0
...    ...  ...   ...   ...  ...   ...
P96  1    1    1    1  ...    0
P97                              1
Comme P97 ne peux pas avoir tout vu, il y a un tableau qu'il n'a pas vu, Tx, et on peut conclure avec Px,P97,Tx,T97

Si n < 97
       T1  T2  T3  T4  ...  Tn+1
P1    1    0    0    0  ...   
P2    1    1    0    0  ...   
P3    1    1    1    0  ...   
...    ...  ...   ...   ...  ...   ...
Pn    1    1    1    1  ...    0
Comme Tn+1 doit être vu, c'est forcément par un Px (il ne reste plus personne d'autre qui peut avoir vu Tn+1), et on conclut avec Px,Tx+1,Pn,Tn+1


Je ne me sers jamais de la valeur 97, donc j'imagine qu'il y a une astuce ...

 #14 - 01-02-2011 21:41:06

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

lzs 97 tableaux !

Traduction de l'énoncé :
(1) Pour tout tableau Ti, il existe au moins une personne Pj telle que Pj a vu Ti.
(2) Pour toute personne Pm, il existe au moins un tableau Tn tel que Pm n'a pas vu Tn.

Faisons un démonstration par récursion...

Et puis non, je crois qu'il y a plus simple : parlons d'ensembles.

(1) U Tj (union des tableaux vus par chacun) = E (ensemble des tableaux)
(2) Pour tout Pj, Tj (ensemble des tableaux qu'il a vus) <> E

D'après (1) et (2), il n'existe pas de Tj tel que Tj contienne tous les autres Ti. Sinon il vaudrait E.
Prenons Ti et Tj 2 ensembles de tableaux qui ne se contiennent pas l'un ou l'autre. Autrement dit, Tj possède une intersection avec le complémentaire de Ti.
Ainsi Tj contient au moins 1 tableau n'appartenant pas à Ti. Et réciproquement.


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #15 - 03-02-2011 10:36:40

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Les 97 tableauux !

Logan ta récurrence ne marche pas. Elle ne couvre pas tous les cas possibles.
Les ensembles de tailles N+1 que tu couvres sont ceux dont il existe un sous-ensemble de taille N de personnes qui ont déjà vu tous les tableaux, ce qui ne représentent pas tous les cas possibles.
Je pense que précisément tu montres que la propriété est vrai pour tout ensemble de n personnes où deux personnes ont vu tous les tableaux à elles seules.

Il faudrait plutôt dire que si tu as un ensemble de taille N+1 alors il y a deux cas possibles :
1) Il existe un sous ensemble de taille N où tous les tableaux ont été vu : Ok par récurrence ( le cas que tu fais)
2) Il n'existe pas de sous ensemble de taille n ou tout le monde a vu tout les tableau. => Il existe un tableau T1 qu'une seule personne P1 a vu. Cette personne a pas vu au moins un tableau T2 qu'au moins une personne P2 a vu.
=> gagné (le cas que tu ne couvres pas)

En fait la preuve que j'ai faite en plus formelle ^^

 #16 - 03-02-2011 11:45:59

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

les 97 tavleaux !

J'aime beaucoup la preuve de fix33... Simple, claire et efficace.

@irmo : Irmo, tu t'es gourré, l'ordre n'est pas total.

 #17 - 03-02-2011 14:34:50

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Lse 97 tableaux !

Le fait que deux personnes puissent chacune avoir vu un tableau que l'autre n'a pas vu rend l'ordre partiel. 
Donc dans son raisonnement par l'absurde l'ordre est bien total.

 #18 - 03-02-2011 15:29:23

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Les 97 taableaux !

Exact Nicouj, j'ai parlé trop vite.

Grrr ... J'aurais dû réfléchir plus avant de me jeter dans une récurrence, du coup j'ai pas vu que l'hypothèse du raisonnement par l'absurde implique que [latex]T(P1)\subseteq T(P2)[/latex] ou [latex]T(P2)\subseteq T(P1)[/latex] qui est précisément l'axiome de linéarité.

 

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 : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Chaussure à son pied par darkcod03100
28-11-2010 Enigmes Logiques
P2T
Cercle des Sages par Franky1103
24-07-2014 Enigmes Logiques
P2T
28-03-2011 Enigmes Logiques
P2T
Escalier et chapeaux par McFlambi
21-06-2010 Enigmes Logiques
P2T
29-12-2007 Enigmes Logiques
P2T
Annuaire par Promath-
29-09-2010 Enigmes Logiques
P2T
28-03-2011 Enigmes Logiques
P2T
Grille magique par Spirou
16-01-2014 Enigmes Logiques
P2T
Un peu de désordre par Clydevil
03-04-2013 Enigmes Logiques

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