Forum de mathématiques - Bibm@th.net

Vassillia

Membre

Inscription : 16-09-2023

Messages : 77

Vraies ou fausses pièces

Bonjour, une énigme pas facile, à ma connaissance, elle n'est pas totalement résolue mais on peut trouver quelques résultats intéressants soi-même quand même.

Des faux-monnayeurs ont mis en place un réseau de distribution de fausses pièces de 1 euro qui font toutes le même poids inconnu tandis que le poids des vraies pièces de 1 euro est connu.
Les enquêteurs vont demander le nombre de pièces de leur choix à chacun des n individu suspects (qui ne possède qu'un seul type de pièce en nombre illimité) puis ils marqueront la provenance des pièces.
Ils peuvent ensuite faire uniquement 2 pesées à partir d'une ou plusieurs pièces à leur disposition. Leur but étant d'identifier les individus participant au réseau et les individus honnêtes.

Pouvez-vous aider les enquêteurs à minimiser le nombre de pièces à récupérer lorsqu'il est possible de faire les identifications ?

Autant on pourra chercher la valeur optimale pour les petites valeurs de n, autant on pourra se contenter d'une borne max et min pour les grandes valeurs de n. Ainsi tout le monde peut y trouver son compte quelque soit son niveau.

Amusez-vous bien si la thématique vous plait.

Dernière modification par Vassillia (18-09-2023 14:54:00)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Vraies ou fausses pièces

Bonjour,

Quel type de balance ?
(Il suffit d'une balance pour dénoncer les membres du réseau ;)).

Vassillia

Membre

Inscription : 16-09-2023

Messages : 77

Re : Vraies ou fausses pièces

Ah oui, vu comme ça effectivement, c'est plus simple ! Bien trouvé !
Mais on se contentera d'une balance qui donne le poids de l'ensemble des pièces que les inspecteurs mettent sur le plateau avec une précision suffisante pour nos besoins.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Vraies ou fausses pièces

Si on connaissait le poids des fausses pièces, une seule pesée avec 1,2,4,...2^n pièces suffirait.Mais on ne connait pas le poids des fausses pièces.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Vraies ou fausses pièces

On peut mathématiser ainsi :

Trouver deux fonction [tex]p, q : \{1,2,\dots,n\} \to  \mathbb N[/tex] telles que les rapports [tex]\dfrac{\sum_{i\in I} p(i)}{\sum_{i\in I} q(i)}[/tex] pour [tex]I \subset \{1,\ldots,n\}[/tex] soient tous différents entre eux.
Pour [tex]n=3[/tex] par exemple on peut prendre les valeurs (0,1,1) pour [tex]p[/tex] et (2,1,0) pour [tex]q[/tex].
Il suffit de demander 2 pièces au premier, 1 au second et 1 au troisième.

Vassillia

Membre

Inscription : 16-09-2023

Messages : 77

Re : Vraies ou fausses pièces

Je ne suis pas bien convaincue que tout le monde trouve la mathématisation aussi évidente que toi mais bravo, c'est exactement là où je voulais en venir.
Il reste à trouver deux fonctions qui font l'affaire quitte à complétement exploser le nombre de pièces.
En tout cas impossible de faire mieux pour n=3.

Vassillia

Membre

Inscription : 16-09-2023

Messages : 77

Re : Vraies ou fausses pièces

Bonjour, pour en savoir plus vous pouvez consulter OEIS
Dans la version d'origine de ApSimon, l'auteur avait choisi $p(i)=i!$ et $q(i)=1$ mais il y a des analyses plus récentes qui font mieux (je n'en attendais pas tant)

Dernière modification par Vassillia (27-09-2023 16:06:44)