Deux questions de mathématiques (raisonnement, logique)

John a écrit:Soit le problème suivant :

Un herboriste se sert d'une balance pour peser les différents sachets d'infusion qu'il vend à ses clients. Ses sachets pèsent entre 1 et 40 grammes. Il dispose pour les peser d'une balance à plateaux et de quatre poids. Il place toujours les sachets d'herbes sur un plateau de la balance, et les poids sur l'autre plateau. Quels sont les quatre poids qu'il lui faut posséder pour pouvoir peser toutes les combinaisons de masses, de 1 à 40 grammes ?

La réponse est : 1, 3, 9 et 27 grammes, qui permettent effectivement par l'addition et la soustraction d'obtenir tous les nombres de 1 à 40.

Ma question à moi est la suivante : est-il possible de répondre à cette question par un raisonnement, et non à tâtons et de manière empirique ?

Je m'étais posé ce type de question en essayant de chercher les scores qui n'étaient pas possible au rugby (2, 3 et 5 points) et je ne pense pas qu'il y ait de théorie (simple ou sans programme informatique) quand il y a trop de paramètres (4 poids inconnus)...

Soit l'autre problème suivant :

Un employé a obtenu une prime de 200 euros. Il achète x objets coûtant x euros, y objets coûtant y euros, et z objets coûtant z euros.

Ce qui équivaut à : x²+y²+z² = 200.

La solution est : x = 6 ; y = 8 ; z = 10. Là encore, y-t-il un moyen de résoudre le problème par un raisonnement mathématique, et non en essayant successivement les diverses combinaisons avec des chiffres au hasard ?

En maîtrise, je m'étais fait une disquette de petits programmes utiles (que je n'ai jamais utilisés ) de théorie des nombres et ce que tu demandes doit exister. Mais je ne sais pas à partir de quoi...
Demande à Finrod, peut-être qu'il a fait de la recherche en théorie des nombres.

John a écrit:

Ce qui équivaut à : x²+y²+z² = 200.

Avec 200, ça reste relativement facile : x, y, et z < 15 et par exemple si x dépasse 10, y et z soit nécessairement très petit...
Donc c'est vite fait.

Il faut se dire que pour le concepteur, qui part dans l'autre sens, c'est beaucoup plus facile (!!), ici si tu recherches comme les Bogdanov la main de dieu dans cet ex.

Oh my god...

John a écrit:

Avec, ça reste relativement facile : x, y, et z < 15 et par exemple si x dépasse 10, y et z soit nécessairement très petit...
Donc c'est vite fait.

Il faudrait rajouter dans le problème, x<15 ; y<15 et z<15 et x "supérieur ou égal" à 10 ?

Non, ce que Pierre veut dire c'est que 15²=225 est déjà supérieur à 200, donc ça restreint tout de suite.

Pour le problème de l'herboriste, c'est issus d'un bouquin de Bachet http://fr.wikipedia.org/wiki/Claude-Gaspard_Bachet_de_M%C3%A9ziriac

Voici un solutions moderne. Notons a, b, c, d les 4 poids, ce sont des entiers supérieurs ou égaux à 1. On peut sans perte de généralité supposer que l'on appelle a le plus léger, b le second, c le troisième et d le plus lourd. Il y a un peu de liberté dans l'interprétation de l'énoncé, alors je vais supposer que les 4 poids sont tous différents (d e toutes façons avec de poids égaux on voir vite que ça marche pas). Mathématiquement ça se traduit par des inégalités : 1 <= a < b < c < d.

Ensuite, l'énoncé peut se reformuler en disant que l'on veut que les sommes de la forme S= A.a + B.b + C.c +D.d couvrent tous les entiers de 1 à 40, où les lettres A,B,C,D représentent soit un signe +, soit un signe -, soit 0. Autrement dit on travaille en base 3, d'où immédiatement a=3^0=1, b=3^1=3, c=3^2=9 et d=3^3=27. La limite étant a+b+c+d=40.

Pour une solution moins formelle voir ici: http://www.indispensables.over-blog.com/article-24670903.html

John a écrit:Soit le problème suivant :

Un herboriste se sert d'une balance pour peser les différents sachets d'infusion qu'il vend à ses clients. Ses sachets pèsent entre 1 et 40 grammes. Il dispose pour les peser d'une balance à plateaux et de quatre poids. Il place toujours les sachets d'herbes sur un plateau de la balance, et les poids sur l'autre plateau. Quels sont les quatre poids qu'il lui faut posséder pour pouvoir peser toutes les combinaisons de masses, de 1 à 40 grammes ?

La réponse est : 1, 3, 9 et 27 grammes, qui permettent effectivement par l'addition et la soustraction d'obtenir tous les nombres de 1 à 40.

Ma question à moi est la suivante : est-il possible de répondre à cette question par un raisonnement, et non à tâtons et de manière empirique ?

