Re: Un peu de mathématiques...

Apeiron Sam 9 Mai - 12:43

Très bien, donc :

Spoiler:

Certes, seulement la réponse à ma question devient : Non.
Un élève de lycée ne peut trouver cela, car il n'a pas les moyens d'estimer le pourcentage de ton argument et donc ne peut constater que cette stratégie est intéressante.
Ta stratégie ne serait valide pour ce topic que s'il est possible qu'un lycéen fasse la démonstration de ton argument, et je pense que ce n'est pas le cas.
L'idée est excellente, et elle s'applique aisément, seulement les calculs pour la démontrer sont délicats au point que nous-même ne les avons pas fait. C'est là son défaut.
Contrairement à ce qu'Elrohir pense, je n'ai pas posé d'énigme difficile jusqu'à maintenant, car le but était d'utiliser des mathématiques de lycée de la façon la plus ingénieuse possible. La plus difficile des énigmes que j'ai posées était l'énigme des prisonniers, qui ne requiert que le minimum en proba même si mener le raisonnement nécessite d'avoir vraiment bien compris ce minimum et une certaine ingéniosité.

Donc, j'aime beaucoup ton énigme, mais il lui manque la preuve, qui n'est pas accessible.
Pou l'avenir, je rajoute deux règles pour les énigmes mathématiques :
1) Elles doivent pouvoir être résolues par un lycéen
2) Si elle s'appuie sur des bases techniques, ces bases doivent faire l'objet d'un rappel.

Apeiron Mar 12 Mai - 16:04

Bon, je vais supposer que nous en avons fini avec le problème des douze prisonniers et le problème des 500 boîtes.Je vais proposer une autre type de problème. Ici il ne s'agit pas d'un problème stratégique, mais d'un problème d'optimisation.
J'espère ne pas contredire à mes deux conditions ci dessus, dans la mesure où le lycée n'offre que très peu d'outil pour l'optimisation. Le problème est que si je vous donne l'outil que je vais utiliser, le problème sera réduit à un simple calcul. Aussi, je vous prie d'excuser la licence que je prends : je vais d'abord vous présenter le problème, puis vous donner quelques pistes sans vous donner (pour le moment) de méthode de résolution.

Un marchand de jouet souhaite maximiser ses bénéfices.
Il fabrique deux types de jouet : de petits trains en bois, et de petites voitures en bois. Il lui faut 20 minutes pour fabriquer un petit train et 800g de bois, et il le revend 8 euros. Il lui faut 30 minutes pour fabriquer une petite voiture et 600g de bois, et il la revend 9 euros. Il fabrique les jouets le matin de 8h à 13h, puis fait une pause et les revend l'après midi. De plus, il ne peut se procurer que 7,2 kilos de bois. Enfin, sa popularité est telle qu'il vend dans l'après matin tout ce qu'il a fait le matin.
Combien de petits trains et de petites voitures a-t-il intérêt à faire ?

Astuce : une méthode consiste à réécrire l'énoncé sous forme de système, puis à tenter une résolution graphique (je sais, c'est vague, mais j'en dirai plus suivant ce que vous proposez).

Elrohir Mar 12 Mai - 17:01

Soit x le nombre de petites voitures qu'il fabrique en une matinée et y le nombre de petits trains fabriqués dans la même matinée. x et y appartiennent à IN

De 8 à 13h, il a 5h soit 300min pour produire ses jouets. Il faut donc que 20y +30x soit < ou = à 300.

Il dispose de 7,2kg de bois soit 7200g. Il faut donc que 800y + 600x soit < ou = à 7200.

Spoiler:

Apeiron Mar 12 Mai - 17:14

Bonne réponse d'Elrohir ! Smile

Je suis curieux de savoir comment tu as trouvé...

