Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- Ernst
- 28-04-2024 13:13:37
Suite et fin (il était temps)
Bon, donc j'ai une formule, super, sauf que voilà, les résultats ne coïncident pas toujours avec mes valeurs informatiques, aïe aïe aïe... Déception bien sûr, vérification, que pouic, scrutation, toujours rien, découragement, investigation avec décomposition pas à pas et liaison par liaison, et là enfin, ouf, je tombe sur l’erreur !
En fait quand le programme terminait un parcours, il rajoutait la distance du retour grâce au tableau des distances, sauf que la liaison 2-1 est à zéro puisque c’est un vis-à-vis, et donc il n’ajoutait rien du tout. Et comme le tableau des distances était juste, voilà aussi pourquoi les parcours ne terminant pas sur la maison 2 restaient exacts...
Bref, terminé, heureux je suis.
- Ernst
- 28-04-2024 13:03:28
La suite.
Pour aller plus loin, une fois un parcours valide obtenu je décide de tester systématiquement tous les échanges possibles des maisons deux à deux et d’appliquer celui avec le meilleur gain. En recommençant sur le parcours ainsi amélioré jusqu’à stagnation avant nouveau tirage, un autre bond considérable puisque j’arrive cette fois à la trentaine de maisons - à condition d’user de tous les processeurs et de laisser tourner quelques heures quand même - au delà c’est mort.
À force d’y penser jour après jour, une nouvelle idée me vient. Les parcours les plus courts commencent tous par 1-4-5-...-… et ils se terminent tous par ...-6-3-2. Je me dis que je pourrais peut-être forcer ces positions et ne tirer au hasard que les maisons du centre, ce qui me ramènerait à des configurations plus efficaces. Et là pof, magique, cinquante, cent, deux cents, cinq cents maisons, les résultats sortent en quelques dizaines de secondes pour les plus grands nombres, plus aucune limite, le bonheur.
Après analyse, la config’ est toujours la suivante :
ce qui donne deux parcours pour le plus court grâce à la symétrie haut/bas sur la terminaison.
À partir de là il est donc facile d'en tirer une formule générale.
- Ernst
- 28-04-2024 12:59:32
La suite.
Approche suivante, constituer deux listes distinctes, celle des nombres impairs et celle des nombres pairs, qui seront mélangées séparément. Il est alors facile de construire un parcours alterné immédiatement valide aux vis-à-vis près, et pour ceux-là, échanger la maison qui pose problème avec sa voisine du même côté permet de lever l’obstacle. Bref, gros progrès, je passe au-delà des vingt maisons par rue facile. Avec dix programmes moulinant en parallèle (processeur multi-coeur) et en laissant tourner une petite heure je suis tout heureux d’établir le parcours minimum pour vingt-quatre maisons, yé !
Ceci dit, la croissance factorielle est un cauchemar.
- Ernst
- 28-04-2024 12:57:38
Allez, la genèse du truc. Un peu long mais faut ce qu’il faut.
Au départ, je suis un adepte des simulations, je tire donc des parcours au hasard, calcule la distance et ne retiens que les plus courts, en vérifiant qu’ils soient valides. Pour le tirage, je mélange simplement l’ordre du tirage précédent, ça va super vite. Pour les distances je calcule un tableau préalable avec marquage à zéro des impossibilités (même parité et vis-à-vis), ce qui fait qu’en une seule consultation j’obtiens soit la distance de la liaison, soit l’impossibilité du parcours tout entier. Avec ça et en forçant la maison 1 à la première place pour ne pas perdre de temps avec d’autres points de départ (je voulais savoir s’il y avait plus court en partant d’ailleurs, la réponse est non) le résultat est quasi immédiat. Par contre cela devient difficile quand le nombre de maisons augmente, avec une limite pratique pour atteindre les seize maisons...
C’est normal. Tirer les parcours au petit bonheur la chance, c’est avoir de moins en moins de dispositions qui respectent les contraintes et finir par passer tout son temps à éliminer les parcours interdits.
- Ernst
- 28-04-2024 12:51:20
Bonjour,
Et voilà, problème résolu pour n’importe quel nombre de maisons supérieur à 4 et pair. Les paramètres :
n = nombre de maisons
a =distance entre les maisons
b = largeur de la rue
parcours minimum = $ \left( n-4 \right) \sqrt {{a}^{2}+{b}^{2}}+3\,\sqrt {4\,{a}^{2}+{b}^{2}}+b$
Je suis tout content d'avoir trouvé ça, maintenant je vais détailler...
- Ernst
- 22-04-2024 14:07:49
Eh ben, y'en a qui cogitent !
Bonjour,
En fait à l’inscription, j’avais passé un peu de temps à regarder les échanges courants, et celui-ci faisait partie de ceux qui m’étaient restés en tête.
J’y reviens parce que les parcours les plus courts ne tiennent pas compte de la largeur de la rue pour revenir au point de départ une fois qu’il a terminé sa tournée, honte à moi. Les plus longs c’est ok, mais les plus courts sont finalement de 216,54 mètres pour huit maisons et 302,7 pour douze maisons.
Ce qui fait, soit dit en passant, que les douze maisons représentent maintenant presque 5 % d’augmentation par rapport au plus « méritant » que le facteur avait expérimenté avec huit maisons, et une fois de plus les syndicats râlent tout ce qu'ils peuvent, normal.
- Bernard-maths
- 15-04-2024 16:51:09
Eh ben, y'en a qui cogitent !
Mais la politique est partout !
merci Ernst ... B-m
- Zebulor
- 15-04-2024 13:45:18
Bonjour,
merci Ernst pour ce moment de distraction politico-mathématique ! :-)
- Ernst
- 15-04-2024 12:53:46
2) rue en quart de cercle, largeur 8m, rayon intérieur de 100m, miasons situées à 0°, 30°, 60° et 90°, face à face.
Suite à l'augmentation du nombre de maisons dans une tournée et toujours vigilants quant aux charges de travail, les syndicats ont obtenu en compensation que les rues courbes ne soient plus desservies, un panneau de boîtes aux lettres étant simplement disposé à l’extrémité de chacune. Après de tapageuses réactions de principe, le gouvernement s’est empressé de céder – au nom du compromis démocratique bien sûr – trop content qu’il était de pouvoir annoncer une réduction massive de fonctionnaires aux prochaines élections.
Pas de chance, vraiment.
- Ernst
- 15-04-2024 12:49:41
Malheureusement l’histoire ne s’arrête pas là. Ce supérieur hiérarchique ayant été promu vers un poste moins sensible aux frénésies expérimentales, son successeur, une femme déterminée ayant pour religion le sacro-saint rendement, décide de reprendre les choses en main. Elle redessine la carte des distributions des facteurs et renforce la tournée de chacun en y ajoutant quatre maisons, paf.
À grands coups de PowerPoint, elle saura montrer que les parcours 1-4-5-8-11-10-7-12-9-6-3-2 et 1-4-5-10-11-8-9-12-7-6-3-2 ont une longeur de 294,70 mètres, et qu’ils sont donc équivalents aux tournées actuelles à 2 % près, autant dire rien. Et comme elle saura être généreuse avec les petits fours aux réunions, la mesure passera. Les élections aussi d’ailleurs. La méritocratie devenant tout à coup moins prioritaire, notre facteur gardera finalement le même salaire mais aura à s’occuper de douze maisons au lieu de huit, car ainsi va la fonction publique.
(les récréations mathématiques image du monde)
- Ernst
- 15-04-2024 12:47:07
Parmi ces 18 trajets, quel(s) (so)(e)st le(s) plus court(s) ??? Et le plus long, du coup !?
[...]
1) rue rectiligne de 8m de large, maisons (boites aux lettres) espacées de 20m.
Bonjour,
Soit un facteur qui arrive devant la maison n°1 et qui fait sa distribution en respectant les contraintes de l’énoncé, puis qui revient à son point de départ pour continuer sa tournée. Le parcours le plus court fait 208,54 mètres avec 1-4-7-6-3-8-5-2 les jours pairs et 1-6-7-4-5-8-3-2 les jours impairs. Notre facteur étant d’origine oxymorienne, il est partisan à la fois d’une variété dite méthodique et d'une méthode dite variée, c'est pour ça.
Le jour où il apprend que le gouvernement entend récompenser les fonctionnaires au mérite, notre facteur adopte l’ordre 1-4-5-2-7-6-3-8 qui, pour exactement la même distribution, lui fait maintenant parcourir 288,81 mètres. Peu instruit du mérite et des promesses électorales, il s’attend à une augmentation salariale d’au moins 38 %, normal.
Dans le même temps son supérieur hiérarchique, girouette administrative peu appréciée par la base, délaisse l’ancestral « gouverner c’est prévoir » pour un bien plus moderne « expérimenter c’est gouverner ». Il impose donc à tout son personnel un changement obligatoire d’habitudes, juste pour voir. Notre sympathique facteur, peu convaincu il faut bien le dire, s’emploie alors à « expérimenter » 1-6-3-2-7-4-5-8 et 1-8-3-6-7-2-5-4 qui tous les deux conservent ces 288,81 mètres, ouf.
- Bernard-maths
- 25-11-2023 14:28:09
Ne pas oublier les habits du facteur, dans les virages il rase les murs ... merci.
- Zebulor
- 25-11-2023 11:57:55
Bonjour,
Parmi ces 18 trajets, quel(s) (so)(e)st le(s) plus court(s) ??? Et le plus long, du coup !?
En effet Bernard, j'y avais pensé, soyons concrets. Et solliciter la mairie pour lui aménager des passages piétons obliques en conséquence.
- Bernard-maths
- 23-11-2023 17:07:37
Bonjour à tous !
Vous tournez en rond ? ou quoi ?
Pensez plutôt à ce pauvre facteur, certes un peu bizarre, mais que se passe -t-il quand il est vraiment pressé ?
Parmi ces 18 trajets, quel(s) (so)(e)st le(s) plus court(s) ??? Et le plus long, du coup !?
On suppose que le facteur peutr se promener sans contrainte ... de la 1ère maison à la dernière servie, ET retour à la 1ère !
Je vous propose deux types de rue :
1) rue rectiligne de 8m de large, maisons (boites aux lettres) espacées de 20m.
2) rue en quart de cercle, largeur 8m, rayon intérieur de 100m, miasons situées à 0°, 30°, 60° et 90°, face à face.
Wiwaxia peut faire un programme ...
Bernard-maths
- Pierre CAMI
- 23-11-2023 16:29:16
Bonjour à toutes et tous
C'est sur que je me suis trompé 3 fois, mais j'ai réussi à avoir les réponses
que j'attendais.
Il n'est pas nécessaire d'espérer pour entreprendre ni de réussir pour persévérer.(G.O)
Bonne fin de journée