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