Mathématiques - Enigme : équilibrage d'une balance à plateaux ...

Enigme : équilibrage d'une balance à plateaux ...
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: barbouille94

Bonjour, je vous propose cette petite énigme :

But :
- équilibrer une balance à plateaux (Simple ?

Pas sûr

, voir les contraintes)

Contraintes :
- la liste des poids par plateau est imposée (les poids disponibles pour le plateau de droite ne peuvent pas aller sur le plateau de gauche et vice-versa)
- le poids d'équilibre doit être le plus grand possible

Exemple simple :
- poids pour le plateau de droite : 100,30,30,29,20
- poids pour le plateau de gauche : 70,70,9,7
- le poids d'équilibre maximum sera ici de 149g par plateau (100+29+20 contre 70+70+9)

Poids à utiliser :
- pour le plateau de droite :

Code:

- pour le plateau de gauche :

Code:

Bon !! Ok !! C'est de la belle balance (165 tonnes) !!

A vos bouliers ...

Posted by: Flodelarab

En tout cas, il n'y a que $2^{41}$ équilibres maximums à tester. Trop facile.

Posted by: Patastronch

Citation:

Posté par Flodelarab

En tout cas, il n'y a que $2^{41}$ équilibres maximums à tester. Trop facile.

Equilibre maximum 'potentiel' j'aurais dit !
Suffit de commencer par le plus grand equilibre possible pardi !

Posted by: barbouille94

Citation:

Posté par Patastronch

Equilibre maximum 'potentiel' j'aurais dit !

Il y a bien une solution. C'est

... Je ne la donnerais que plus tard

Je dirais juste que ça dépasse la centaine de tonnes ...

Citation:

Posté par Patastronch

Suffit de commencer par le plus grand equilibre possible pardi !

Par contre, je ne l'ai trouvée que de façon informatique

en commençant effectivement par le plus grand possible.

Par contre, je ne vois pas encore comment s'y prendre si on nous pose la colle en bord de plage avec comme seules armes :
- un maillot
- de la crême solaire
- les lunettes
- un papier
- un crayon
- et à la rigueur une gomme ...

Alors ? Qui aura le boulier le plus rapide ?

Posted by: Dark Page

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

Posted by: Patastronch

Le poids le plus lourd du plateau de gauche est strictement plus lourd que la somme de tous les poids du plateau de droite, il est donc pas utilisable. Le poids maximal qu'on peut donc expérer atteindre est inférieur ou égale à la somme de tous les poids du plateau de gauche sauf le plus lourd, soit 102334156.
On a déjà une borne sup a notre problème !

Or on remarque que la somme des n poids les plus léger du plateau de gauche est égale au poids du n+1 ème poids le plus léger du plateau droit + 1 (ou + le poids le plus léger du plateau droit).

Donc l'équilibre de poids maximal est 102334156 avec à droite le poids le plus léger et le plus lourd et à gauche tous les poids sauf le plus lourd. Preuve de maximalité évidente puisqu'on a atteint notre borne sup vu plus haut :)

Posted by: Patastronch

arg me suis planté dans ma relation, c 'est donc tout faux. C'est pas +1 mais -1.

Posted by: Patastronch

Trouvez l'erreur :
Lepoids le plus lourd du plateau de gauche est supérieur a la somme de tous les poids du plateau de droite. Donc innutilisable, on le retire.

La somme restante possible avec tous les poidsdu plateau gauche est strictement inferieur au poids le plus lourd du plateau droit, donc on le retire.

Etc... jusqu'a qu'il n'y ai plus de poids.

Exemple:
Gauche :
1
3
8
21

Droite :
2
5
13
34

34>21+8+3+1=33
On retire 34.
21>13+5+2=20
On retire 21
13>8+3+1=12
On retire 13
...

Relations utlisées pour la récurrence :
Le neme poids du plateau gauche =somme des n premiers poids de droite +1
Le nème poids du plateau droit = somme des n-1 premiers poids de gauche +1

Pas d'erreur ? Alors c'est que c'est impossible. Mais vu que l'auteur dit avoir trouver une solution c'est que j'ai du me planter quelquepart mais je vois pas ou.

Posted by: Dark Page

L'erreur vient de ta première hypothese
qui est fausse
La somme de tout les elements du premier plateaux =
165580190
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
soit la plus gros poids est la somme de tout les element de la première balance, on ne peux pas faire plus, et la somme du plus gros du second avec 2, 13, 34.

