Enigme Partage du trésor 1/2 @ Prise2Tete

nodgim · #1

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.

scarta · #2

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"

nodgim · #3

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

caduk · #4

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

scarta · #5

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

nodgim · #6

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

scarta · #7

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

Sydre · #8

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

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

nodgim · #9

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

nodgim · #10

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

Merci d'avance.

scarta · #11

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

Migou · #12

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.

scarta · #13

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

Sydre · #14

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

nodgim · #15

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

nodgim · #16

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

scarta · #17

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

Sydre · #18

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

godisdead · #19

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

nodgim · #20

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

Milou_le_viking · #21

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.

scarta · #22

Ca y est j'ai pu le coder
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)

nodgim · #23

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

scarta · #24

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

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

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

scarta · #25

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

Partage du trésro

#0 Pub

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

Partage du tréso

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

Partage du résor

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

partage du teésor

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

partage du ttésor

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

Partage du tréosr

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

partage du tréspr

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

partagr du trésor

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

aPrtage du trésor

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

Parrtage du trésor

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

partagz du trésor

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

Partge du trésor

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

partahe du trésor

Code:

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

partafe du trésor

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

partahe du trésor

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

Partge du trésor

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

partage du tréqor

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

partage fu trésor

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

Partage ud trésor

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

partage du tréspr

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

partafe du trésor

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

Partage d utrésor

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

Partage d trésor

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

Prtage du trésor

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

Partag edu trésor

Réponse rapide

Sujets similaires

Pied de page des forums