Petite énigme

[kaderben]

Bonjour
Ci joint le sujet d'une petite énigme qui se fait aisément (l'orthographe, je ne suis pas sûr) par élimination dans le tableau et je l'ai fait.
Je voulais savoir si ce genre d'exo peut se faire à l'aide de la logique, je pense aux formalisations et aux tables de vérité.
Je connais les 16 connecteurs logiques mais je n'ai jamais manipulé ce genre d'exo.

Je pense écrire, par exemple: ("Albert" ET "nonNice") ET ("Albert" ET "non200")
("2000" ET "nonVenise") ET ("2000" Et "nonNice")
"Norbert" ET "2000"
Est ce que c'est du n'importe quoi ou ça peut aller pour l'instant ?

Merci pour vos commentaires
-----

[leg]

bonjour comment tu peux avoir Norbert et 2000 puisqu'il a fait les photos de 2002...
les photos de paris sont de 2000...et Albert n'a pu aller qu'à Venise...

[invite936c567e]

Bonjour

Je ne vois pas trop à quoi rime ce formalisme, ni en quoi d'algèbre booléenne va pouvoir t'aider.

Ce problème de logique se règle facilement en utilisant le tableau de l'énoncé, lequel suggère donc la méthode. Tu peux par exemple barrer les cases indiquant un fait impossible (faux), et entourer les cases indiquant un fait avéré (vrai). Les cases ni barrées ni entourées sont encore indéterminées.

La résolution s'appuie sur les indices donnés en utilisant seulement le fait que les cas de figure s'excluent mutuellement : considérant trois faits de même nature relatifs au même élément, si deux sont faux, alors le troisième est forcément vrai, et si l'un est vrai, alors les deux autres sont forcément faux.

Conseil : intéresse-toi aux dates, puis aux lieux.

[invite501e8040]

Bonjour
Ci joint le sujet d'une petite énigme qui se fait aisément (l'orthographe, je ne suis pas sûr) par élimination dans le tableau et je l'ai fait.
Je voulais savoir si ce genre d'exo peut se faire à l'aide de la logique, je pense aux formalisations et aux tables de vérité.
Je connais les 16 connecteurs logiques mais je n'ai jamais manipulé ce genre d'exo.

Je pense écrire, par exemple: ("Albert" ET "nonNice") ET ("Albert" ET "non200")
("2000" ET "nonVenise") ET ("2000" Et "nonNice")
"Norbert" ET "2000"
Est ce que c'est du n'importe quoi ou ça peut aller pour l'instant ?

Merci pour vos commentaires

Par la logique, oui. Peut être est-il intéressant de chercher du côté de prolog. Par exemple voici une page qui résout le problème d'Einstein en prolog : http://blog.courtine.org/2010/09/23/...ein-en-prolog/. En prolog tu énonces les prédicats, et ensuite tu poses ta question et le programme trouve la solution comme un grand.
Pour des problèmes plus compliqués (ou pas) on peut faire appel à de la programmation par contrainte où on doit définir des contraintes sur des variables pour au final obtenir la solution. Là encore c'est le programme qui décide de comment résoudre le problème, l'utilisateur ne fait que spécifier le problème. Gecode est un outil de programmation par contrainte.
Maintenant dans des cas très simples comme celui-ci il suffit de chercher parmi toute les réponses possibles celle(s) qui convient(conviennent).

En fait les tables de vérités n'aident pas à la résolution, ou plutôt elles représentent tous les cas possibles.
De toutes façons, il faut bien définir les variables et les contraintes/prédicats.
Par exemple dans ton ("Albert" ET "nonNice") ET ("Albert" ET "non200"), ce sont des booléens si j'ai bien compris mais que signifie Albert:=vrai et Albert:=faux ?
Je verrais plutôt une variable par cases du tableau, qui peut être vraie ou fausse. En plus des indices il faut ajouter le fait qu’il ne peut y avoir qu'une date par personne, qu’un pays par personne et qu'on ne peut les utiliser qu'une seule fois.

ps: je penses que tu peux modéliser ce genre de problèmes par un problème de satisfaisabilité (Satisfiability), par contre pour le résoudre il faudra passer par des programmes comme gecode ou autre vu que ces problèmes sont np-complet, ou alors bêtement énumérer toutes les possibilités jusqu’à tomber sur la bonne (ce qu'est en réalité la table de vérité).

[A voir en vidéo sur Futura]

[kaderben]

Pour Norbert c'est "Norbert ET 2002"
Bref, d'après vos réponses, la logique ne nous servira à rien !
Merci

[invite936c567e]

La logique servira, puisque c'est un problème de logique. En revanche c'est la logique booléenne avec le formalisme que tu souhaites adopter qui me semble particulièrement inadapté.

[kaderben]

Bonjour PA5CAL
Oui, "En revanche c'est la logique booléenne avec le formalisme que tu souhaites adopter qui me semble particulièrement inadapté" tu as raison. Je n'ai jamais manipuler ce genre de formalisme avec ses tables de vérité ou autres. J'ai déjà dit que je connais les connecteurs car je les ai utilisés en electronique, mais jamais dans ce genre d'exercice que je propose.
J'aimerai bien que quelqu'un me montre un tout petit peu comment on s'y prend pour formaliser les informations données dans les indices de cet exo ( sans que cela soit une contrainte de temps pour l'internaute)...
Cordialement

[Médiat]

Bonjour,

C'est effectivement possible, mais assez pénible :
en posant
= Albert, = Norbert, = Xavier
= Nice, ...
= 1998, = 2000...

votre premier indice permet d'écrire etc ...

Ne pas oublier les formules du genre etc

[invite501e8040]

Bonjour,

C'est effectivement possible, mais assez pénible :
en posant
= Albert, = Norbert, = Xavier
= Nice, ...
= 1998, = 2000...

votre premier indice permet d'écrire etc ...

Ne pas oublier les formules du genre etc

Pour moi les variables sont mal posées.
Comment à partir de ces variables peut on trouver la réponse à l’énigme ? avec ces variables il y a 2^(3*3) états possibles alors que dans le tableau de l'énigme il y en a 2^(18). Plus précisément comment forcer les contraintes: si Albert est allé à nice alors ni Norbert ni Xavier n'y sont allé ? on pourrait écrire mais ça n'a pas de sens avec les variables actuelles... d'ailleurs comment interpréter les variable, d'où ma question dans les posts précédents, que signifie Albert = 1 et Albert = 0 ?

[Médiat]