voila

Posted by: Patastronch

Citation:

Posté par Dark Page

L'erreur vient de ta première hypothese
qui est fausse
La somme de tout les elements du premier plateaux =
165580190
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
soit la plus gros poids est la somme de tout les element de la première balance, on ne peux pas faire plus, et la somme du plus gros du second avec 2, 13, 34.

voila

Je te fais confiance pour les calculs :) Je les ai pas fait j'ai conjecturé que ca restait vrai, apres avoir vérifié les 6 premieres occurences, ce qui n'est visiblement pas le cas d'apres ce que tu dis.

Bravo !

Posted by: barbouille94

Citation:

Posté par Patastronch

...Pas d'erreur ? Alors c'est que c'est impossible. Mais vu que l'auteur dit avoir trouver une solution c'est que j'ai du me planter quelquepart mais je vois pas ou.

Vous avez réussi à me faire douter des poids donnés dans l'énoncé de base

.
Du coup je viens de vérifier et j'arrive bien à une solution 165tonnes et des poussières (je ne donne pas les poussières, nananère

).

Et il y a plus de poids utilisés côté droit que côté gauche ...

Posted by: Flodelarab

Pardon pour l'auteur du post mais je crois que l'obstacle principal de cette énigme est la flemme et non la difficulté.

En effet, on peut faire la liste des poids atteignables sur chaque plateau et comparer. Cette méthode s'apparente à la création de la liste des diviseurs d'un nombre connaissant les nombres premiers qui le composent. Pas difficile mais fastidieux.

Avec un petit programme Python (que je peux vous livrer), on obtient la liste suivante:

0
235
238
324
327
358
361
371
374
612
615
701
704
735
738
748
751
1599
1602
1688
1691
1722
1725
1735
1738
4183
4186
4272
4275
4306
4309
4319
4322
10948
10951
11037
11040
11071
11074
11084
11087
28659
28662
28748
28751
28782
28785
28795
28798
75027
75030
75116
75119
75150
75153
75163
75166
196420
196423
196509
196512
196543
196546
196556
196559
514231
514234
514320
514323
514354
514357
514367
514370
1346271
1346274
1346360
1346363
1346394
1346397
1346407
1346410
3524580
3524583
3524669
3524672
3524703
3524706
3524716
3524719
9227467
9227470
9227556
9227559
9227590
9227593
9227603
9227606
24157819
24157822
24157908
24157911
24157942
24157945
24157955
24157958
63245988
63245991
63246077
63246080
63246111
63246114
63246124
63246127
165580143
165580146
165580232
165580235
165580266
165580269
165580279
165580282

Le poids maximum atteignable par les deux plateaux est donc le dernier chiffre.

Voilà. Satisfait ?

Posted by: Imod

Citation:

Posté par Flodelarab

Avec un petit programme Python (que je peux vous livrer), on obtient la liste suivante:

0
235
238
324
...
165580269
165580279
165580282

L'exemple type de ce que je n'aime pas en maths

L'informatique est un outil fantastique mais ce n'est qu'un outil et j'ai tendance à préférer ce que je peux faire en m'en passant

Imod

Posted by: nuage

Salut,

Citation:

Posté par Imod

L'exemple type de ce que je n'aime pas en maths

Imod

Normal, c'est pas des maths.
Ce que l'on peut espérer (en math) c'est une preuve que le programme de Flodelarab est juste. Personnellement je le crois volontiers. Mais il est vrai que le résultat n'a pas d'importance.
J'espère que l'auteur de cette énigme va nous donner un raisonnement simple conduisant au résultat.
Sinon cette énigme serait plus à sa place dans le forum informatique.

Quand même bravo Flodelarab.

Posted by: Patastronch

Citation:

Posté par nuage

Quand même bravo Flodelarab.

