En me relisant, je me demande si je suis bien claire du coup, je vous donne un exemple pour n=3

première pesée 1+2=3 donc en une seule pesée le professeur est assuré d'avoir au moins un étiquetage correct (la pièce 3 mais il ne peut pas être sûr pour la pièce 1 et la pièce 2)

deuxième pesée 1<2 donc en deux pesées le professeur est assuré d'avoir tous les étiquetages corrects (la pièce 1 et la pièce 2 sont vérifiées maintenant)

Voilà, voilà, j'espère que cela vous donnera envie d'essayer pour d'autres valeurs, la réponse à la question 1) m'a beaucoup étonnée personnellement.

Bonsoir,
Pour la question 2,  un algorithme de tri standard donne la réponse en n log(n). Mais il n'utilise pas la possibilité pour la balance de donner Trois réponses.

Merci de ta participation GBZM.
Certes, un algo de tri fait le job mais on perd une autre info très utile autre que la troisième réponse de la balance.
En effet, on ne veut pas trier, on veut juste vérifier que le tri effectué par les élèves est correct ou si tu préfères : considérons que c'est toi qui as fait le tri, tu connais le poids de chaque pièce et tu veux me démontrer que tu as raison.
Combien de pesées au minimum pour me convaincre ? Tu optimises tes choix de pièces pour les pesées de sorte que moi je puisse conclure au plus vite.
Est-ce que tu vois comment améliorer facilement la borne que tu proposes ou je ne suis toujours pas claire ?

Bonjour,
Je ne sais pas si j'ai bien compris le problème, je prends un exemple pour expliquer ce que j'ai compris. Pour , pour le 1) on peut dire qu'il suffit d'une pesée pour être sur de l'étiquette 6  ? Car et il n'y a que 6 qui peut se décomposer avec 3 poids différents. (Donc on est sûr de 6 mais pour 1,2 et 3 on ne sait pas).
Si c'est juste, on peut dire que pour tous les de la forme , il suffit de faire une seul pesée pour être sur de l'étiquette la pesée étant à gauche du égale sur le plateau de gauche et à droite du égale sur l'autre plateau.

