Enigme : équilibrage d'une balance à plateaux ...

[Patastronch]

Mais sur d'autres séries de poids, j'ai des résolutions qui prennent beaucoup de temps quelque soit l'algo.

Donc, je ne désespère pas de trouver une façon de faire moins bourrin que l'outil informatique, ce qui permettrait (je l'espère) de rendre au final l'outil informatique (je reste quand même un gros flemmard d'informaticien :lol2: ) plus rapide que ce que j'ai actuellement ...

Le poids est bien 165580282.

Ce probleme est np-complet (vulgairement, problème irrésolevable avec un algo de complexité polynomial), donc si les poids initiaux n'ont pas une certaine
structure simplificatrice ou que le nombre de poids est trop grand, trouver la solution exacte en un temps raisonnable est impossible même avec le plus puissant des ordinateurs.
Généralement on utilise des algo de type séparation et évaluation (branch and bound) avec un heuristique judicieusement choisis pour résoudre les probleme np-complet. Sinon si on veut seulement une bonne solution (pas forcément la meilleur) on peut utiliser des metaheuristique (algo genetique, recherche taboo ...). Enfin j'ai la net impression qu'on peut déduire un schéma d'approximation polynomial sur ce probleme et si c'est le cas on peut en déduirte un algo polynomial qui renvoit une solution a au plus epsilon pres (epsilon fixé par l'utilisateur) de l'optimal. Mais ce n'est pas parcequ'un algo est polynomial qu'il est efficace pour autant !

[Flodelarab]

Apres savoir qui s'est trompé dans ses calculs (parceque selon toi 165580282 est possible et selon Darkpage la somme de tous les poids du premier plateau est 165580190) j'en sais rien mais si les calculs de Darkpage sont bon il a trouvé la solution maximale.

Je m'étonne que tu t'obstines.

"La somme de tout les éléments du premier plateaux" (celui de droite, en fait) "= 165580290 "
Je suis d'accord. Moi aussi, j'ai une calculatrice qui fait les sommes.
Mais il n'a jamais dit que c'était le poids de l'équilibre.
Moi je dis que ce poids n'est pas atteignable avec les poids du plateau de gauche.

Ma liste donne l'ensemble des poids que les 2 côtés peuvent atteindre ! Donc ceux qui donnent l'équilibre. Le plus gros est bien: 165580282 < 165580290

D'ailleurs 165580290 - 165580282 = 8
Le seul poids qui ne sera pas mis à droite est celui de 8

[Patastronch]

Je m'étonne que tu t'obstines.

"La somme de tout les éléments du premier plateaux" (celui de droite, en fait) "= 165580290 "
Je suis d'accord. Moi aussi, j'ai une calculatrice qui fait les sommes.
Mais il n'a jamais dit que c'était le poids de l'équilibre.
Moi je dis que ce poids n'est pas atteignable avec les poids du plateau de gauche.

Ma liste donne l'ensemble des poids que les 2 côtés peuvent atteindre ! Donc ceux qui donnent l'équilibre. Le plus gros est bien: 165580282 < 165580290

D'ailleurs 165580290 - 165580282 = 8
Le seul poids qui ne sera pas mis à droite est celui de 8

La somme fait selon lui 165580190< 165580282 !
Donc tu vois bien qu'un de vous 2 s'est planté dans ses calculs, je sais pas lequel j'ai pas vérifié.

ENsuite il dit :


soit 49 de plus que le plus gros elements du second plateaux
Pour combler ce 49 manquant on remarquera que sur le second plateaux nous possédons 2 + 13 + 34 = 49

Voila ce qu'il dit.
Equilibre donc atteignable et maximal puisque c'est la somme de tous les poids du premier plateau. TOut cela est vrai uniquement si les calculs sont justes bien entendu. Tant que ce point n'est pas remis en cause je vois pas ou se trouve le probleme dans son raisonnement.

Si apres tu confirmes que la sommes vaut 165580290 dans ce cas tout est faux dans la suite de son raisonnement. Mais je repete, j'ai fait aucun calcul (un vrai feneant ne fait pas de programme tout court) donc je ne sais pas qui a la bonne somme.

[scelerat]

Je ne sais pas si qu'elqu'un a remarqué la propriété suivante :
de chaque coté on a
d'abord 1
puis 3=1+2
puis 8=5+3

2
5=3+2
13=8+5
.......
Bon je vous fait pas un dessin sachant ca on arrive
a des plataux pouvant porter les poid suivant :
a a+1
2a+1 3a+2
5a+3 8a+5
...
Et ca simplifie le probleme je pense...
Je vais chercher ca

On a bien d'un cote les termes pairs et de l'autre les termes impairs d'une suite de Fibonacci, mais on a un 150 en plus pour le premier plateau. A mon avis, c'est sur ce 150 que repose le calcul...
Supposons qu'on n'ait pas le 150, on doit pouvoir montrer qu'on ne peut pas trouver de solution (par l'absurde : si on met le plus grand poids d'un cote, il manque 1 pour equilibrer avec tous ceux de l'autre cote, donc on retire ce poids, et on recommence en echangeant les cotes).
Donc on est ramene a trouver un ensemble de (qu'on omet) et un de (qu'on prend en sus du plus grand) tels que .
La plus grande somme inferieure a 151 qu'on puisse faire avec des est 143, ca marche avec le 8, pas la peine de chercher plus loin.

[Dark Page]

je suis bien heureux de voir que ma première idée était la bonne
en realité j'avais meme pas vu le 150 en plus qui permet le raisonnement

Maintenant j'aimerais quand meme comprendre pourquoi
Flodelarab a trouvé un grand nombre d'equilibrage possible
alors que celon toi scelerat (lol pas pu m'empecher)
il n'y a qu'une possibilité

De plus (autant pour moi) flodelarab a raison j'ai fait une erreur
c'est bien un 2 et non un 1 mon raisonnement tombe donc a l'eau
je suis d'avis moi aussi que l'on resolve ce probleme de facon mathematique
et non informatique ( aucun interet )


la reponse de scelerat a l'air bonne meis c'est pas bien clair tu pourrait pas nous donner un raisonnement plus detailler

[scelerat]

je suis bien heureux de voir que ma première idée était la bonne
en realité j'avais meme pas vu le 150 en plus qui permet le raisonnement

Maintenant j'aimerais quand meme comprendre pourquoi
Flodelarab a trouvé un grand nombre d'equilibrage possible
alors que celon toi scelerat (lol pas pu m'empecher)
il n'y a qu'une possibilité

Il n'y a qu'une possibilite parce qu'on prend le plus grand terme du second plateau. Mais la suite est telle que si on rajoute (ou enleve) un terme de chaque cote, ca marche pareil (sauf peut-etre le programme, ou on a des overflows). Donc, par exemple si on enleve 102334155 et 165580141, la solution est 63246127, et si on ajoute les termes suivants, 267914296 pour le premier plateau et 433494437 pour le second, elle devient 433494578.

Floredelab a toutes les solutions intermediaires...