La formalisation m'a l'air correcte (juste, pourquoi tu prends x pour les voitures et pas pour les trains ? et à la fin tu parles de camions ^^ mais c'est pas grave... ^^).
J'appelle x le nombre de trains et y le nombre de voitures, et je note << pour "inférieur ou égal".

Le problème à résoudre est donc (réécriture de l'énoncé) :

Trouver le max de 8x+9y sous les contraintes 20x+30y << 300 et 800x+600y << 7200.

Encore bravo. ^^
Et les autres ?

Elrohir Mar 12 Mai - 17:38

Bonne réponse d'Elrohir !
Je suis curieux de savoir comment tu as trouvé...

Pure intuition ... Si si ... D'ailleurs c'est bizarre : tu es sûr de ne pas avoir fait de faute dans l'énoncé ?

La formalisation m'a l'air correcte (juste, pourquoi tu prends x pour les voitures et pas pour les trains ? et à la fin tu parles de camions ^^ mais c'est pas grave... ^^).

Oups ... Je vais éditer ça de suite ... Et puis voiture < train donc le plus petit symbole (x) pour les voitures et le plus grand (y) pour les trains.

Apeiron Mar 12 Mai - 17:46

Ben quoi... il est pas bien mon énoncé ? scratch

Pure intuition ? T'aurais pas tenter quelques calculs ?

Et puis voiture < train donc le plus petit symbole (x) pour les voitures et le plus grand (y) pour les trains.

Le x est plus tassé mais pas vraiment plus long que le y...
Ça n'a pas vraiment d'importance, mais la coutume est de classer les éléments logiquement, ou alors s'il n'y a pas d'ordre apparent d'utiliser x pour le premier type d'objet et y pour le second (c'est ce que j'ai fait).

Elrohir Mar 12 Mai - 18:10

Ben quoi... il est pas bien mon énoncé ?
Pure intuition ? T'aurais pas tenter quelques calculs ?

Spoiler:

Le x est plus tassé mais pas vraiment plus long que le y...
Ça n'a pas vraiment d'importance, mais la coutume est de classer les éléments logiquement, ou alors s'il n'y a pas d'ordre apparent d'utiliser x pour le premier type d'objet et y pour le second (c'est ce que j'ai fait).

Et puis d'abord j'appelle mes variables comme je veux ! Nah !

Apeiron Mar 12 Mai - 18:20

Ah, ok. Effectivement.
En fait, la méthode graphique permet de prouver que le point que tu as choisi était bien le bon, et après il convient de finir comme tu l'as fait. Parfois, c'est un autre point qui convient, ou alors le choix de points crédibles peu s'élargir avec l'ajout d'autres contraintes.

J'attends de voir ce que pensent les autres, et ce soir je livrerai la méthode graphique.

Apeiron Mer 13 Mai - 10:49

Bon, j'ai attendu un peu plus que prévu.
Voilà maintenant la méthode graphique.

Le problème est : Trouver le max de 8x+9y sous les contraintes 20x+30y << 300 et 800x+600y << 7200.

Or, 20x+30y << 300 <=> y << 10 -2/3 x
et 800x+600y << 7200 <=> y << 12 -4/3 x
Ce sont les équations de deux droites à tracer, et la zone positive située sous ces droites est donc la zone où les contraintes sont respectées :

Un peu de mathématiques... - Page 5 Optim.th

Ensuite, il suffit de regarder la fonction à maximiser : 8x + 9y
Les droites représentant cette fonction sont les droites de la forme 8x + 9y = a <=> y = a/9 -8/9 x où a est un nombre quelconque, donc les droites de coefficient directeur -8/9 (toutes les droites parallèles à la droite en bleu).
Pour maximiser la fonction sous les contraintes, il suffit de trouver le point de la zone où les contraintes sont respectées par lequel passe la droite de coefficient -8/9 la plus en haut à droite (c'est la droite bleue).
Pour voir que c'est bien celle en haut à droite, il suffit de comparer les coefficient des droites. Or -4/3 < -8/9 < -6/9, donc c'est bien le point A qui est candidat (la droite bleue passe bien entre les deux droites rouges).
Le point candidat A est le croisement des deux droites, donc les coordonnées (x,y) du point A s'obtiennent avec le système :

20x+30y = 300 et 800x+600y = 7200, qui admet une solution unique : (3,8 ).

Ainsi, x=3 et y=8.
Au passage nous savions (enfin, les matheux le savaient) que l'optimisation était possible, car la zone où les contraintes sont respectées forment une surface fermée et que la fonction à maximiser est continue, donc elle atteint forcément un maximum sur la surface. C'est ce qui justifie que l'unique point candidat est bien solution.

Elrohir a deviné que c'était le point A, mais ça aurait pu être les points (0,10) si le coefficient de la droite représentative de la fonction à maximiser avait été supérieur à -2/3, ou (9,0) si le coefficient de la droite représentative de la fonction à maximiser avait été inférieur à -4/3.
Et avec une autre contrainte appropriée il aurait pu y avoir deux points candidats qui ne sont pas sur des axes.

Apeiron Jeu 14 Mai - 11:15

Il peut être intéressant de noter que ces problèmes ont une sorte de symétrie. Ce n'est pas du tout essentiel pour résoudre le programme que j'ai noté, mais je le donne à titre d'information.

Le programme :

Trouver le max de 8x1+9x2 sous les contraintes 20x1+30x2 << 300 et 800x1+600x2 << 7200.

(où x1 est la quantité de train et x2 la quantité de voitures)
est appelé programme primal, et il admet comme programme dual :

Trouver le min de 300x3 + 7200 x4 sous les contraintes 20x3 + 800x4 >> 8 et 30x3 + 600x4 >> 9.

(où x3 représente le temps, x4 la quantité de bois et où >> signifie "supérieur ou égal")

Pour voir le lien entre les deux types de programme, il suffit en fait de les écrire sous forme saturée :

Trouver le max de 8x1+9x2 sous les contraintes 20x1 + 30x2 + x3 = 300 et 800x1 + 600x2 + x4 = 7200.
Trouver le min de 300x3 + 7200 x4 sous les contraintes 20x3 + 800x4 + x1 = 8 et 30x3 + 600x4 + x2 = 9.

En fait, les x3 et le x4 de la première équation n'ont pas tout à fait le même rôle que dans la seconde équation et vice-versa pour x1 et x2, donc il faudrait plutôt récrire les programme de cette façon :

Trouver le max de 8x1+9x2 sous les contraintes 20x1 + 30x2 + x3' = 300 et 800x1 + 600x2 + x4' = 7200.
Trouver le min de 300x3 + 7200 x4 sous les contraintes 20x3 + 800x4 + x1' = 8 et 30x3 + 600x4 + x2' = 9.

(de plus, le x3' et le x4' représentent ici des quantités volontairement négatives pour conserver la symétrie d'écriture malgré le changement de signe)

Les deux systèmes sont reliés par les équations :

x1.x3' = 0
x2.x4' = 0
x1'.x3 = 0
x2'.x4 = 0

qui permettent dans certains cas de retrouver les solutions de l'un à partir de l'autre.

Dans notre exemple, nous avons x1=3 et x2=8, et comme les deux contraintes sont saturées (le point A est sur les deux droites rouges) nous avons x3' = x4' = 0.
Nous obtenons alors :

3.0 = 0
8.0 = 0
x1'.x3 = 0
x2'.x4 = 0

Ce qui ne nous aide pas vraiment...
En fait, ces équations sont plutôt utiles quand certaines contraintes sont saturées et pas d'autres.

Après résolution, le programme dual admet comme solution x3 = 1/5 et x4 = 1/200 (avec x1' = x2' = 0).
Notez que 300/5 + 7200/200 = 60 + 36 = 96.

Elrohir Ven 15 Mai - 2:15

Euh ... Comprend paaaaaas ...

Spoiler:

Apeiron Ven 15 Mai - 9:03

J'ai cherché à vous faire le problème le plus simple possible. Qu'une méthode naïve fonctionne dans ce cas n'est pas une surprise. Et ce n'est pas une méthode inductive que tu as utilisée, car il n'y a pas une succession d'expériences amenant à une théorie.
J'ai vraiment l'impression que tu mélanges plusieurs notions.

Elrohir Ven 15 Mai - 12:18

Bah c'est pas le premier problème mathématiques que je fais quand même ... D'ailleurs ya plein de règles inductives qui me reste de ma terminale :

- Si l'exercice a un petit 1, il a sûrement un petit 2 ...
- Si tu ne tombe pas sur un nombre entier, refais tes calculs.
- Un problème mathématique a toujours une réponse.
- etc.

Le problème de la méthode "classique" c'est qu'elle peut être très longue en justification, utiliser une méthode "naïve" comme tu dis permet parfois de gagner un temps précieux ... une de mes plus grande joie est de démontrer en deux lignes ce que les autres démontrent en cent ... (C'est arrivé au lycée, peut-être que Derich s'en souviens : c'était un nouveau chapitre et il fallait démontrer qu'un triangle était rectangle en utilisant un nouveau théorème très long ... Je suis arrivé au même résultat en utilisant Pythagore ...).

Apeiron Ven 15 Mai - 17:45

Sauf que là il s'agit de chance. Si c'était un QCM,, tu aurais peut-être eu les points, mais il t'aurait au moins fallu les deux autres points candidat.

Si tu veux, je te mets au défi.
Résous le problème en sachant que cette fois il vend les voitures 6 euros.

Elrohir Ven 15 Mai - 18:07

Mais je sais bien qu'il est possible de compliquer le problème !!! (D'ailleurs je pensais que tu l'aurais fait pour le premier c'est pour ça que je n'étais pas sûr de ma solution) Je dis simplement que que pour résoudre un problème, il est parfois plus rapide d'utiliser ma méthode naïve ... Et si ça marche pas (tel que je te connais c'est le cas avec les voitures à 6€) j'utilise la méthode rigoureuse. En fait je pensais utiliser la méthode rigoureuse dès le départ parce que je pensais justement que tu avais fait un truc tordu ... Comme je n'ai rien pour faire les graphes (je savais lesquels faire mais pas comment) j'ai tenté le coup avec ma méthode et ça a payé ...

Apeiron Ven 15 Mai - 19:20

Soit.
Dans ce cas tu tomberas sur des résultats faux si tu continues d'utiliser une telle méthode. Mais manifestement ça n'a pas l'air de te déranger.
A priori, il n'y a rien à rajouter sur le sujet, vu que les autres ne réagissent pas.

Nouveau sujet :

Quatre cartes comportant un chiffre sur une face et une lettre sur l'autre, sont disposées à plat sur une table. Une seule face de chaque carte est visible. Les faces visibles sont les suivantes : D, 7, 5, K. Quelle(s) carte(s) devez-vous retourner pour déterminer la ou les carte(s) qui ne respecte(nt) pas la règle suivante : Si une carte a un D sur une face, alors elle porte un 5 sur l'autre face. Il ne faut pas retourner de carte inutilement, ni oublier d'en retourner une.

Elrohir Ven 15 Mai - 20:18

Spoiler:

Apeiron Sam 16 Mai - 11:02

Yep. ^^

Voici un lien Wikipédia qui t'en dira plus sur le sujet s'il t'intéresse :
http://fr.wikipedia.org/wiki/T%C3%A2che_de_s%C3%A9lection_de_Wason

Elrohir Sam 16 Mai - 12:50

Cool ! Je suis doué en réfutation alors ! A mon tour !

Un lotissement de trois maisons doit être équipé d'eau, de gaz et d'électricité. La règlementation interdit de croiser les canalisations pour des raisons de sécurité. Comment faut-il faire ?

Un peu de mathématiques... - Page 5 Water_gaz_electricity_Dudeney

A, B et C sont les maisons. Les autres bâtiments sont des usines (W = water, G = gaz et E = électricité).

Apeiron Dim 17 Mai - 14:07

Connu, connu...

Spoiler:

Elrohir Dim 17 Mai - 14:33

Bien joué Apeiron !

Spoiler:

Apeiron Dim 17 Mai - 15:09

La démonstration doit se faire facilement, non ?
A moins que ce soit un truc retors style le théorème des quatre couleurs... scratch

Elrohir Dim 17 Mai - 18:08

J'ai dit compliqué pour moi ... C'est quoi ton théorème des 4 couleurs ?

Apeiron Dim 17 Mai - 18:57

Le théorème des quatre couleurs est un théorème assez difficile à montrer qui affirme en gros que si tu divises un pays en régions limitrophes connexes (d'un seul morceau), alors il te suffira de quatre couleurs pour les colorier sans que deux régions limitrophes ne soient de la même couleur.

L'article de Wikipédia donne en exemple la carte de la Russie :
http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_quatre_couleurs

Le théorème des cinq couleurs (le même avec cinq couleurs au lieu de quatre) est beaucoup plus facile à montrer.
Pour quatre couleurs, le problème a plus d'un siècle et n'a pu être démontré assez récemment qu'à l'aide d'un ordinateur (notamment Coq, dont j'ai déjà parlé me semble-t-il dans mon article à propos de la thèse de Church) afin d'évaluer tous les cas possibles.
Sa célébrité vient à la fois du fait qu'il s'agit d'un des problèmes NP (compliqué informatiquement parlant) qui s'exprime de façon très simple, et que sa résolution a partagé la communauté scientifique, puisque certains hésitaient à valider une preuve informatique.

Elrohir Dim 17 Mai - 19:37

Ah ok ... Et on ne l'a pas prouvé autrement depuis ?

Contenu sponsorisé