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 - 22-04-2015 11:37:34

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

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

Nous retrouvons nos n nobliaux et leurs (n-1) chevalières, et nous rappelons une caractéristique ennuyeuse de leur petit jeu d'échanges : à chaque tour de jeu, ce sont eux, et pas nous, qui décident quel nobliau va jouer.

Par exemple, partant de la position [0020310], voici deux parties possibles :

[0020310] [0021120] [0102120] [0110220] [0111030] [0111111]

[0020310] [0101310] [0102120] [0102201] [0110301] [0111111]

Cependant nos nobliaux ont tendance à surestimer leur libre arbitre. Saurez-vous leur rappeler qu'ils ne contrôlent nullement leur destinée, en prouvant qu'étant donnée une position initiale, quels que soient les coups joués :

* une seule position finale est  possible (c'est-à-dire que ce sera toujours le même nobliau qui finira sans chevalière - le premier, dans notre exemple).
* toutes les parties terminent en le même nombre de coups (5 dans notre exemple).
* le nombre de coups joués par chaque nobliau sera le même (dans notre exemple, les 7 nobliaux jouent respectivement [0011210] fois, ce qui signifie par exemple que le 5e nobliau est le plus généreux en donnant deux fois 2 bagues).

Attention ! La seule démonstration que je connais est basée sur un lemme peu connu, si vous n'avez jamais vu de problème de ce type, ça risque d'être dur.

  • |
  • Répondre

#0 Pub

 #2 - 22-04-2015 19:25:18

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

Les chevalière sde la table ronde (étape 2)

1ère Demande
Numérotons les cases 1 à n dans le sens antihoraire (je visualise mieux)
Appelons S la somme de la positions des chevalières, modulo n (de 1 à n)
Cette somme ne varie pas. En effet quand un nobliau donne ses chevalières, l'une des chevalière perd 1 modulo n, et l'autre gagne 1 modulo n, même si le nobliau est sur la case n ou 1.
S est donc invariant. Pour une position avec un S donné (donc prenant des valeurs de 1 à n):
La somme totale des n cases est n(n+1)/2 (mod n)
La case libre à la fin vérifiera n(n+1)/2-x congru à S (mod n) soit x congru à n(n+1)/2-S. Comme S est fixé au début, il n'y a qu'une case libre possible à la fin, donc tous les échanges convergent vers une même fin

Edit: modifié 8 en n, généralisation.

2ème Demande, 3ème Demande
Comme l'avait dit Vasimolo, la partie a une fin. Et cette fin stipule qu'il existe un état d'équilibre. Sa démonstration amène un corollaire, qui lui stipule que tous les nobliaux ne donneront pas de chevalières. En effet si c'était le cas ils pourraient les échanger entre eux et on aurait un état infini dont parlait Vasimolo, impossible donc. Ainsi tous les nobliaux ne donnent pas au cours d'une répartition.
Prouvons que le nombre de coups est fixé pour chaque nobliau.
Notons N(k) le nombre de "donations" par un nobliau k (lz nombre de fois où il donne des chevalières. D(k) est le nombre de chevalières au début pour le nobliau k, dans une première situation.
On appelle k le nombre de chevalières à la fin, on a k=N(k-1)+N(k+1)-2N(k)+D(k).
Supposons: pour deux chemins différents, on avait un N(k) plus grand pour un des deux chemins, (donc un nombre de coups différents pour un des nobliaux) on aurait inévitablement un N(k+1) plus grand (on ne perd aucune généralité à choisir le nobliau suivant), soit de 1 unités, soit de 2 unités MINIMUM (tout dépend si le nobliau k-1 augmente aussi son nombre de dons), en effet c'est ce que stipule la formule donnée plus haut
Dans les deux cas, cette augmentation se répercutera de proche en proche sur les nobliaux k+2 (et éventuellement k-2), et ainsi, sur tous les nobliaux (en effet si N(i) augmente N(i+1)+N(i-1) augmente aussi de deux unités, donc de proche en proche ils augmentent tous)
Dans tous les cas, il y aura alors une augmentation de n coups au total, et chaque nobliau aura donc fait 1 don.
Or nous avons vu plus haut que c'était impossible.
On aboutit à une contradiction, on n'a donc PAS de N(k) plus grand pour deux chemins différents. Donc le nombre de donc pour chaque chevalier est constant.
Cela prouve donc la demande 2, et simultanément la 3 (Si les nombres de dons sont constants leur somme aussi).

Voici donc pour moi smile
J'aime beaucoup cette énigme! Merci smile


Un promath- actif dans un forum actif

 #3 - 23-04-2015 15:34:20

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

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

Félicitations à Promath- pour ses démonstrations, plus simples que celles que je connais, et qui fonctionnent smile

 #4 - 24-04-2015 09:29:59

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

Les chevalières de la table ronde (éape 2)

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.   

On sait qu'on doit aboutir à une conf ..11101111.. Il faut donc opérer des actions sur les cases surnuméraires.

Un bon exemple valant mieux qu'un long discours:
Soit la conf 0024000. Actions minimales nécessaires:
A:..............0012000.
analyse: la case 3 reçoit 2 (bagues) et donne 2, nombre inchangé, il faut ajouter une action. Idem pour la case 4.
A:0023000
analyse: les cases 2 et 5 reçoivent 2 et 3 bagues, il faut compenser par une action dans ces cases.
A:0123100
analyse: nouvelles actions à faire sur les cases 3 et 4.
A:0134100
analyse: action nécessaire sur case 5.
A:0134200
analyse: nouvelle action nécessaire sur la case 6:
A:0134210
analyse:
conf de départ: 0024000
A:...................0134210
conf finale:.......1111101

On est arrivé de la conf de départ à une conf finale avec le nombre minimum d'actions nécéssaires. Il est à noter qu'on ne peut pas ne pas aboutir à la conf finale: tant qu'il y a des cases surnuméraires, il y a des actions nécéssaires.

Imaginons maintenant un autre scénario avec la même conf de départ qui aboutirait aussi à la conf finale avec plus d'actions que 0134210. Ajouter une action sur l'une quelconque des cases obligerait à ajouter une action sur toutes les cases, afin d'éviter d'avoir une case avec un nombre négatif de bagues. En effet, ajouter une action dans une case, c'est y ôter 2 bagues. Pour compenser, il faut faire une action sur les 2 cases voisines, et par effet domino, sur toutes les cases. Or il est impossible d'accomplir une action sur toutes les cases. Il y a tjs au moins 2 cases non actionnées dans un scénario.

Preuve de l'impossibilité d'actions sur toutes les cases dans un scénario.

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. Par extension, la zone active est celle où il y a eu ou aura au moins 1 action enregistrée (1 case à 2 bagues est donc de fait une case de la zone active) Au cours de son évolution par des actions, une zone active va s'étaler mais avec cette réserve que 2 cases consécutives ont au moins 2 bagues (principe de Vasimolo où une bague est enchainée à la frontière entre 2 cases). Une zone active qui n'a plus aucune bague surnuméraire (nb de cases vides=nb de bagues qui dépassent 1 bague par case) ne peut  donc plus s'agrandir. Or il existe, dans l'ensemble du cercle, une case vide de plus: celle ci ne peut donc être active.

 #5 - 24-04-2015 21:55:08

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

les chevalières de lz table ronde (étape 2)

@nodgim : je ne vois pas comment tu prouves que tes nombres d'actions seront forcément 0134210, ou que ta conf finale est 1111101 (et pas 1111011 ou 1110111 par exemple).

 #6 - 25-04-2015 09:46:57

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

Les chevalièrres de la table ronde (étape 2)

Je n'ai pas le choix ! Je ne peux pas faire autrement. Je ne suis pas libre des cases à actionner pour faire baisser le nombre de bagues dans une case de x à 1 ou 0. Je sais seulement que pour faire baisser x à 0 ou 1, il me faut x/2 actions. Au minimum. Le zéro final n'est pas connu, il se déduit des actions menées.

 #7 - 25-04-2015 10:51:04

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

Les chevalières de la tabl ronde (étape 2)

@nodgim : mais pourquoi ce que tu observes sur cet exemple serait valable pour n'importe quelle position de départ ?

 #8 - 25-04-2015 12:16:57

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

Les chealières de la table ronde (étape 2)

Il est évident ce problème , pourquoi ça fait dix heures que je sèche dessus lollollollol

On considère tous les échanges possibles à partir de la position initiale . La réalisation de n’importe lequel d’entre eux ne va bloquer aucun des autres qui devra donc être réalisé à un moment ou à un autre . On peut donc par exemple effectuer tous ces échanges en même temps et réitérer le même processus aux rangs suivants . Comme l’ordre des échanges n’a aucune incidence sur le résultat final , c’est fini .

J'attends la suite avec impatience smile

Vasimolo

 #9 - 25-04-2015 12:21:21

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

les chevalières de ma table ronde (étape 2)

Parce que partout où il y a possibilité d'actions (2 bagues ou plus par case) je ne pourrais pas faire autrement que d'accomplir cette action. Si la case contient 2n ou 2n+1 bagues, je ne pourrais pas faire autrement que d'y accomplir n actions au minimum. Je n'ai pas le choix.
En fait, je fais un scénario d'actions minimales à opérer dans chaque case, pour en arriver in fine au nombre d'actions total.
Si en m'y prenant autrement, j'arrive à un autre résultat avec moins d'actions, il y aurait comme un problème, puisque mon scénario prévoit le nombre minimum d'actions. Maintenant, c'est vrai qu'on peut rétorquer qu'avec une autre méthode, on pourrait arriver à un autre résultat avec plus d'actions.

 #10 - 25-04-2015 12:53:38

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

Les chevalières d la table ronde (étape 2)

@Vasimolo & nodgim : vous me faites tous deux à peu près la même réponse. En fait, vous êtes arrivés à visualiser le résultat du "lemme" dont je parlais dans l'énoncé, mais vous ne le démontrez par rigoureusement. Ça ne m'étonne pas que vous trouviez ça évident : ça s'intuite bien, mais ça nécessite quand même une démonstration.

Le fait est que les nobliaux peuvent décider d'organiser leurs échanges dans n'importe quel ordre : qu'est-ce qui prouve que s'ils commencent à jouer dans une certaine zone du cercle, ça ne va pas permettre à un certain nobliau d'accumuler des chevalières et par la suite, de jouer, alors que s'ils avaient commencé à jouer dans une autre zone, il n'aurait pas pu ?

 #11 - 25-04-2015 16:28:49

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

les chevakières de la table ronde (étape 2)

Il me semble Ebichu que tu as raté une partie de mon argumentation : "La réalisation de n’importe lequel d’entre eux ne va bloquer aucun des autres qui devra donc être réalisé à un moment ou à un autre .

Tous les échanges vont donc être faits à un moment ou un autre et comme le temps de la réalisation est sans effet sur le résultat ...

Vasimolo

 #12 - 25-04-2015 16:58:39

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

les chevalièrzs de la table ronde (étape 2)

@Vasimolo : Je vois bien ce que tu veux dire, mais la rédaction ne me convainc pas. Est-ce que tu pourrais le rédiger avec des quantificateurs, des ensembles, une récurrence,... que sais-je encore ?

Je ne suis pas exigeant au point de demander le recours à un assistant de preuve, mais en l'état actuel, si je ne connaissais pas la rédaction d'une démonstration, je ne serais pas convaincu du résultat.

 #13 - 25-04-2015 20:16:19

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

les chevalières de la tavle ronde (étape 2)

J'ai la solution par la représentation d'un graphe. On représente toutes les cases par des colonnes et toutes les bagues unitairement dans chaque colonne et alignées sur une seule ligne. On apparie les bagues. Sur une seconde ligne, on représente les bagues à leur nouvel emplacement: pour les appariées, chacune dans la colonne voisine, par les bagues seules, dans la même colonne. On relie chaque bague d'une ligne à l'autre par un trait pour bien suivre leur cheminement. On réapparie les bagues regroupées dans leur nouvelle case et on recommence l'opération jusqu'à la dernière ligne.
Ce graphe étant fait, toutes les actions qu'on pourra faire peuvent être suivies dans ce graphe, par exemple en noircissant les actions. La seule modification qu'on pourrait être amené à faire est un reappariememt des bagues au sein d'une même case, de façon à ne pas rester bloqué dans une case à une certaine ligne alors que l'action peut se continuer. Ce reappariement ne change rien au graphe.
Au final, on aboutira toujours au même résultat.

Il faudra sans doute que je représente un tel graphe pour mieux me faire comprendre....

 #14 - 25-04-2015 22:35:18

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

les chevalières de la rable ronde (étape 2)

@nodgim : Oui, un petit dessin, ça serait sympa smile

 #15 - 26-04-2015 10:18:40

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

Les cchevalières de la table ronde (étape 2)

Je renonce au graphe: certains scénarios sont difficilement démontrables...

 #16 - 26-04-2015 11:11:51

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

Les chevalières de la table ronde (étap 2)

Comment j'ai pu passer à côté de cet invariant !!!

On numérote les chevaliers de 1 à n et on attribue la masse k à chaque chevalière du chevalier k . On retrouvera la même masse totale des chevalières modulo n en réinitialisant les masses après un échange de chevalières . La position finale est donc unique .

Il reste à voir pourquoi le nombre d'échanges est constant smile

Vasimolo

 #17 - 26-04-2015 17:51:30

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

Les chevalières de la tabel ronde (étape 2)

@Vasimolo : bien vu ! Promath a fait le même raisonnement que toi pour ce premier point.

 #18 - 26-04-2015 19:39:40

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

les chevalièred de la table ronde (étape 2)

Le lemme en question a t'il un rapport avec le fait qu'au moins un chevalier sans bagues au départ ne donne aucune bague de toute la partie ?

 #19 - 27-04-2015 13:17:34

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

Les chevaières de la table ronde (étape 2)

@nodgim : non, le lemme n'utilise pas cela, il utilise uniquement le fait que la partie se termine. Par contre, ce à quoi tu fais allusion pourrait être une piste pour une autre démonstration.

 #20 - 27-04-2015 18:41:51

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

Les chevalèires de la table ronde (étape 2)

Oui, bien sûr, elle me servirait directement pour la preuve recherchée ici, en prolongeant la démo entamée (nombre mini d'actions).
C'est assez évident que dans tous les cas au moins 1 case n'est pas émettrice de bague, 2 cases même en fait, mais une seule suffirait pour la preuve.

 #21 - 28-04-2015 12:17:03

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

Les chevalières de la table ronde (étap 2)

J'ai complété le msg 4 pour une démo complète.

 #22 - 28-04-2015 18:29:35

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

Les chevalièrs de la table ronde (étape 2)

Pour les demandes 2 et 3 , j'avais commencé à regarder dans le sens de Promath . Je n'avais pas réagi sur le fait qu'augmenter les échanges de tout le monde était incompatible avec la léthargie de certains chevaliers .

Moi aussi je l'aime bien cette série ...

... et j'attends la suite avec impatience smilesmilesmile

Vasimolo

 #23 - 28-04-2015 22:04:24

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

les chevalières de la yable ronde (étape 2)

Félicitations à vous pour vos efforts, avec cette fois-ci une mention spéciale à Promath pour sa promptitude et sa clairvoyance.

Avant de vous proposer la dernière étape, je vous livre le fameux lemme qui me permettait de résoudre le premier point de l'énigme.

Il est connu sous le nom de lemme "de Newman", ou "du diamant", entre autres, et a pour énoncé sous forme compacte : "s'il y a confluence locale et terminaison, alors il y a confluence".

La terminaison, c'est ce que nous avons démontré à l'étape 1. La confluence, c'est ce que l'on cherche à démontrer, le fait qu'il n'y a qu'un seul état final possible (tous les chemins mènent à Rome). La confluence locale consiste en ce que si on peut jouer deux coups à partir d'une position, alors on peut prolonger ces deux coups en deux suites de coups qui aboutissent à la même position. Dans le problème qui nous intéresse, il suffit d'un coup supplémentaire : si, partant d'une position, les nobliaux a et b peuvent jouer, on remarque que les suites de coups "a puis b" et "b puis a" aboutissent à la même position. Par exemple, à partir de [221000], on peut jouer [031001] ou [302000] ; et de ces deux positions, on peut obtenir [112001].

Sous la contrainte de la terminaison, le lemme de Newman exprime moins formellement que si, dès lors que deux chemins divergent, il est possible de les faire à nouveau converger, alors tous les chemins convergent en un unique état final.

Démontrons maintenant ce lemme par l'absurde. Supposons qu'en partant d'une position P1, il n'y a pas confluence, c'est-à-dire qu'il existe deux suites de coups menant de P1 à deux positions terminales distinctes T1 et T'1. Appelons Q1 la dernière position commune à ces deux suites de coups, les coups suivant Q1 dans ces deux suites sont donc distincts, et mènent à deux positions appelées P2 et P'2. La propriété de confluence locale utilisée au départ de Q1 donne qu'il existe deux suites de coups au départ de P2 et P'2 menant à une position commune, et en terminant la partie au départ de cette position commune, on arrive à une position terminale T2. T2 ne peut être à la fois égale à T1 et T'1, et donc si par exemple T2 est différente de T1, on recommence le raisonnement avec P2, T1 et T2. Ce faisant, on peut construire une suite infinie P1, P2,... de positions, ce qui contredit la terminaison.

Enfin, les deux autres points de l'énigme peuvent être résolus en adaptant la démonstration de ce lemme. Par exemple, le début de la démonstration pour le deuxième point commencerait par : "Supposons qu'en partant d'une position P1, il existe deux suites de coups menant à la position terminale en deux nombres de coups différents L1 et L'1", etc...

 

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 ?

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