Euh faut lire les cocos ... Darkpage a pondu la solution depuis longtemps et sans programme (qui était la contrainte de l'énnoncé au passage)

Posted by: Flodelarab

Citation:

Posté par Patastronch

Euh faut lire les cocos ... Darkpage a pondu la solution depuis longtemps et sans programme (qui était la contrainte de l'énnoncé au passage)

J'ai beau lire et relire les posts de Darkpage, je ne vois nullepart le nombre 165580282
(en fait j'ai fait rechercher par firefox

informaticien = flemmard

)

Posted by: Flodelarab

Et coco=communiste donc je partage mon code:

Code:

#! /usr/bin/python

droite =[1,3,8,21,55,144,150,377,987,2584,6765,17711,46368,  121393,317811,832040,2178309,5702887,14930352,3908  8169,102334155]
gauche = [2,5,13,34,89,233,610,1597,4181,10946,28657,75025,1  96418,514229,1346269,3524578,9227465,24157817,6324  5986,165580141]
#droite=[100,30,30,29,20]
#gauche=[7,9,70,70]

sd=[0,] #somme droite
sg=[0,] #somme gauche

for p in droite:
    taille=len(sd)
    sd=sd[:]*2
    for index in range(taille,2*taille):
        sd[index]=sd[index]+p

for p in gauche:
    taille=len(sg)
    sg=sg[:]*2
    for index in range(taille,2*taille):
        sg[index]=sg[index]+p

indicedroite=0
indicegauche=0
sd.sort()
sg.sort()

while (indicedroite<len(sd))and(indicegauche<len(sg)):
    if sd[indicedroite]==sg[indicegauche]:
        print sd[indicedroite]
        indicedroite=indicedroite+1
    else :
        if sd[indicedroite]<sg[indicegauche]:
            indicedroite=indicedroite+1
        else:
            indicegauche=indicegauche+1

C'est juste pour montrer la simplicité des manipulations de listes sous python.
Pour chaque poids, on le met ou on le met pas. Et obtient la liste complète des poids atteignables sur chaque plateau.

Posted by: nuage

Salut,

Citation:

Posté par Patastronch

Euh faut lire les cocos ... Darkpage a pondu la solution depuis longtemps et sans programme (qui était la contrainte de l'énnoncé au passage)

je sais sans doute pas lire, mais j'ai pas vu.

Posted by: barbouille94

Citation:

Posté par Flodelarab

Pardon pour l'auteur du post mais je crois que l'obstacle principal de cette énigme est la flemme et non la difficulté.

Pardon de quoi ? Je revendique le fait d'être un informaticien flemmard ...

J'ai moi même trouvé le poids par programme (et non en utilisant un crayon, un papier et de l'huile de coude ...)

Citation:

Posté par nuage

Normal, c'est pas des maths.
Ce que l'on peut espérer (en math) c'est une preuve que le programme de Flodelarab est juste.

C'est un peu ce que j'espérais en postant ici sous forme de "jeu" ... Même si le post original ne l'indique pas (mais je le dis un peu plus loin dans le fil ...)

Citation:

Posté par nuage

J'espère que l'auteur de cette énigme va nous donner un raisonnement simple conduisant au résultat.

Bah ... ben non, je l'ai pô le raisonnement ...

Citation:

Posté par nuage

Sinon cette énigme serait plus à sa place dans le forum informatique.

Déjà fait ... J'ai des algos intéressants, y compris la découverte d'un langage : le haskell.
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

) plus rapide que ce que j'ai actuellement ...

Le poids est bien 165580282.

Posted by: Patastronch

Citation:

Posté par Flodelarab

J'ai beau lire et relire les posts de Darkpage, je ne vois nullepart le nombre 165580282
(en fait j'ai fait rechercher par firefox

informaticien = flemmard

)

Citation:

Posté par nuage

Salut,

je sais sans doute pas lire, mais j'ai pas vu.

Citation:

Posté par Dark Page

La somme de tout les elements du premier plateaux =
165580190
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
soit la plus gros poids est la somme de tout les element de la première balance, on ne peux pas faire plus, et la somme du plus gros du second avec 2, 13, 34.

voila

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.

Posted by: Patastronch

Citation:

Posté par barbouille94

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

) 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 !

Posted by: Flodelarab

Citation:

Posté par 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

Posted by: Patastronch

Citation:

Posté par Flodelarab

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.

Posted by: scelerat

Citation:

Posté par Dark Page

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 $d_i$ (qu'on omet) et un de $g_j$ (qu'on prend en sus du plus grand) tels que $150 + 1 = \sum g_j + \sum d_i$ .
La plus grande somme inferieure a 151 qu'on puisse faire avec des $g_j$ est 143, ca marche avec le 8, pas la peine de chercher plus loin.

Posted by: 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

Posted by: scelerat

Citation:

Posté par 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é

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...