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
[+]

 #26 - 07-07-2020 22:05:48

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

Partage du tréor

Bon, fausse piste - testé avec n=5, le passage d'une solution "à 10" vers une solution "à 9" est possible pour certaines solutions de départ uniquement (et c'est assez long aussi accessoirement) du coup ça ne m'apportera pas grand chose sad

#0 Pub

 #27 - 08-07-2020 08:27:55

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

partage dy trésor

Tant pis. Merci pour le 9 en 5 tas. Je me doutais bien qu'il fallait faire des découpes distinctes, c'est un peu ce qu'il se passe avec le 10 tas.

 #28 - 08-07-2020 22:10:13

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

Patage du trésor

Bon, je suis un gros nul, ça ne marche que jusqu'à 4, mon affaire.
De fait, à partir de 5, ce n'est plus possible de le faire en 2(n-1).
Pour rappel, s est la somme des valeurs des pièces.
Un k tas est un tas de somme s/k

En effet, si tout les n tas et n-1 tas sont de taille 1 ou 2, alors toutes les pièces sont un multiple du pgcd de s/n et s/n-1. A partir de n = 5, ce pgcd est forcément supérieur à 1, et certains valeurs de tas sont forcément premières entre elles. Il faut donc avoir au moins un tas de taille 3. Tout les n-1 tas sont de taille 2, donc il existe un n-tas de taille au moins 3, et ce tas comporte au moins deux pièces non multiples du pgcd.
On appellera une pièce non multiple du pgcd une pièce singuulière.
Un n tas ou un n-1 tas contenant une pièce singulière contient forcément une autre pièce singulière. Suivons donc ce processus :
Prenons un n tas de taille 3, qui contient donc au moins deux pièces singulières. Choisissant-on une, et considérons son n-1 tas associé. Il est de taille 2, l'autre pièce est forcément singulière. Si cette nouvelle pièce est la même que celle de notre n tas initial de taille 3, alors on a une boucle. Sinon, on considère le n tas associé. Ce n tas contient forcément une autre pièce singulière, on considère donc le n-1 tas associé, et ainsi de suite, jusqu'à obtenir une boucle (c'est forcé puisque le nombre de pièces est fini. Cette boucle contient le même nombre de n tas et de n-1 tas. Comme tout les n-1 tas de la boucle contiennent uniquement deux pièces, leur union est inclue dans l'union des n-1 tas. Leur somme doit donc être inférieure à celle des n tas de la boucle, ce qui n'est évidemment pas le cas. On a donc une absurdité. La limite de 2(n-1) n'est donc plus atteignable.

Une longue preuve pour augmenter de seulement 1 la borne inférieure  lol
En cherchant un peu, on trouve donc comme solutions optimales :
5 : 1 2 3 4 6 9 11 12 12
6 : 1 2 2 2 3 5 6 9 10 10 10

Je suis à peu près  persuadé que l'on ne peut pas faire 7 avec 13 pièces, je cherche une preuve et je continue.

Je n'ai pas eu beaucoup de temps pour regarder ce problème. Je pensais que c'était un problème très dur à aborder du fait de ses propriétés arithmétiques très compliquées, et où on ne peut trouver des solutions qu'en tâtonnant,  mais je vois qu'il y a des choses intéressantes pour l'aborder à la main. Même si je pense qu'il est dur de trouver une formule exacte pour l'optimum, il doit y avoir moyen de trouver des choses intéressantes pour trouver des bornes.

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

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

Partag edu trésor

En 31 pièces :

6 de valeur 252
1 de 168
2 de 108
1 de 84
2 de 63
2 de 54
1 de 36
6 de 28
1 de 21
1 de 18
1 de 14
2 de 9
1 de 8
2 de 7
1 de 6
1 de 3

En 10 tas :

6*28+21+2*7+14+8+6+18+3
2*63+2*54+2*9
2*108+36
168+84
6 tas de 252

En 9 tas :

2*63+2*54+2*9+28
2*108+36+28
168+84+28
3 tas de 252+28
252+18+7+3
252+21+7
252+14+8+6

En 8 tas :

7+2*28+2*108+36
14+28+18+3+168+84
252+28+21+8+6
252+2*28+7
252+63
252+63
252+54+9
252+54+9

En 7 tas :

3+2*7+14+21+2*28+168+84
252+6+3*28+18
252+9+63+8+28
252+2*54
252+36+63+9
252+108
252+108

En 6 tas :

252+5*28+3+7+2*9
252+63+54+36+8+7
252+108+14+28+18
252+108+54+6
252+84+63+21
252+168

Les partitions en 5 à 2 tas se déduisent des partitions en 10, 9 et 8 tas.

 #30 - 10-07-2020 08:52:05

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,890E+3

partage di trésor

En 22 pièces big_smile
220 213 192 185 175 164 151 147 129 128 123 105 101 95 88 77 67 39 35 32 29 25

220+175+25
213+105+67+35
192+151+77
185+147+88
164+129+95+32
128+123+101+39+29

220+105+35
213+147
192+129+39
185+175
164+101+95
151+123+32+29+25
128+88+77+67

220+95
213+77+25
192+123
185+101+29
175+105+35
164+151
147+129+39
128+88+67+32

220+35+25
213+67
192+88
185+95
175+105
164+77+39
151+129
147+101+32
128+123+29

220+32
213+39
192+35+25
185+67
175+77
164+88
151+101
147+105
129+123
128+95+29

 #31 - 10-07-2020 09:15:19

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

Partage du trésr

Bon, continuons :

Avec 2(n-1) + 1 pièces, il y a exactement un n-1 tas de taille 3, les autres étant de taille 2.

Le cycle décrit à la démo précédente existe toujours, mais cette fois, les n-1 tas du cycle ne sont pas forcément inclus dans les n tas du cycle. En effet, il suffit que le n-1 tas de taille 3 appartienne à la chaîne, et que l'une des 3 pièces ne fasse pas partie de l'un des n tas du cycle. On peut ainsi trouver des solutions facilement pour 5 et 6 en se basant sur le graphe ainsi dessiné. Cependant, à partir de 7, ce n'est plus possible.

Pour voir ça, on peut remarquer que l'on ne peut avoir un deuxième cycle. En effet, ce deuxième cycle doit lui aussi passer par le n-1 tas de taille 3. Le n-1 tas de taille 3 est forcément à un point de divergence des deux cycles car sinon, on pourrait extraire un troisième cycle ne passant pas par le n-1 tas de taille 3. Les 3 pièces du n-1 tas de taille 3 appartiennent donc à 3 n tas différents, qui appartiennent tous à l'un des cycles. Pour boucler le deuxième cycle, il faut forcément rejoindre à un moment donné un n tas du premier cycle. (on ne peut pas rejoindre sur un n-1 tas, car tout les autres n-1 tas sont de taille 2). On voit alors qu'au global sur l'union des deux cycles, il y a autant de n tas que de n-1 tas. De plus, les n-1 tas sont inclus dans les n tas (on a vu que les 3 pièces du n-1 tas de taille 3 étaient toutes inclues dans les cycles).

Il n'y a donc qu'un cycle. Dans le cas n=7, Ca ne donne pas beaucoup de possibilités de graphes, et on peut parcourir ces possibilités relativement rapidement à la main, mais je n'ai pas trouvé d'argument tranché pour plier la question en 2 lignes (comme dans mes démos smile).
En revanche, à partir de 8, on sait que l'on doit trouver au moins n-2 pièces singulières, car chaque n-2 tas doit contenir au moins une pièce singulière. Le cycle doit donc contenir au moins (n-2)/2 n-1 tas et le même nombre de n-1 tas.
Or ( s/(n-1) )x(n-2)/2 > ( s/(n-2) +1)x(n-2)/2 quand n >= 8
Ce ne sera donc pas possible d'avoir des cycles aussi grand.

Je galère à trouver pour le 7. Il faut peut-être au moins 15 pièces. Le nombre de cas à traiter pour 14 est assez grand, mais j'ai l'impression que des propriétés arithmétiques empêchent qu'il y ait une solution, je creuse...

 #32 - 10-07-2020 09:23:22

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

partage du trédor

J'ai fini par trouver l'entrée OEIS. Bon, pas de solutions pour n = 10 apparemment... tongue

https://oeis.org/A265286

Apparemment, ils ont quand même trouvé une solution pour 10 en 22, mais n'ont pas prouvé l'optimalité...

 #33 - 10-07-2020 15:51:12

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,890E+3

Partaage du trésor

Sur un site russe, ils sont convaincus de pouvoir atteindre 21.

 #34 - 10-07-2020 16:14:28

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

Partagge du trésor

Comment as tu obtenu ton 22? sur leur site, par un programme ou a la main?

 #35 - 10-07-2020 16:24:29

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,890E+3

Paartage du trésor

Un des exemples de leur site, qui aurait l'idée de trouver ça à la main ?
Le 21 semble rester un graal.

 #36 - 10-07-2020 17:03:50

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

partage fu trésor

Merci Gwen.

Perso, vu que mon 31 a été obtenu après peu d'essais, je me doutais bien qu'on pouvait faire beaucoup mieux....

Donc, le nombre de pièces tendrait plutôt vers 2n + epsilon.

 #37 - 10-07-2020 17:16:44

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

artage du trésor

Je pense qu'en utilisant les résultats que j'ai élaboré, on peut construire l'ensemble des hypergraphes possibles pour les n tas et les n-1 tas. Pour de petites valeurs de n et des nombres de pièces pas trop grand au dessus de 2(n-1), la combinatoire semble acceptable. Ensuite, chaque graphe doit être assez rapide à traiter par backtracking. Par contre, ça va prendre un moment à coder...
Je cherche encore si il y a quelques idées pour démontrer l'impossibilité de certaines configurations, ou si on peut réduire plus la taille des calculs...

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Partage d'un gâteau par titoufred
29-04-2013 Enigmes Mathématiques
P2T
06-04-2011 Enigmes Mathématiques
P2T
Point de trésor ? par SaintPierre
28-02-2011 Enigmes Mathématiques
P2T
Partage de pirates par gonzague
20-07-2009 Enigmes Mathématiques
P2T
Partage du cercle en trois par clement.boulonne
31-12-2010 Enigmes Mathématiques
03-12-2007 Enigmes Mathématiques
P2T
14 = 16 par fred101274
22-12-2010 Enigmes Mathématiques
P2T
La couleur du chapeau par PRINCELEROI
03-08-2013 Enigmes Mathématiques
31-10-2010 Enigmes Mathématiques

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