Bravo Barjovrille, tu as tout compris et tu viens évidemment de trouver le nombre de pesées minimum pour ces nombres bien particuliers (peut-être que certains d'entre vous savent comment ils s'appellent d'ailleurs).
Pour continuer dans cette voie, essaye peut-être de trouver d'autres nombres pour lesquels une seule pesée suffit.

Bonjour je ne sais pas si j'ai bien compris aussi ce probleme
si le professeur veut verifier l'etiquetage de la pièce numero 6 (soit 6g)
alors en prenant toutes les partitions de 6 on a  :


5+1  oui
4+2  oui
4+1+1 non
3+3  non
3+2+1  oui
3+1+1+1 non
2+2+2 non
2+2+1+1 non
2+1+1+1+1  non
1+1+1+1+1+1 non

donc le control du poids de la pièce numero 6 ce ferait comme suit :
plateau 1 : 6
plateau 2 :  5 , 1

plateau 1 : 6
plateau 2 :  4 , 2

plateau 1 : 6
plateau 2 :  3 , 2 , 1

donc pour verifier le poids de la pièce 6 il faut piocher les bonnes possibilités dans les facons d'obtenir une partition du nombre  6, soit dans ce cas avec 3  pesèes

est ce deja ca pour commencer ?

et si c'est bien ca , il suffit ensuite de trouver une generalité pour la pesée de la pièce numero k

En fait, ta 3ème pesée est suffisante et les 2 premières ne servent à rien.

En effet, avec la 3ème pesée, tu me dis qu'une seule pièce a le même poids que 3 autres pièces.
Quel est le poids minimum de 3 pièces lorsque n=6 ? 1+2+3
Quel est le poids maximum de 1 pièce  lorsque n=6 ? 6
Donc on est certain que l'égalité indiquée par la balance est bien 1+2+3=6 ce qui nous permet de confirmer le poids de 6.

On ne peut pas faire le même raisonnement avec 2+4=6 car tu me dis qu'une seule pièce a le même poids que 2 autres pièces mais c'est aussi valable pour 1+2=3 donc peut-être que la pièce seule dans la balance pèse 3 ou 4 ou 5 ou 6 et on ne peut rien confirmer.

Rappellons par ailleurs que la balance n'est pas obligée de donner une égalité

OK, la réponse attendue est binaire : oui, l'étiquetage est correcte ou non, l'étiquetage n'est pas correct.
Il ne s'agit pas de rétablir un étiquetage correct.

Toujours avec l'idée stupide du tri, on peut trivialement répondre si une pièce donnée est bien étiquetée ou pas en n-1 pesées.
Par ailleurs je ne suis pas convaincu par le coup 6=1+2+3.  Si la balance répond égal, OK le 6 est bien étiqueté. Mais si la balance penche du côté de 1+2+3, on ne peut rien dire, sauf que ces pièces ne sont pas toutes bien étiquetées. Mais il se peut très bien par exemple que le 6 soit bien étiqueté.

Ok pour n-1 mais on devrait pouvoir faire mieux, nettement mieux même et c'est ce qui m'a vraiment étonnée.
Tu as raison, mon problème est mal posé, la version que je t'ai proposé ensuite où tu dois me convaincre que tu as bien étiqueté au moins une pièce est plus pertinente. Dans ma version initiale, mal formulée, désolée, dès qu'on aperçoit une erreur, on peut faire un scandale et demander aux élèves de recommencer. Le but étant de confirmer l'étiquetage, pas de l'infirmer.

GBZM, j'avais les mêmes remarques, mais comme la question est de donné le minimum d'étape pour assurer une étiquette, on peut se placer dans le cas où tout se passe bien et on aura la borne inférieure.
Je pense que la deuxième formulation de Vassillia lève les ambigüités. On connait le poids de toutes les pièces et on veut démontrer en un minimum d'étape que cette pièce (celle qui nous arrange) a cette étiquette, à quelqu'un qui sait juste que les pièces ont un poids variant de 1 à n.

Autre cas où on peut assurer une étiquette en une seule pesée, le cas où n vérifie :  , alors le poids n est le seul à vérifier . (Il n'y a aucune pièce toute seule à part la pièce de poids n qui est plus lourde que cette somme).

Joli Barjovrille mais il existe encore d'autres cas où on peut le faire en 1 pesée. On a vu que pour n=6 et 7 tu sais faire.
Pour n=8 alors ? 1 pesée ou plus ?
Et pour n=5 ? 1 pesée ou plus ?

Pour ces deux cas c'est un peu du bricolage, pour l'instant je n'arrive pas à généraliser comme plus haut. Voici ce que je propose :
Pour n=5 on peut le faire en 2 pesée je n'ai pas trouvé mieux :
On pèse 3+2=5, on garde le 5, on enlève le 3 et 2, on prend les 2 poids restant on a 4+1=5, on peut vérifier à la main qu'il n'y a qu'un seul poids qui a deux décomposition différentes en 2 poids.

Pour n=8, on peut le faire en 1 pesée, le poids maximum de 2 pièces est 15 atteint avec 7 et 8, le poids minimum de 5 pièces est 15 qui est atteint avec 1,2,3,4,5. On a l'égalité sur la balance 1+2+3+4+5=7+8. C'est la seule combinaison 5 pièces contre 2 pièces où on obtient égalité. Par "unicité" de la combinaison on sait que 6 n'est pas sur la balance et il n'y a qu'une seule pièce qui n'est pas sur la balance donc on sait que la pièce sur le côté est 6.

Parfait, c'est très bien vu pour n=8
Il pourrait être interessant de généraliser ce cas dans un premier temps puis dans un second temps de se rapeller comment tu as trouvé d'autres cas vérifiables en 1 pesée à partir des n=k(k+1)/2 qu'on appelle nombres triangulaires.
Il se pourrait d'ailleurs que se renseigner sur ces nombres triangulaires soit utile pour trouver une borne haute pour le cas général (wikipédia devrait suffire).
On ne peut pas faire mieux pour n=5, je te l'ai surtout demandé pour ne pas avoir une seule pesée systématiquement.

Bonsoir,
pour s'intéresser à la question deux.
Avec l'exemple de Vassillia on voit que 2 pesées suffisent pour déterminer la correction de la numérotation dans le cas n=3 et il est évident qu'il en faut au moins 2.
Sauf erreur de ma part 2 pesées suffisent pour le cas n=4 et il en faut 3 pour les cas n=5 et n=6. Je ne suis pas allé plus loin.

Merci de ton intérêt verdurin, on peut faire un peu mieux pour les cas n=5 et n=6 mais c'est déjà pas mal du tout d'avoir réussi en 3 pesées.

Je ne sais pas si il y a plus précis mais voici ce que j'ai trouvé comme généralisation : Soit , si il existe tel que , alors on peut assurer la pièce en une pesé, on fait l'égalité que je viens de cité sur la balance et on raisonne comme n=8 par "unicité", la pièce sur le côté ne peut être que .
Au passage on peut assouplir  la condition d'égalité sans rompre l'unicité (comme le cas d'avant)  c'est à dire : si   si il existe tel que et   on a unicité de la combinaison qui vérifie l'inégalité stricte et on conclut de la même façon. (A la base je cherchais des règles plus précises mais je me suis perdu dans les recherches).

En fouillant les exemples j'ai aussi remarqué que si n vérifie la propriété suivante : il existe tel que , alors on peut assurer la pièce n ou n-1 (en fait les 2 en même temps) en 2 pesée, on fait l'égalité sur la balance et toujours par histoire d'unicité on sait que les deux pièces sur le plateau de droite sont alors n et n-1, on effectue une deuxième pesée pour voir qui est plus petit que l'autre et on peut conclure. Je ne sais pas si ça aide pour la majoration générale car c'est assez restrictif.

Pour j il faut plutôt prendre pour éviter les problème de définition.

Ps : On peut "edit" un message sur le forum ? Si oui pouvez vous me dire comment on fait?

Ah ben voilà, on a tous les cas faisables en 1 pesée, encore bravo Barjovrille !
Pour une majoration, on peut utiliser le résultat de Fermat en 1638 qui dit que tout entier est somme de trois nombres triangulaires (à condition de considérer zéro comme un nombre triangulaire)
Il reste à voir comment l'utiliser ?

PS : on ne peut pas éditer à ma connaissance mais en cas de problème vraiment important, tu peux contacter la modération

Salut Vassillia.
J'ai sans doute de la sauce blanche à la place du cerveau mais je n'arrive pas à certifier toutes les étiquettes en deux pesées dans le cas n=5.
Accepterais-tu me donner la solution, en mode caché, de ce cas ?
D'avance merci.

Salut verdurin

Bien sur, n'hésitez pas à demander les solutions qui vous intéressent passé un temps raisonnable.
Et je te rassure, il n'y a vraiment pas de honte à ne pas trouver la valeur optimale, trouver une manière de faire est déjà très satisfaisant.

 Cliquez pour afficher

Pour n=5
1ère pesée 1+2<4
Donc le plateau de droite vaut 4 ou 5
2ème pesée 1+4=5
Donc on valide 4 et 5 puis 1
On en déduit 2 et 3

ou alors
1ère pesée 1+2=3
Donc le plateau de droite vaut 3, 4 ou 5
2ème pesée 1+3<5
Don on valide 3 et 5 puis 1
On en déduit 2 et 4

Merci.

Bonjour,
je vais essayer de montrer qu'on peut toujours assurer une pièce en au plus 3 pesées.
Soit où les sont triangulaires (Fermat). On peut supposer sans perte de généralité que . On effectue une première pesée comme est triangulaire il existe tel que (première pesée) on sait que la pièce   est supérieur au poids minimal de pièces. On prend la pièce de poids , qu'on va noté , on fait la pesée où est la pièce de la pesée précédente qu'on a juste mis à droite. On peut minorer le poids de la pièce car on a par l'étape précédente un minorant de et on peut minorer le poids de pièces. Et on prend la pièce de poids qu'on note , on effectue la pesée (où est la pièce de l'étape précédente qu'on a mis a droite). Et on peut minorer le poids de car on connait un minorant du poids de , et on peut minorer le poids de pièces.

Pour résumer, donc est la seule pièce plus grande que n donc c'est la pièce de poids n.

J'ai fait apparaitre les nombres triangulaires dans l'ordre décroissants car si on fait autrement il se pourrait qu'on ai besoin de deux fois la même pièce dans une pesée ce qui n'est pas faisable.

Si c'est juste je vais faire une pause pour ce défi je reviendrais plus tard pour la deuxième question (si il n'y a personne d'ici la). En tout cas merci pour ce défi Vassillia, je n'ai pas l'habitude de pratiqué ce domaine des maths, j'ai été agréablement surpris.

Les notations partent un peu dans tous les sens, dis moi si il y a quelque chose qui n'est pas clair.

Eh bien si ce n'est pas ton domaine de prédilection, je demande à voir ce que ça va donner quand ce sera ton domaine de prédilection ! C'est tout à fait correct et tout à fait impressionnant de ta part.
En fait on peut faire légèrement mieux, c'est à dire toujours assurer au moins une pièce en 2 pesées (voir cet article ) mais l'étude de cas devient un peu casse-pied selon moi.
Je n'en attendais pas tant, tu as trouvé tous les résultats que j'espérais, je trouve ce résultat assez bluffant même avec 3 pesées, ravie que cela te plaise et peut-être à bientôt pour la suite...

Merci pour la source ! Effectivement assurer en 2 pesées rallonge la démonstration. Je trouve aussi que c'est impressionnant la borne indépendante du nombres de pièces.