Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Le principe des pigeons

Posté par
klaus24
20-03-17 à 21:57

Lorsque l'on place n+1 pigeons dans n boites (ou tiroirs), une des boites doit contenir au moins deux pigeons.
Le but de l'exercice est de montrer que la méthode de résolution peut être "mauvaise" (preuves de longueur exponentielle, Haken 1985). Répondre aux points suivants :


a- Formaliser ce principe au moyen d'une formule du Calcul Propositionnel. Le résultat sera PHn:
On introduira pour cela n(n + 1) variables propositionnelles :
P1;1; P1;2; P1;3; : : : ; p1;n; p2;1; : : : ; pi;j ; : : : ; pn+1;n:
pour 1 <= i <= n + 1; 1 <= j <= n:
La variable propositionnelle pi;j sera interprétée: le pigeon i est dans la boite j.


b- Montrer, en utilisant des arguments mathématiques (principe informel des pigeons) que PHn est une tautologie.


c- Considérer la négation de PHn: Vérifi er qu'elle est écrite en forme normale conjonctive. Appliquer la méthode de résolution pour n = 2: Combien de clauses obtient-on ?

Posté par
lafol Moderateur
re : Le principe des pigeons 20-03-17 à 22:26

Bonjour à toi aussi

Posté par
flight
re : Le principe des pigeons 20-03-17 à 22:58

..le pigeon c'est celui qui repond alors ?

Posté par
lafol Moderateur
re : Le principe des pigeons 21-03-17 à 17:48

Posté par
klaus24
re : Le principe des pigeons 29-03-17 à 14:46

dsl vraiment c mon premier post
j'espr q vous me répondre

Posté par
lafol Moderateur
re : Le principe des pigeons 29-03-17 à 17:19

attentionextrait de c_faq la FAQ du forum :

Q26 - Pourquoi dois-je écrire mon message dans un français correct ? Pourquoi le langage SMS est-il interdit sur l'Île ?


attentionextrait de c_faq la FAQ du forum :

Q09 - Comment bien rédiger son message ?



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !