Des objets et des boîtes . . .

Ben314159

Bonjour
Sur math forum il y a un gus (anglophone) qui pose quelques énigmes ces temps ci dont celle là : 

Autant je pense avoir une idée concernant la valeur du maximum (et avec quelle liste de déclaration on l'obtient), autant je suis totalement sec concernant la façon dont on peut prouver que c'est effectivement le maximum.

P.S. S'il y en a des encore plus allergique à l'anglais que moi, je peux me fendre d'une traduction . . .

Domi

Bonjour Ben314159
Si j’ai bien compris la question et si on note E=[[1,N]], il me semble qu'on cherche une partie minimale M de P(E) telle que tout entier de E appartient à exactement un élément de M.

C'est tout de même assez tordu 
Domi.

Namiswan

Avec ta réinterprétation, M={E} marche non ? Peux-tu préciser ?

Je ne crois pas de mon côté avoir compris le problème. Tel quel j'ai l'impression que chaque assertion donne une info sur un seul objet, donc je ne vois pas comment faire mieux que N-1...

Domi

J'essayais de donner un côté "ensembliste" au problème mais tu as raison , il manque peut-être une condition ? Je me suis fait la même remarque que toi sur le N-1 mais je ne suis pas sûr.
Domi

lourrran

Mieux que, ça veut dire quoi dans ton idée ?   Ça veut dire moins que, ou plus que ?
C'est clair que la succession d'informations doit contenir au moins N-1 messages.

Mais on peut imaginer ce cas : 
N=3
Obj 1 est dans la boite 1 ou 2
Obj 2 est dans la boite 1 ou 2
Obj 1 est dans la boite 1 ou 3

Si la personne B entend les 3 messages, elle peut trouver la disposition des N=3 objets.
Mais si elle rate l'un ou l'autre des 3 messages, elle ne peut pas trouver la disposition.

Si je note M le nombre de messages, j'ai M=3=N.
Et ce qu'on cherche, c'est maximiser ce nombre M, et non minimiser

Et pas question de le maximiser en disant un message du type Obj1 est dans la boite 1 ou 2 ou 3 (donc une lapalissade puisqu'il y a 3 boites), parce que même si la personne B n'entend pas ce message, elle n'aura rien raté.

Domi

Je penche de plus en plus vers le N-1, mais le posteur fait-il mieux ?
Domi

Ben314159

Exprimé de façon plus mathématique, "l'inconnue", c'est une permutation $\sigma$ de $\{1,\dots,N\}$ dans lui même.
On cherche un certain nombre $M$ de contraintes de la forme $\sigma(n_i)\in A_i\ ;\ i\in\{1,\dots,M\}$ où les $n_i$ ne sont pas forcément distincts (*) et aucune contrainte particulière sur les ensembles $A_i\subset\{1,\dots,N\}$. On veut que : 
- Lorsque l'on considère toutes les contraintes, il y a une unique permutation $\sigma$ qui soit solution.
- Lorsque l'on enlève une quelconque des contraintes, alors il y a plusieurs  solutions.
Le but est de trouver le $M$ maximal.

(*) Mathématiquement parlant, les deux contraintes $\sigma(n)\in A$ et $\sigma(n)\in B$ se résument bien sûr à l'unique contrainte $\sigma(n)\in A\cap B$, sauf que, dans le premier cas, ça compte comme 2 contraintes alors que dans le second, ça compte pour une seule.  Donc sauf erreur, ça signifie que, pour maximiser $M$ on peut supposer que toutes les contraintes sont de la forme $\sigma(n)\not= m$ (i.e. avec un ensemble $A$ le plus gros possible). 
Dans ce cas, on peut voir le problème sous la forme de la recherche d'une partie $X\subset\{1,\dots,N\}^2$ telle qu'il y ait une unique permutation vérifiant $\forall n\!\in\{1,\dots,N\},\ \big(n,\sigma(n)\big)\in X$ mais que, pour tout ensemble $X'$ contenant strictement $X$ il y ait plusieurs solutions. Le but étant de minimiser le cardinal de $X$ (vu que les éléments du complémentaire de $X$ donnerons les contraintes de la forme $\sigma(n)\not= m$)

Ben314159

Et je n'avais pas fait gaffe que l'énoncé était sous forme de deux images (et je n'en ai copié qu'une).  Il y avait aussi un exemple pour $N\!=\!4$ : 
$C_1:\sigma(2)\in\{3,4\}$
$C_2:\sigma(3)\in\{1,3\}$
$C_3:\sigma(1)\in\{1,4\}$
$C_4:\sigma(2)\in\{1,2,3\}$
Une seule solution : $\sigma(2)\!=\!3\ ;\ \sigma(3)\!=\!1\ ;\ \sigma(1)\!=\!4\ ;\ \sigma(4)\!=\!2$ et plusieurs solutions dés qu'on enlève une des $4$ contraintes. (mais $M=4$ n'est pas optimal pour $N=4$)

EDIT. Et ma conjecture, pour le moment, c'est que le $M$ maximal, c'est $N(N-1)/2$ avec $X=\big\{(n,m)\mbox{ t.q. }m\leqslant n\big\}$.

Namiswan

Je n'avais pas fait attention que M devait être maximal (dans ma tête on cherchait à minimiser le nombre d'informations données). Ok au moins le problème m'est clair maintenant.

depasse

Bonjour
EDIT: Preuve invalidée par @raoul.S
On peut supposer SPDG que la permutation que doit trouver notre ami est l'identité.
Pour qu'il trouve que 1 est dans la boîte 1 on lui donne n-1 infos:
1 est dans $\{1\} \vee [[2,n]]\setminus \{j\}$, où $j$ varie de $2$ à $n$.
Alors il a trouvé que 1 est dans la boîte $1$ mais n'a aucune idée sur la répartition des $n-1$ autres objets. On est donc ramené au cas de $n-1$ objets.
Finalement le nombre maximum cherché est (au moins) la somme des $n-1$ premiers entiers, ce qu'a conjecturé @Ben314159
Cordialement
Paul

raoul.S

Si j'ai bien compris ta solution @depasse , elle a des contraintes inutiles. Par exemple pour le cas $n=4$ tu as 6 contraintes. Mais tu peux supprimer la contrainte $1\in \{1,3,4\}$ tout en garantissant une solution unique.

depasse

@raoul.S
Merci, tu as (hélas!) raison !

Ben314159

Moi, ce que je n'ai pas compris, c'est la remarque de Raoul . . .
Pour moi, dans le cas $N=4$, les 6 contraintes, c'est $\sigma(1)\!\not=\!2\ ;\ \sigma(1)\!\not=\!3\ ;\ \sigma(1)\!\not=\!4\ ;\ \sigma(2)\!\not=\!3\ ;\ \sigma(2)\!\not=\!4\ ;\ \sigma(3)\!\not=\!4$.
Et si, comme le dit Raoul, j'enlève la contrainte $\sigma(1)\!\not=\!2$ alors, en plus de la solution de base $\sigma\!=\!(1,2,3,4)$, il y a maintenant $\sigma\!=\!(2,1,3,4)$, non ?
Et il me semble que dans le cas général avec les $N(N\!-\!1)/2$ contraintes $\sigma(n)\!\not=\!m$ pour $m\!>\!n$ il est tout aussi clair qu'elles sont toutes utiles vu que, si on enlève la contrainte $\sigma(n_o)\!\not=\!m_o$, alors on a une deuxième solution, à savoir $\sigma(n_o)\!=\!m_o$ ; $\sigma(m_o)\!=\!n_o$ et $\sigma(n)\!=\!n$ pour les autres.

Bref, pour moi, le problème, c'est de montrer qu'on ne peut pas faire mieux . . .

Domi

Comme souvent j'avais lu la question à l'envers. À ma décharge la question est plutôt contre-naturelle et en english 
Domi.

Ben314159

J'aurais mis l'exemple dés le début, ça aurait aidé à comprendre . . .
Sinon, concernant le coté "contre-naturel", c'est vrai qu'on s'attendrait plutôt à ce qu'il faille minimiser le nombre d'info. qu'on donne au copain, mais avec l'énoncé tel qu'il est c'est assez trivial de trouver le minimum.  Pour que ce soit moins trivial, on pourrait (justement...) imposer que les info qu'on donne soit obligatoirement de la forme $\sigma(n)\!\not=\!m$ où je me demande si le minimum n'est pas de nouveau $N(N\!-\!1)/2$.

Titi le curieux

Bonsoir, 
Pour simplifier, on va admettre que toutes les affirmations sont du type "l'objet $o$ n'est pas dans la boîte $b$" (Il est évident que la solution n'est pas maximale si ce n'est pas le cas). Je me demande si un cas qui fonctionne implique nécessairement qu'un objet ou un boîte est directement sujet de $N-1$ affirmations.
Si c'est le cas, il suffit* de le prouver pour prouver que la formule $M=N(N-1) /2$ est la bonne. 
Tout ce que je peux dire sur le sujet c'est que ça fait trois quart d'heure que je gratte et que je ne suis pas capable de pondre un contre-exemple (il est facile de montrer qu'il n'y en a pas pour N=3, je ne crois pas qu'il y en a pour N=4, j'ai juste tourné autour du cas N=5). 

*: L'expression utilisée ne signifie pas que ce serait facile 

Ben314159

Sauf erreur, j'ai la solution.
On suppose qu'on a une liste de contraintes (différentes) de la forme $\sigma(n)\!\not=\!m$ telles que l'unique permutation vérifiant ces contraintes soit l'identité mais qu'il y ait au moins une autre solution lorsque l'on enlève une (quelconque) des contraintes.
Pour tout $a\!\not=\!b$, la transposition de $a\leftrightarrow b$ n'est pas solution donc, dans la liste des contraintes, il y a $\sigma(a)\!\not=\!b$ ou bien $\sigma(b)\!\not=\!a$, voire les deux.
Supposons qu'il y ait les deux. On sait qu'en enlevant la contrainte $\sigma(a)\!\not=\!b$ il y a une solution $\sigma\!\not=\!Id$ qui vérifie forcément $\sigma(a)\!=\!b$ (sinon elle vérifierais la contrainte enlevée et, par unicité, serait égale à l'identité). Dans cette permutation on a donc un cycle $a\!\rightarrow\!b\!\rightarrow\!c\!\rightarrow\dots\rightarrow\!a$ de longueur au moins 3 (vu qu'on a toujours la contrainte $\sigma(b)\!\not=\!a$) et où toutes les flèches, sauf la première, étaient autorisées au départ.  De même, en enlevant la contrainte $\sigma(b)\!\not=\!a$, on trouve un cycle  $b\!\rightarrow\!a\!\rightarrow\!c'\!\rightarrow\dots\rightarrow\!b$ de longueur au moins 3 où toutes les flèches, sauf la première, étaient autorisées au départ.  Mézalors, le cycle $a\!\rightarrow\!c'\!\rightarrow\dots\rightarrow\!b\!\rightarrow\!c\!\rightarrow\dots\rightarrow\!a$ (*) était autorisé dés le départ et, en complétant  avec $Id$ en dehors de son support, on obtient une solution $\not=\!Id$ au problème de départ ce qui contredit l'unicité.
Bilan : pour tout $a\!\not=\!b$, une et une seule des deux affirmations $\sigma(a)\!\not=\!b\ ;\ \sigma(b)\!\not=\!a$ fait partie des contraintes et il y a  donc exactement $N(N\!-\!1)/2$ contraintes (qui est à la fois le maximum, mais aussi le minimum . . .)

(*) S'il y a des élément en commun entre les deux cycles, on court-circuite pour obtenir un cycle plus court.

Titi le curieux

Bien joué!

raoul.S

Effectivement on dirait que c'est bon.