Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 03-07-2020 12:00:36

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Partgae du trésor

Bonjour @ tous

Vous avez un petit trésor constitué de pièces de différentes valeurs. Il se trouve que vous pouvez le partager en 2 à 10 tas égaux. Combien de pièces avez vous au minimum et quelles sont les valeurs des pièces ?

Les pièces doivent avoir une valeur entière, elles peuvent bien entendu être présentes en plusieurs exemplaires.

Pour la réponse, il faudra donner les 9 partitions.

Bonne épargne !

PS: perso, j'ignore si j'ai bien le minimum.

  • |
  • Répondre

#0 Pub

 #2 - 03-07-2020 16:12:43

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Parttage du trésor

Hello
"Vous avez un petit trésor constitué de pièces de différentes valeurs"
==> le sens littéral est que toutes les pièces n'ont pas la même valeur, donc qu'au moins une pièce possède une valeur différente.

J'imagine toutefois que c'est plutôt "Vous avez un petit trésor constitué de pièces tel que deux pièces ont toujours deux valeurs différentes"

 #3 - 03-07-2020 17:05:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Partage du térsor

@ Scarta : Lis le reste, l'ambiguïté y est levée.

 #4 - 03-07-2020 17:40:45

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Patage du trésor

Soit s la somme des valeurs des pièces
On voit facilement que pour n tas, on ne peut pas faire mieux que 2(n-1). (Si il y en avait moins, en n-1 tas, l'un des tas aurait une pièce. Sa valeur serait s/(n-1). En divisant en n tas, on ne pourrait la placer dans aucun tas.

Vite fait, j'ai trouvé :

1 : 1
2 : 1 1
3 : 1 1 2 2
4 : 1 1 2 2 3 3
5 : 3 3 5 5 10 10 12 12
6 : 2 2 5 5 6 6 7 7 10 10

Ensuite, ça se corse, je revient...

 #5 - 03-07-2020 19:25:37

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

pattage du trésor

Exact, j'ai lu trop vite.
Il faut un minimum de 2520€ pour pouvoir prendre en compte tous les diviseurs possibles
On peut donc avoir 6 pièces de 252€ pour commencer, et le reste en pièces de 1€ - ce qui est recevable mais pas optimal, loin de là - 7 c'est trop, pour 6 personnes une d'entre elles devrait avoir deux pièces de 252 et ça dépasse le montant total de 420€/personne

On peut ensuite considérer des pièces de 168€ - 4 max, si on veut ne pas être bloqué pour 4 personnes, sans présumer que ça fonctionne encore derrière, etc...

J'arrive à un résultat de 36 pièces pour l'instant
252 x 6
168 x 2
56 x 1
52 x 3
42 x 1
32 x 2
28 x 10
11 x 1
7 x 6
6 x 3
3 x 1

 #6 - 03-07-2020 22:10:10

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

oartage du trésor

@ Sydre : aïe ! Je crains que tu ne te sois perdu dans les brumes, ou que tu n'as pas compris le problème. Refais le avec moins de tas peut être, pour voir. Il n'y a pas de complication théorique ici.

@ Scarta : De loin le meilleur résultat pour l'instant. Il faudra tout de même donner la distribution exacte, mais je crois que tu es en cours de progression....

@ Caduk : continue !

 #7 - 05-07-2020 00:27:56

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Partage du ttrésor

J’ai trouvé 32

252 x6
60 x6
45 x6
35 x6
28 x6
cette distribution suffit bien évidemment pour 6, mais aussi pour 7 (en prenant tous les 60 pour le 7eme) par 8 (les 60 et les 45 distribués de part et d’autre) et par 9 (60,45 et 35 distribués en 3)
On peut montrer (modulo 10) que ça ne permet pas de faire 10x252
Cependant, on peut avec deux pièces de plus y arriver.

252 6 fois
28x4 + 35x4 = 252
35x2 + 60x3 + 2 = 252
60 + 45x3 + 28 + 29 = 252 2 fois
(On divise juste 60 en 2+29+29, ce qui ne change pas les autres distributions)

Total:
252x6
60x5
45x6
35x6
28x6
29x2
2x1

Toujours modulo 10, on peut montrer que si on part des 30 premières pièces, on ne fera pas mieux que 32 (mais ça ne veut pas dire que les 30 premières soient correctes)

Edit : j’oublie le plus important. Les autres divisions ne sont pas importantes : si je peux diviser en 2N parts, je peux aussi diviser en N parts. Du coup les seuls cas à considérer sont de 6 à 10

 #8 - 05-07-2020 03:12:52

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

partage di trésor

Manifestement j'avais lu l'énoncé un peu vite la première fois lol

Nouvelle tentative, donc.

Cette fois je trouve un minimum de [latex]550[/latex] pièces avec la distribution de valeur suivante :

6 x 6912, 15 x 1728, 9 x 2160, 6 x 10368, 6 x 3456, 18 x 432, 12 x 1296, 6 x 648, 9 x 216, 6 x 1620, 6 x 23328, 6 x 3888, 12 x 7776, 12 x 2592, 10 x 144, 2 x 72, 8 x 6144, 8 x 768, 7 x 1344, 14 x 384, 10 x 192, 8 x 38400, 8 x 4800, 8 x 7680, 8 x 960, 8 x 24000, 12 x 6000, 8 x 9600, 14 x 1200, 7 x 1680, 6 x 480, 2 x 240, 8 x 3072, 16 x 48, 7 x 10290, 6 x 2940, 9 x 1470, 6 x 420, 2 x 210, 7 x 16464, 6 x 4704, 9 x 2352, 6 x 672, 2 x 336, 8 x 288, 5 x 120, 18 x 96, 10 x 24, 8 x 60000, 12 x 15000, 8 x 36000, 12 x 9000, 7 x 29400, 6 x 8400, 9 x 4200, 2 x 600, 4 x 3750, 4 x 2250, 4 x 1500, 8 x 2400, 8 x 300, 6 x 3240, 6 x 1080, 6 x 540, 6 x 46656, 6 x 15552, 6 x 20736, 6 x 5184, 6 x 864, 8 x 12

 #9 - 05-07-2020 08:32:22

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

partage du ttésor

@ Sydre : c'est encore beaucoup.

Pour toi, quel est la somme minimale des valeurs de toutes les pièces ? Car cette somme minimale est à mon avis le premier calcul à faire.

 #10 - 05-07-2020 08:35:22

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

partage du trésoe

@ Scarta: peux tu s'il te plait donner les distributions de 10 à 6 tas ?

Merci d'avance.

 #11 - 05-07-2020 12:09:23

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

paetage du trésor

C’est pourtant écrit, quoi que pas très clair. Mais bon dès que j’ai un vrai clavier je détaille.

Sinon, j’ai appliqué la même méthode à d’autres valeurs N pour des problèmes « de 2 à N » et il me semble que la différence entre deux N consécutifs est phi(N). Si c’est vrai ça va être coton à prouver

 #12 - 05-07-2020 12:47:13

Migou
Expert de Prise2Tete
Enigmes résolues : 17
Messages : 528
Lieu: Ville 2/N près 2*i

Partage du résor

Bonjour bonjour,

De mon côté, je trouve une partition en 36 pièces.

Ce qui est sûr, c'est que le montant du trésor est d'au moins 2520 (ppcm entre 2, 3, ... 10)

Pour un montant de 2520 avec 36 pièces :

6 pièces de 252

9 pièces de 28
7 pièces de 35
5 pièces de 45
2 pièces de 32

1 pièces de : 60 53 50 25 17 10 7

--------------------

Pour 10 : 10 tas de 252 = 2520

6 tas sous la forme 252
1 tas sous la forme 9x28
1 tas sous la forme 5*45 + 17 + 10
1 tas sous la forme 7*35 + 7
1 tas sous la forme 2x32 + 60 + 53 + 50 + 25
--------------------

Pour 9 : 9 tas de 280 = 2520

On répartit les 9 pièces de 28 sur chacun des neuf tas restants, qui passent tous de 252 à 280

6 tas sous la forme 252 + 28
1 tas sous la forme 5*45 + 17 + 10 + 28
1 tas sous la forme 7*35 + 7 + 28
1 tas sous la forme 2x32 + 60 + 53 + 50 + 25 + 28


--------------------
Pour 8 : 8x315

On répartit le tas  de 7*35 + (7+28) par tranches de 35 sur chacun des tas restants.

6 tas sous la forme 252 + 28 + 35
1 tas sous la forme 5*45 + 17 + 10 + 28 + 35
1 tas sous la forme 2x32 + 60 + 53 + 50 + 25 + 28 + (7+28)

--------------------
Pour 7 : 7x360

on répartit le tas 5*45 + (17+28) + (10+35) par tranches de 45 sur les 7 tas restants

5 tas sous la forme 252 + 28 + 35 + 45
et un sous la forme 252 + 28 + 35 + (17+28)
1 tas sous la forme 2x32 + 60 + 53 + 50 + 25 + 28 + (7+28) + (10+35)

--------------------
Pour 6 : 6x420

Répartir le tas de 2x32 + 60 + 53 + 50 + 25 + 28 + (7+28) + (10+35) par tranches de 60, soit : 60, 53+7, 50+10, 35+25, 32+28, 32+28

En dessous de 6, toutes les répartitions découlent de celles vues ci-dessus, en regroupant des tas.

 #13 - 05-07-2020 13:19:49

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Pratage du trésor

Code:

252   252   252   252   252   252            
28    28    28    28    28    28            
35    35    35    35    35    35            
45    45    45    45    45    45            
29    60    60    60    60    60            
29                                
2                                
                                
                                
60    252   252   252   252   252   252        
60    28    28    28    28    28    28        
60    35    35    35    35    35    35        
60    45    45    45    45    45    45        
60                                
29                                
29                                
2                                
                                
                                
45    45    252   252   252   252   252   252    
45    45    28    28    28    28    28    28    
45    45    35    35    35    35    35    35    
60    60                            
60    60                            
29    60                            
29                                
2                                
                                
                                
35    35    35    252   252   252   252   252   252
35    35    35    28    28    28    28    28    28
45    45    45                        
45    45    45                        
60    60    60                        
29    60    60                        
29                                
2                                
                                
                                
28    35    45    45    252    252    252    252    252
28    35    45    45                    
28    60    45    45                    
28    60    60    60                    
35    60    28    28                    
35    2     29    29                    
35                                
35

 #14 - 05-07-2020 16:51:17

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

partage du trédor

Effectivement j'ai aussi oublié de corriger la valeur minimale du trésor.

En prenant la valeur correcte, [latex]2^3\cdot 3^2\cdot 5\cdot 7=2520[/latex], je trouve un minimum de [latex]498[/latex] pièces avec la distribution de valeur suivante :

22 x 12, 27 x 6, 49 x 3, 21 x 8, 103 x 1, 2 x 10, 52 x 4, 130 x 2, 22 x 5, 24 x 7, 1 x 30, 1 x 14, 4 x 9, 7 x 26, 10 x 11, 9 x 31, 9 x 19, 1 x 20, 4 x 17

Si c'est encore faux c'est qu'il doit toujours y avoir quelque chose de bancal dans ma méthode, auquel cas je veux bien un ordre de grandeur de ton minimum smile

 #15 - 05-07-2020 16:56:03

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Prtage du trésor

@ Scarta: je sais, c'était clair, mais il me fallait la répartition pour mieux vérifier. Donc c'est OK, bravo @ toi !

Perso, j'ai un chouia mieux.....

@ Migou : C'est OK, il y a un peu mieux.

 #16 - 05-07-2020 16:57:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Partage du tréor

@ Sydre : messages croisés. Tu peux diviser ton résultat par plus de 10, pour te donner une idée.

 #17 - 05-07-2020 17:50:27

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Partage du tréosr

Mince, un chouïa mieux veut dire que mon histoire de l’indicatrice d’Euler ne tient plus sadsadsad

 #18 - 05-07-2020 20:27:05

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

Patage du trésor

Bon, j'avais oublié certains cas.

Je trouve finalement un minimum de [latex]86[/latex] pièces avec la distribution de valeur suivante :

14 x 126, 14 x 14, 7 x 1, 7 x 3, 1 x 4, 2 x 18, 6 x 36, 4 x 8, 4 x 6, 15 x 2, 1 x 30, 5 x 26, 6 x 5

C'est toujours loin de l'ordre de grandeur annoncé : je crois que je vais m'arrêter là, ce problème ne me réussit pas lol

 #19 - 06-07-2020 13:33:49

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 747

partage du teésor

La valeur du tas est un multiple de 2520 (peu probable qu'il faille le multipler pour optimiser)
Premier jet :
252    28    35    45    60
252    28    35    45    60
252    28    35    45    60
252    28    35    45    60
252    28    35    45    12
252    28    35    27   
    28    35    18   
    28    7    10   

35 pièces !
les 9 tas :
252 / 28 => 6 fois
60/60/60/60/12/28
35/35/35/35/35/35/28/7
45/45/45/45/45/27/18/10

 #20 - 06-07-2020 17:33:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

partage du tréspr

@ Godisdead : je te fais confiance sur ce résultat, bien que tu ne donnes pas les partitions, vu la valeur des pièces. On peut faire un peu mieux.

 #21 - 07-07-2020 11:27:11

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 446

Partage d trésor

Hello,


En guise de début, il faut que la somme des pièces soit divisible par 2, 3, ... et 10.
Donc la somme minimale des pièces est égale au produit des plus grandes puissances de nombre premier de 2 à 10.
S = 5*7*8*9 = 2520

Ensuite, je partirai sur une première pièce à 252, mais il faut encore que je réfléchisse.

Et d'autre part, si je sais répartir mes pièces en 10, 9, 8, 7 et 6, alors je sais aussi les répartir rn 5, 4, 3 et 2.

 #22 - 07-07-2020 15:14:13

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

partage du trédor

Ca y est j'ai pu le coder smile
Et ça tourne pour des plus petites valeurs, ce qui m'a permis pour n=5 de voir qu'en effet, là ou je trouvais 10 on peut faire 9 en pensant un peu différemment

Y'a plus qu'à essayer d'appliquer ça à n=10 (je pense pas arriver au bout du code pour n=10 d'ici 45h)

 #23 - 07-07-2020 19:44:16

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Paratge du trésor

@ Scarta : le 9 pour 5 m'intéresse. Peux-tu le donner ?

Sinon, bravo pour le programme, je m'attends à une partition bien moindre que le manuel.

 #24 - 07-07-2020 21:19:47

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

parrage du trésor

1, 2, 3, 3, 7, 8, 12, 12, 12

Partitions
5: 12, 12, 12, 8+1+3, 7+3+2
4: 12+3, 12+3, 12+2+1, 8+7
3: 12+8, 12+7+1, 12+3+3+2
2: 12+12+3+3, 12+8+7+2+1

Il faudrait environ 24 heures pour sortir n=7, et c'est pire qu'exponentiel : le nombre de pièces implique à lui seul une croissance exponentielle, et en plus le montant total (PPCM({i=2..n}) augment aussi !
Après, si tu veux payer l'instance EC2 pour l'année à venir, je te file le code smile

En gros, entre 5 et 6 c'est exponentiel, mais entre 6 et 7 c'est la fin du monde sad

Pour 6, tu tombes à 11 pièces : 1, 1, 2, 2, 4, 5, 7, 8, 10, 10, 10

6: 10, 10, 10, 8+2, 7+2+1, 5+4+1
5: 10+2, 10+2, 10+1+1, 8+5, 5+7
4: 10+5, 10+4+1, 10+2+2+1, 8+7
3: 10+10, 10+8+2, 7+5+4+2+1+1
2: 10+10+10, 8+7+5+4+2+2+1+1

 #25 - 07-07-2020 21:26:21

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

partage du ttésor

Par contre, je pense que ça serait un peu plus rapide : je vais coder un autre programme, qui va essayer de faire une optimisation sur une solution presque optimale.

Par exemple, en partant de la mienne, je vais essayer de grouper 3 éléments et les découper en 2, pour voir si la solution est valable.

L'intéret est double : d'abord j'essaye d'égaliser smile et ensuite vu que je peux sortir quasi-mécaniquement ma solution approchée (qui n'est pas si mal), si je peux aussi l'optimiser mécaniquement derrière c'est magique smile

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete