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 - 28-04-2015 22:15:51

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

les chevalières de la tabke ronde (étape 3)

Nos n nobliaux sont décadents ; il se réunissent pour échanger leurs bagues, mais ce n'est qu'un prétexte à de continues libations. Qu'importe, de toute façon ? Ils sont désormais convaincus que l'ordre de leurs échanges n'a aucune espèce d'importance.

Afin de se consacrer du mieux qu'ils peuvent à l'étude de la philosophie hédoniste, ils désirent prolonger la soirée le plus qu'il est possible. Quelle stratégie leur conseilleriez-vous au moment de répartir les (n-1) chevalières entre eux, avant de commencer les échanges ?

(De manière moins pédante : comment placer les (n-1) bagues pour que la partie soit la plus longue possible ?)

  • |
  • Répondre

#0 Pub

 #2 - 29-04-2015 08:16:45

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

Les chevalières de la table ronde (étpe 3)

Il faudra justifier, bien sûr, mais c'est toutes les bagues au même endroit.
On peut d'ailleurs calculer le nb de coups pour 2n ou 2n+1 bagues au même endroit:
1²+2²+3²+...n²=n(n+1)(2n+1)/6.

 #3 - 29-04-2015 08:58:35

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Les chevalières de la table ronde (éatpe 3)

@nodgim : et non, nyark nyark smile Je peux (dans certains cas) fabriquer des parties strictement plus longues que ta proposition.

 #4 - 29-04-2015 09:50:55

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Les chevalièes de la table ronde (étape 3)

Bonjour,
Voici ce que j'obtiens par simulation

Code:

Nb de         Répartition              Répartition          Nb de      Nombre de
nobliaux       initiale                  finale             coups        coups
                                                            total     individuels
1        (0)                      (0)                         0   (0)
2        (1, 0)                   (1, 0)                      0   (0, 0)
3        (2, 0, 0)                (0, 1, 1)                   1   (1, 0, 0)
4        (2, 1, 0, 0)             (1, 0, 1, 1)                2   (1, 1, 0, 0)
5        (4, 0, 0, 0, 0)          (0, 1, 1, 1, 1)             5   (3, 1, 0, 0, 1)
6        (3, 2, 0, 0, 0, 0)       (1, 0, 1, 1, 1, 1)          8   (3, 3, 1, 0, 0, 1)
7        (6, 0, 0, 0, 0, 0, 0)    (0, 1, 1, 1, 1, 1, 1)      14   (6, 3, 1, 0, 0, 1, 3)
8        (4, 3, 0, 0, 0, 0, 0, 0) (1, 0, 1, 1, 1, 1, 1, 1)   20   (6, 6, 3, 1, 0, 0, 1, 3)

 #5 - 29-04-2015 10:32:13

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

les chevalières de la table tonde (étape 3)

@enigmatus : cette simulation m'a l'air tout à fait juste. Il reste à généraliser : expliquer quelle(s) est la position initiale la plus favorable (pas trop dur), trouver une formule pour le nombre de coups maximal en fonction de n (un peu plus dur), et démontrer rigoureusement qu'il s'agit bien du maximum (plus dur).

 #6 - 29-04-2015 18:16:14

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

Les chevalières de la table ronde (éétape 3)

Effectivement, on trouve au moins 1 cas où les bagues sur une seule case ont besoin de moins d'actions que si elles sont partagées sur 2 cases voisines:
Pour 2^n-1 sur 1 case: (2^(n-1)-1)(2^(n-1)(2^n-1)/6
Pour 2^n-1 réparti en (2^(n-1);2^(n-1)-1): (2^(n-1)-1)(2^(n-1)(2^(n-1)+1)/3

C'est plus fort pour le 2ème cas.

ça semble être une particularité pour les 2^n-1.

 #7 - 29-04-2015 22:47:37

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

les chevaluères de la table ronde (étape 3)

@nodgim : la particularité que tu as fort justement notée n'est pas restreinte aux seuls cas que tu cites. Il y a d'autres nombres pour lesquels elle est valable.

 #8 - 30-04-2015 03:45:49

dbab3000
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 111

les chevalières de la table ronfe (étape 3)

Je pense avoir trouver la position initial et le nombre d'échanges:
Supposons qu'il y n nobliaux et n chevalières on peut trouver des positions initiaux qui donne un cycle infini par exemple:
si n est pair on a :
(02020202020202...) tel que 02 se répète n/2 fois après que tous les nobliaux échangent leurs bagues ça donne (202020202020...)
si n est impair on a:
(10202020202...) tel que 02 se répète (n-1)/2 fois et qui donne (210202020202020...)
On remarque que ces positions donnent un cycle infini.
En suivant le même raisonnement:
Si n est impair alors n-1 est pair, la position initial est (002020202020202...) tel que 02 se répète (n-1)/2 fois.
Si n est pair alors n-1 est impair, la position initial est (0102020202020202...) tel que 02 se répète (n-2)/2 fois.
On sait que l'ordre des échanges n'est pas important donc je vais considérer qu'une étape est l'ensemble des échanges possibles depuis une répartition exemple: 10202020 les 3 échanges sont une seule étape qui donne 11020201et l'autre étape a 2 échanges.
On remarque dans le dernier exemple que le nombre d'échange diminue de 1 dans chaque étape, on a F(8)=3+2+1=6 tel que F(n) est le nombre des échanges et n le nombre de nobliaux,calculons F(n):
Si n est impair, la position initial est (002020202020202...) le nombre d'échange dans la première étape est égale au nombre de 2 qui est (n-1)/2, alors
F(n)=somme (de k=0 à k=(n-1)/2) (n-1)/2-k=(n²-1)/8
Si n est pair,la position initial est (0102020202020202...) le nombre de 2 est (n-2)/2,alors
F(n)=somme de (k=0 à k=(n-2)/2) (n-2)/2-k=(n²-2n)/8
Donc:
Si n est pair F(n)=(n²-2n)/8
Si n est impair F(n)=(n²-1)/8
Je vais essayer de prouver que c'est la valeur maximale.
Bonne nuit.

 #9 - 30-04-2015 09:03:00

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

Les chevalères de la table ronde (étape 3)

Oui, pour un nombre pair, c'est sur 1 seule case qu'il faut grouper les bagues. Pour un nombre impair 2n+1, il faut répartir sur 2 cases (n,n+1).

 #10 - 30-04-2015 14:07:18

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

les chevalières de la table rondz (étape 3)

@dbab3000 : vérifie si ton intuition est la bonne sur des petites valeurs de n.

@nodgim : je suis d'accord - reste à le prouver smile

 #11 - 30-04-2015 17:32:15

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

Les chevalières de la tale ronde (étape 3)

Entre 1 et 2 cases c'est facile à montrer. En revanche, la répartition optimale dans les 2 cases n'est pas facile-facile à montrer...

 #12 - 01-05-2015 03:34:44

dbab3000
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 111

Les chevaliières de la table ronde (étape 3)

1ère partie
J'ai commis une erreur je me suis trop basé sur mon intuition et je n'ai pas fait de test, je rectifie pour les 10 premières valeurs de n la répartition qui attribue plusieurs échanges:
n=1 (0) 0 échange f(1)=0
n=2 (01) 0 échange f(2)=0
n=3 (002) 1 échange f(3)=1
n=4 (0012) 2 échanges f(4)=2
n=5 (00004) 5 échanges f(5)=5
n=6 (000023) 8 échanges f(6)=8
n=7 (0000006) 14 échanges f(7)=14
n=8 (00000034) 20 échanges f(8)=20
n=9 (000000008) 30 échanges f(9)=30
n=10 (0000000045) 40 échanges f(10)=40
On remarque que:
Si n pair la bonne répartition est (000000000....(n-2)/2,n/2) 0 se répète n-2 fois.
Si n est impair la bonne répartition est (000000...(n-1)) 0 se répète n-1 fois.
2ème partie
On prend f(n) le nombre d'échanges total entre les nobliaux et n le nombre de nobliaux.
Si n est impair n=2k+1
Je vais juste expliquer la méthode, je ne vais pas faire le calcul car c'est un peu long.
On prend g(k) tel que f(2(k+1)+1)-f(2k+1)=g(k)
puis on prend h(k) tel que g(k+1)-g(k)=h(k)
et h(k+1)-h(k)=2
On trouve h(k) puis g(k) puis f(2k+1) suivant k et on sait que k=(n-1)/2
et on trouve f(n)=n(n²-1)/24
Si n est pair n=2k
On prend g(k) tel que f(2k+2)-f(2k)=g(k)
puis on prend h(k) tel que g(k+1)-g(k)=h(k)
et h(k+1)-h(k)=2
On trouve h(k) puis g(k) puis f(2k) suivant k et on sait que k=n/2 et on trouve f(n)=n(n²-4)/24
J'espère que je n'ai pas commis d'erreur cette fois ci, je vais essayer de montrer que c'est la valeur maximal.
Bonne nuit.

 #13 - 01-05-2015 09:24:00

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Les chevalires de la table ronde (étape 3)

J'ai commencé à regarder mais je n'ai rien de vraiment concluant pour l'instant . Je pencherais pour un maximum de coups quand les chevalières sont toutes dans la même main et alors pour n chevalières un nombre total de coups égal à la somme des carrés des entiers inférieurs ou égaux à N=E(n/2) . C'est à dire un maximum égal à N(N+1)(2N+1)/6 .

Tout ça est à confirmer .

Vasimolo

 #14 - 01-05-2015 13:00:45

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

les chevalières dr la table ronde (étape 3)

Un peu de vocabulaire:
-Action: un nobliau qui donne. On peut comptabliser les actions dans une case donnée par un nombre. On peut aussi comptabiliser toutes les actions dans toutes les cases par une suite ordonnée de nombres représentant chacun le nombres d'actions dans chaque case. L'ordre des nombres est celui des cases successives.
-case: position d'un chevalier, chevalier lui même.
-configuration (conf): représentation par une suite ordonnée de nombres qui donnent chacun le nombre de bagues de chaque case. L'ordre des nombres est celui des cases successives.
-scénario: ensembles des actions depuis la conf de départ à la conf finale.
-zone active:dans une conf de départ, on distingue les zones actives des autres zones. 1 zone active est une zone de cases successives sans case vide et avec au moins une case de plus d'une bague.
Règle 1 :
Si une zone active a plus de 2 cases, elle exigera moins d'actions que la même zone à 1 ou 2 cases avec le même nombre de bagues. En effet, par l'opération inverse de l'action (recevoir 1 bague de chaque voisin) on peut tjs réduire la zone d'action à 1 ou 2 cases.
Règle 2:
Pour déplacer une bague d'une case A à une case B distante de A de n cases, il faut n(n+1)/2 actions. 
Démonstration:
A111111111B
On actionne ttes les cases sauf B (n actions)
A111111110B: A a perdu 1 bague, elle est dans B.
On actionne ttes les cases sauf B et la case vide (n-1 cases):
A111111101B
On recommence et au final, on aura actionné n+(n-1)+....1=n(n+1)/2 cases.
Donc c'est à partir d'une config où les bagues sont groupées dans une seule ou deux cases qu'il faudra le plus d'actions. En effet, les cases vides les plus éloignées sont celles qui exigent le plus d'actions.
Méthode des actions (dans le msg précédent, on a prouvé que l'ordre des actions était indifférent): Activer une fois ttes les cases de la zone active puis observer.
Les bagues sur une seule case:
Exemple avec 8:
8----1 action-->161----3a---->10601--->1a---->11411. En réunissant les 2 dernières étapes: 161---4a--->11411.
11411---9a---->1112111----16a---->111101111
Dans le cas général, on voit que le nb d'actions pour étendre la zone de 2 cases est un carré, c'est la suite 1,1+3,1+3+5,....
Formule résultante avec 2n ou 2n+1 bagues: n(n+1)(2n+1)/6.
Les bagues sur 2 cases
Exemple avec 54
54--2a--->1431---(4+2)a--->113211---(6+4+2)a---->11121111---(8+6+4+2)a---->111110111
Formule résultante avec 2n bagues: (n-1)n(n+1)/3 et avec 2n+1 bagues: n(n+1)(n+2)/3.
La comparaison des formules montre que pour 2n bagues il y a plus d'actions si elles sont groupées sur une seule case, et pour 2n+1 bagues, plus d'actions si elles sont groupées sur 2 cases.
On vient de prouver qu'il fallait partir d'une config avec seulement 1 ou 2 cases occupées. On n'a pas prouvé que dans le cas de 2 cases occupées dans le cas 2n+1 bagues, la meilleure était la config (n,n+1).
Pour une config (n+b,n+1-b) il est assez évident qu'on distribuera plus vite vers la gauche que vers la droite. En effet, la case (n+1-b) ne peut donner à droite que tant qu'elle a des bagues, or elle en a moins que la case (n+b): Elle doit attendre d'être rechargée par sa voisine. Ceci se traduit  par une conf  finale différente et se vérifie dans les faits.
Exemple:
000 43 000---->111 10 111
000 52 000---->111 11 011   
000 61 000---->111 11 101
La différence est mesurable en termes d'actions pas la position du 0 depuis les cases donatrices. D'après la règle 2, il faut:
1 action de moins depuis 52 que 43.
2*3/2=3 actions de moins pour 61 que pour 43.
Dans le cas général, le nb d'actions pour une config (n+b,n+1-b) est donné par la formule n(n+1)(n+2)/3-b(b+1)/2.
Inversement, si on nous dit qu'on est parti d'une config depuis 2 cases données, en observant la position du zéro final, on en déduit b.

Reste à montrer qu'une conf à 1 seule zone active ZA1 est la plus gourmande en nb d'actions.

1) il y a hors ZA1, une ou plusieurs cases isolées contenant 1 seule bague.
Il est assez évident que dans ce cas il n'y aucune action à accomplir pour remplir ces cases d'une bague. La règle 2 montre qu'on fait l'économie d'un n(n+1)/2 pour chaque bague isolée. Il faut éviter ces bagues isolées.

2) Il y a une ZA2 (ou plus) positionnée de telle sorte qu'elle peut fusionner avec ZA1. (fusionner au sens où en s'élargissant il n'y a plus de cases vides entre et il reste des bagues surnuméraires). En appliquant des actions inverses, on va regrouper en une seule ZA. Il faudra plus d'actions inverses pour construire cette nouvelle ZA que d'actions qui ont amené à la fusion ZA1+ZA2. En effet, reconstruire une nouvelle ZA entre ZA1 et ZA2 nécessite de récupérer les bagues surnuméraires de ZA1 et ZA2, donc déplacements supplémentaires.
Il ne faut pas de conf avec des ZA fusionnables.

3)Il y a une ZA2 (ou plus) indépendante de ZA1 (chacune peut remplir les cases de son secteur). Dans ce cas, on applique les formules avec 2n ou 2n+1 bagues. Comme on sait que la formule est à peu près n^3/3, on a bien:
n^3/3+m^3/3<(n+m)^3/3 avec n et m>=2.

Conclusion: il ne faut ni bagues isolées, ni 2 ou plus ZA. Il ne faut qu'une seule ZA.

 #15 - 01-05-2015 19:04:35

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Les chevalières de la table ronde (étape 3

@dbab3000 : oui. Il reste en effet à prouver qu'on ne peut pas faire mieux.

@Vasimolo : p’têt ben qu’oui... p’têt ben qu’non smile

@nodgim : avant de valider ta démo, deux petites remarques.

J'aime beaucoup ta règle 1 (ta démo n'a rien à voir avec la mienne, donc je la découvre en te lisant), mais il faut expliciter ce que tu veux dire par "la même zone". Par exemple, 005000 nécessite moins d'actions que 022100, mais il faut dire que ce n'est pas "la même zone". Enfin bon, c'est un détail.

Plus gênant à mon sens : s'il n'y a qu'une seule zone active, OK, mais je ne comprends pas comment tu démontres que la meilleure configuration initiale ne contient qu'une seule zone active ?

 #16 - 02-05-2015 14:00:32

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

les chevalières fe la table ronde (étape 3)

Salut,
J'ai complété la fin de mon argumentation pour l'unicité de la zone active.

 #17 - 02-05-2015 18:18:14

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Les chevalières de la table ronde (étape 33)

@nodgim : c'est bon, démo validée smile

Une petite remarque : je pense que tes démos seraient simplifiées si tu définissais tes ZA a posteriori, ie 2 nobliaux voisins sont dans la même ZA si à la fin de la partie ils ont échangé au moins une bague (la définition fonctionne grâce au 3e point de l'étape 2).

 #18 - 03-05-2015 21:24:29

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

Les chevalières de la ttable ronde (étape 3)

Je dirais de tout mettre sur un nobliau, je n'ai aucune preuve, j'essaie d'y réfléchir demain si j'ai du temps


Un promath- actif dans un forum actif

 #19 - 03-05-2015 22:34:00

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Les chevalières de la table ronde (étape 3))

Si ça peut en motiver certains, il existe une démonstration élégante et facile à comprendre (mais moins à trouver smile ).

 #20 - 05-05-2015 11:15:55

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Lees chevalières de la table ronde (étape 3)

Félicitations à nodgim pour sa démo, ainsi qu'à enigmatus et dbab3000 pour avoir identifié les meilleures répartitions.

Je vous livre comme promis une démonstration que je trouve assez élégante.

On commence par se rappeler le corollaire de la démo de Vasimolo dans l'étape 1 : il existe au moins 2 voisins qui ne s'échangent aucune bague dans tout le processus, ce qui fait que la rotondité de la table est en réalité cosmétique, le jeu est un jeu linéaire déguisé. Une fois le jeu terminé, on place donc les nobliaux en ligne de sorte que les deux nobliaux extrêmes ne se soient rien échangé : ainsi, dans [abc...z], a et z ne s'échangent rien au cours de la partie.

On va distinguer 2 cas, commençons par le cas où n est impair. On associe un "poids" à chaque bague en fonction de sa position : distance(bague,centre)². C'est-à-dire que les poids sont, en fonction des positions, ...9;4;1;0;1;4;9... Quant au poids de la position, c'est la somme des poids des bagues.

Par exemple, la position [0023010] a pour poids 0.9+0.4+2.1+3.0+0.1+1.4+0.9 = 6.

Chaque coup va augmenter le poids de la position de 2, car le poids des deux bagues jouées passe de 2x² à (x-1)²+(x+1)²=2x²+2.

Le poids minimal d'une position est 0, lorsque toutes les bagues sont en possession du nobliau central : [...00(n-1)00...]. En se rappellant qu'une position finale est du type "tous les nobliaux sauf 1 ont une bague", le poids maximal est le poids de la position [...1110111...] où le 0 est centré. Comme de plus, un argument de symétrie montre que cette position finale est celle à laquelle on aboutit en partant de la position minimale, les parties les plus longues sont celles qui vont de la première à la dernière position. En corollaire, on a la longueur de la partie : somme_{k=1...(n-1)/2} k².

Dans le cas où n est pair, c'est toujours le même poids : distance(bague,centre)², mais comme le centre tombe entre 2 nobliaux, cela donne les poids ...25/4;9/4;1/4;1/4;9/4;25/4... La propriété de l'augmentation du poids de 2 est conservée. Les positions de poids minimal sont celles où les bagues sont réparties dans les deux cases centrales, soient celles du type [...00(k)(n-1-k)00...]. Les positions de poids maximal sont celles pour lesquelles c'est un des deux nobliaux centraux qui n'a pas de bague, soit [...111011...] et [...110111...].

Il reste à constater, par récurrence par exemple, que [...00(n/2)(n/2-1)00...] et [...00(n/2-1)(n/2)00...] sont les seules positions minimales aboutissant à une des deux positions maximales, pour conclure la preuve.

 #21 - 05-05-2015 11:29:26

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

Les chevvalières de la table ronde (étape 3)

Bien vu Ebichu. Je me doutais bien qu'il y avait une entropie. C'est plus abouti que ma démo, car il fallait bien d'abord trouver le coeff des positions. C'est bien sûr une forme carrée.

 #22 - 05-05-2015 22:23:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Les chevalières dee la table ronde (étape 3)

J'étais arrivé au résultat mais sans démonstration smile

Une série très intéressante que l'on peut voir comme une version en dimension 1 du problème du tas de sable .

Vasimolo

 #23 - 06-05-2015 08:47:07

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

Les chevalières de la table rnode (étape 3)

Ben oui Vasimolo: le résultat, assez intuitif, précède la démo, plus longue. C'est souvent comme ça en Math, non ?

 #24 - 06-05-2015 18:01:15

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Les chevaalières de la table ronde (étape 3)

Oui mais c'est tellement plus joli quand le résultat est contre-intuitif et la démonstration expéditive et bluffante .

Vasimolo

 

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 : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Etae (1) —

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