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

[barbouille94]

Bonjour, je vous propose cette petite énigme :

But :
- équilibrer une balance à plateaux (Simple ? :zen: Pas sûr :triste: , 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
:doh:

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)
:id:

Poids à utiliser :
- pour le plateau de droite :

Code: Tout sélectionner

1
3
8
21
55
144
150
377
987
2584
6765
17711
46368
121393
317811
832040
2178309
5702887
14930352
39088169
102334155


- pour le plateau de gauche :

Code: Tout sélectionner

2
5
13
34
89
233
610
1597
4181
10946
28657
75025
196418
514229
1346269
3524578
9227465
24157817
63245986
165580141


:mur:


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

A vos bouliers ...

[Flodelarab]

En tout cas, il n'y a que équilibres maximums à tester. Trop facile.

[Patastronch]

En tout cas, il n'y a que équilibres maximums à tester. Trop facile.

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

[barbouille94]

Equilibre maximum 'potentiel' j'aurais dit !

Il y a bien une solution. C'est :scotch: ... Je ne la donnerais que plus tard :zen: Je dirais juste que ça dépasse la centaine de tonnes ...

Suffit de commencer par le plus grand equilibre possible pardi !

Par contre, je ne l'ai trouvée que de façon informatique :hum: 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 ?

[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

[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 :)

[Patastronch]

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

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

[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

[Patastronch]

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 !

[barbouille94]

...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 :euh: .
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 :ptdr: ).

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

[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 ?

[Imod]

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 :hum:

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 :zen:

Imod

[nuage]

Salut,

L'exemple type de ce que je n'aime pas en maths :hum:
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.

[Patastronch]

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)

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

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 )

[Flodelarab]

Et coco=communiste donc je partage mon code:

Code: Tout sélectionner

#! /usr/bin/python

droite =[1,3,8,21,55,144,150,377,987,2584,6765,17711,46368,121393,317811,832040,2178309,5702887,14930352,39088169,102334155]
gauche = [2,5,13,34,89,233,610,1597,4181,10946,28657,75025,196418,514229,1346269,3524578,9227465,24157817,63245986,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.

[nuage]

Salut,

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.

[barbouille94]

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

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

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

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

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 :lol2: ) plus rapide que ce que j'ai actuellement ...

Le poids est bien 165580282.

[Patastronch]

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 )

Salut,

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

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.