1. Il y a un problème dans l'énoncé car tu dis : "Il place toujours les sachets d'herbes sur un plateau de la balance, et les poids sur l'autre plateau". Si tel était vraiment le cas, tu ne pourrais pas faire de soustraction, tu n'aurais que deux cas possibles : soit le poids est sur le plateau qui lui est dédié (cas 1), soit il n'y est pas (cas 0). Alors avec 4 poids tu peux faire 2^4 (c'est-à-dire 2 puissance 4) combinaisons, c'est-à-dire 16 combinaisons. Les poids seraient : 1=2^0, 2=2^1, 4=2^2 g et 8=2^3 g, et tu mesurerais des masses allant de 0 à 17 g. En somme tu as deux signes (1 et 0) pour coder un nombre, en utilisant tes masses tu comptes en base binaire.

2. Supposons que tu puisses mettre les poids sur l'une ou l'autre des balances. Tu as maintenant trois cas : le poids est sur le plateau où est le sachet (cas -1), le poids n'est sur aucun plateau (cas 0), le poids est sur le plateau autre que celui du sachet (cas 1). Tu as 3^4 combinaisons, c'est-à-dire 81 combinaisons possibles. Mais comme ces combinaisons sont faites aussi avec "-1" cela signifie que tu peux compter de -40 à 40 (ne pas oublier le 0 au milieu !). Entendu que tu utilises 3 signes, tu utilises donc une base trinaire, appelée trinaire balancée car tu utilises les signes -1, 0 et 1, et les poids sont 1=3^0, 3=3^1, 9=3^2 et 27=3^3.

Ai-je répondu à ta question ?

C'est une autre langue. Je pige rien...

+ 1

John a écrit:Soit l'autre problème suivant :

Un employé a obtenu une prime de 200 euros. Il achète x objets coûtant x euros, y objets coûtant y euros, et z objets coûtant z euros.

Ce qui équivaut à : x²+y²+z² = 200.

La solution est : x = 6 ; y = 8 ; z = 10. Là encore, y-t-il un moyen de résoudre le problème par un raisonnement mathématique, et non en essayant successivement les diverses combinaisons avec des chiffres au hasard ?

Attention, il existe une autre solution (sans parler des solutions par permutation des symboles) : x=10, y=10, z=0
En fait une telle équation s'appelle équation diophantienne (une équation où les solutions sont des entiers).

La solution que tu as donnée est celle issue du triplet pythagoricien bien connu : 3²+4²=5² (Te souviens-tu du théorème 3,4, 5 ? "un triangle dont les côtés sont de mesures respectives 3, 4 et 5 est rectangle" (remarque que l'unité de mesure n'a aucune importance)", qui nous vient des Egyptiens de l'Antiquité, qui utilisaient une corde à 13 noeuds pour faire des angles droits). Donc 3²+4²+5²=50. D'où 6²+8²+10²=50*2²=200. Peut-être as-tu pensé au triangle rectangle pour résoudre cette équation, ce qui pourrait expliquer l'oubli de l'autre solution (bien plus facile)

De façon plus générale : tout nombre entier peut s'écrire comme somme de quatre carrés parfaits (démontré par Lagrange).
Et ce qui nous intéresse ici : tout nombre qui n'est pas de la forme (4^n)*(8m+7) avec n et m entiers peut s'écrire comme somme de trois carrés parfaits (démontré par Gauss me semble-t-il).

Ainsi 4^1*(8*5+7)=188 ne peut pas s'écrire comme somme de trois carrés !

Résolvons notre problème.
x²+y²+z²=200
Nous savons que l'une au moins des inconnues est <9 (sinon x², y² et z² sont toutes supérieures ou égales à 81, donc leur somme à 243, ce qui est impossible). Supposons donc que x<9. Nous avons 9 cas y²+z²=200-x² à traiter, quand x va de 0 à 8 (dans les entiers) : y²+z²=200, y²+z²=199, y²+z²=196, y²+z²=191, y²+z²=184, etc...

Bien sûr on pourrait utiliser un théorème de Fermat "Un nombre est la somme de deux carrés parfaits si chacun de ses facteurs multiplicatifs premiers pouvant s'écrire 4k+3 est élevé à une puissance paire", mais là on irait trop loin sans doute pour un mathématicien néophyte.

JPhMM a écrit:
Attention, il existe une autre solution (sans parler des solutions par permutation des symboles) : x=10, y=10, z=0

J'imagine qu'à partir du moment où l'on parle d'achat d'objets, x, y et z sont non nuls

Salut,

Pour le premier je ne vois pas : hormis remarquer qu'avec les poids 1, 3 et 9 on va jusqu'à peser des sachets de 13 kg puis on remarque que 13 + 27 = 40 mais on est obligé de justifier la suite et en examinant les cas.

Pour le second, si on prend la valeur entière de racine(200) on trouve 14 ou méthode citée plus haut (un au moins est plus petit que 9):

Ensuite il n'y a pas de recette miracle : on dresse un tableau de 1 à 14 pour x, y et z et on fait les calculs.

Je ne vois pas d'autre moyen...

A+

Celeborn a écrit:

JPhMM a écrit:
Attention, il existe une autre solution (sans parler des solutions par permutation des symboles) : x=10, y=10, z=0

J'imagine qu'à partir du moment où l'on parle d'achat d'objets, x, y et z sont non nuls

Certes, mais si c'est un problème mathématique, on peut dire j'achète 0 objet. C'est une proposition acceptable. Il faudrait donc rajouter au début, pour éviter toute confusion que chacun des x, y et z n'est nul.