Il faut écrire des tas de choses d'où le qualificatif "pénible" que j'ai écrite (et, d'ailleurs, je ne préconise pas cette méthode).

Par exemple il faut ajouter des choses comme

Si vous faites une table de vérité, il ne devrait rester que 3 lignes du genre

[invite501e8040]

Il faut écrire des tas de choses d'où le qualificatif "pénible" que j'ai écrite (et, d'ailleurs, je ne préconise pas cette méthode).

Par exemple il faut ajouter des choses comme

Si vous faites une table de vérité, il ne devrait rester que 3 lignes du genre

sauf qu'on n'obtient pas ces 3 lignes car certaines contraintes ne peuvent pas être exprimées par le choix de ces variables. On peut forcer à n'avoir qu'un y et qu'un seul z pour chaque x et de même forcer un seul x à être vrai sans les autres. par contre on ne peut pas forcer le fait de choisir un y différent si il répond aux critères d'un autre x de manière à avoir 3 y différents pour chaque x. Bref qu'est-ce qui m'empêche de choisir

[Médiat]

Qu'est-ce qui vous empêche d'écrire etc. ?

[invite501e8040]

car on a déjà
qui correspond au fait qu'on a qu'un seul x à vrai, sinon la table de vérité ne voudrait plus rien dire.
or implique

[Médiat]

Donc pas de problème.

[invite501e8040]

essayez et vous verrez qu'il y a bien un problème.
ce que je veux vous faire comprendre c'est qu'avec les variables que vous proposez il n'est pas possible de résoudre le problème. Une solution serait de rajouter des variables mais il est bien plus simple de considérer les 18 variables suivantes: Albert_nice, albert_paris, albert_venise, albert_1998, albert_2000, albert_2002, norbert_nice,…
C'est le pourquoi du

De toutes façons, il faut bien définir les variables et les contraintes/prédicats.

d'un de mes messages.

[Médiat]

Ne pas oublier des trucs du genre :

[Médiat]

avec les variables que vous proposez il n'est pas possible de résoudre le problème.

Si vous le dites ...

[invite936c567e]

Une exemple de présentation de la résolution.

 Cliquez pour afficher

Traduction des faits donnés dans l'énoncé, avec les notations du tableau :

1. (Albert≠b)  [1a]
   (Albert≠e)  [1b]

2. (e≠b)       [2a]
   (e≠c)       [2b]

3. (Norbert=f)  [3]

Résolution par application des règles que j'ai indiquées sur les faits connus de proche en proche :

                    (Norbert=f)  [3] ⇒ (Albert≠f)   [4]
                    (Norbert=f)  [3] ⇒ (Norbert≠e)  [5]
(Albert≠e)  [1b] et (Albert≠f)   [4] ⇒ (Albert=d)   [6]
(Albert≠e)  [1b] et (Norbert≠e)  [5] ⇒ (Xavier=e)   [7]
(e≠b)       [2a] et (e≠c)       [2b] ⇒ (e=a)        [8]
(Xavier=e)   [7] et (e=a)        [8] ⇒ (Xavier=a)   [9]
                    (Xavier=a)   [9] ⇒ (Xavier≠b)  [10]
                    (Xavier=a)   [9] ⇒ (Xavier≠c)  [11]
(Albert≠b)  [1a] et (Xavier≠b)  [10] ⇒ (Norbert=b) [12]
                    (Norbert=b) [12] ⇒ (Norbert≠c) [13]
(Norbert≠c) [13] et (Xavier≠c)  [11] ⇒ (Albert=c)  [14]

Résultat :

(Xavier=a)   [9]
(Norbert=b) [12]
(Albert=c)  [14]
(Albert=d)   [6]
(Xavier=e)   [7]
(Norbert=f)  [3]

Albert a pris les photos de Venise en 1998.
Norbert a pris les photos de Nice en 2002.
Xavier a pris les photos de Paris en 2000.

Une résolution de ce type peut être rapidement obtenue par programmation informatique, dans un langage logique de type Prolog par exemple.

[invite936c567e]

Afin d'utiliser ce formalisme,

 Cliquez pour afficher

on pourrait traduire l'énoncé sous la forme :
«
Soit l'ensemble fini E={Albert;Norbert;Xavier} constitué d'éléments distincts deux à deux (i.e. tels que Albert≠Norbert, Albert≠Xavier et Norbert≠Xavier).

Chercher a, b, c, d, e et f tels que :
- E={a;b;c}
- E={d;e;f}
- b≠Albert
- e≠Albert
- e≠b
- e≠c
- f=Norbert
»

La résolution n'utilise que les propriétés triviales suivantes :
- ∀(i,j)∈E² (i=j) ⇒ (j=i)
- ∀(i,j)∈E² (i≠j) ⇒ (j≠i)
- ∀(i,j,k)∈E³ ((i=j) et (j=k)) ⇒ (i=k)
- ∀(i,j)∈E² (∀k∈E-{j} k≠i) ⇒ (i=j)
- ∀i∈E ∀j∈E-{i} ∀k∈E (k=i) ⇒ (k≠j)