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 - 16-04-2015 00:17:19

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

les vhevalières de la table ronde (étape 1)

Nos n nobliaux sont toujours assis autour d'une table ronde, et commencent par se répartir n-1 chevalières (des bagues, donc smile ). Un nobliau peut avoir plusieurs ou même la totalité des chevalières.

Mais nos nobliaux sont désargentés : leurs chevalières sont en authentique toc, si bien qu'ils ne rechignent pas à faire preuve de charité, en ménageant toutefois les susceptibilités. Ainsi, à chaque tour de jeu, un certain nobliau disposant d'au moins 2 chevalières va donner une chevalière à chacun de ses voisins : pas de jaloux.

Il s'agit maintenant de démontrer que ce petit jeu d'échanges va se terminer, c'est-à-dire qu'au bout d'un nombre fini d'étapes, nous serons dans une situation où plus aucun nobliau ne peut donner de chevalière.

Un exemple évitera bien des confusions : avec n=8 nobliaux et donc 7 chevalières, une répartition initiale possible est [25000000]. Partant de là, deux cas sont possibles : ou bien c'est le premier nobliau qui commence à donner ses chevalières, et on obtient [06000001], ou bien c'est le deuxième, et on obtient [33100000]. Puis, dans chaque cas, on continue...

Attention ! Il est très facile de faire du gloubiboulga sur ce problème ; démonstration correcte exigée, un peu de rigueur que diable !

  • |
  • Répondre

#0 Pub

 #2 - 16-04-2015 12:07:08

NickoGecko
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1819

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

Bonjour,


A première lecture, cela me fait penser à l'énigme

"embouteillage sur le périph' "

à part qu'ici, la table est encore "droite" alors que le périphérique est circulaire ...

Je reviens ....

A+smile


Il aurait pu pleuvoir, con comme il est ! (Coluche)

 #3 - 16-04-2015 12:24:04

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

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

@NickoGecko : ce n'est pas un hasard, lire l'énigme sur le périph' m'a fait penser à ce problème que j'avais dans mes cartons. smile

À partir de cette étape, la table, comme le périphérique, est ronde, et ce ne sera pas le moindre de vos soucis. big_smile

J'espère que la notation de mon exemple est claire : le 1er et le 8e nobliaux sont voisins, c'est pour ça que [25000000] peut donner [06000001].

 #4 - 16-04-2015 18:21:14

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

les chevalièreq de la table ronde (étape 1)

Bonsoir .

Je crois que j'ai une idée du codage de la position . On note ni le nombre de pièces à la distance i d'un chevalier ( n0 représente le nombre de ses pièces ) . Sa somme notée S est définie par =n0+2.n1+4.n2+8.n4... . A chaque coup la somme de chaque chevalier augmente de 2^(k-1) ( k est la distance entre le chevalier qui distribue les pièces et celui dont on calcule la somme ) sauf si c'est son vis-à-vis qui a distribué les chevalières la somme restant alors stable . Comme chacun des S ne peut pas grandir indéfiniment et que la même personne ne peut pas distribuer continuellement des chevalières , les échanges vont nécessairement s'arrêter .

Vasimolo

 #5 - 16-04-2015 18:34:50

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

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

@Vasimolo : idée intéressante, néanmoins :
* je suppose qu'il s'agit de "8.n3" au lieu de "8.n4" ? (pas grave)
* dans le cas du vis-à-vis, la somme ne reste pas stable mais diminue (nettement plus gênant).

 #6 - 16-04-2015 18:54:41

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

Les chevalières de la table ronde (éttape 1)

En effet mais bon , le vis-à-vis du distributeur baisse de 2^k les autres augmentent de 2^i avec i la distance entre les deux chevaliers . Globalement la somme de tous les S varie toujours dans le même sens donc elle va forcément coincer à un moment donné .

Pas le temps de finir ce soir , on m'attend au volley smile

Bonne soirée .

Vasimolo

 #7 - 16-04-2015 19:28:28

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

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

"la somme de tous les S varie toujours dans le même sens" : en quelque sorte, oui.

"donc elle va forcément coincer à un moment donné" : et pourtant non smile

 #8 - 16-04-2015 23:04:31

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

Les chevalières de al table ronde (étape 1)

Oui en fait la somme est constante , il faudra trouver autre chose sad

Vasimolo

 #9 - 18-04-2015 11:43:53

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

lzs chevalières de la table ronde (étape 1)

Pour réveiller un peu le fil , une nouvelle idée pas encore complètement aboutie smile

On raisonne par l'absurde en supposant que les échanges durent indéfiniment . Alors tous les chevaliers participent continuellement à la fête sinon le sage voisin d'un multi-distributeur croulerait sous les offrandes . Comme il y a un nombre fini de chevaliers et chevalières le phénomène va forcement boucler . Dans une boucle chaque distributeur va apparaître le même nombre de fois , sinon ceux qui donnent moins vont recevoir beaucoup trop . Après je bloque un peu ...

Peut-être une histoire de parité le donneur gardant la même parité contrairement à ses voisins ...

A suivre smile

Vasimolo

 #10 - 18-04-2015 12:29:48

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

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

On appelle une case active une case où un chevalier (=case) donne une bague en amont et en aval. C'est donc au départ une case à au moins 2 bagues. S'il y a plusieurs cases actives successives, qu'on va appeler zone active, alors le bilan après un passage complet sur cette zone est:
-La 1ére et la dernière case perdent 1 bague. Pour la 1ere case, la bague manquante est en amont. Pour la dernière case, la bague manquante est en aval.
-Les cases intermédiaires ont un nb de bagues inchangé. En effet, 1 case donne 2 bagues, mais en reçoit 2 (une de la case amont, une de la case avale).
Une zone active, dans le sens des échanges, a pour 1er case une case d'au moins 2 bagues et pour dernière case celle juste avant une case sans bague (vide). Donc, les cases à une seule bague qui suivent une 1ère case active font partie de la zone active. En effet, après échange d'une case active, une case à 1 bague située juste en aval deviendra active par acquisition d'une bague.


Exemple de zone active:
(Les 0 sont les cases vides, et les autres nombres représentent le nombre de bagues dans une case)

...021111100... qui donnera après échanges de G à D ---->....111111010...
Les 0 sont les cases vides, et les autres nombres représentent le nombre de bagues dans une case.

Une configuration globale des bagues sur un cercle peut être décrite ainsi de cette façon:

;zone active A;0;suite éventuelle de 0 et de 1;zone active B;0;suite éventuelle de 0 et de 1;zone active C;0;suite éventuelle de 0 et de 1;....;zone active A.

Dans la suite du texte, les échanges ne seront plus représentés en détail, mais seulement après un passage global sur zone active.

Montrons qu'une zone active indépendante s'étale en largeur et s'écrase en hauteur (l'empilement des bagues diminue)

En amont:
...0000A. A est une case avec assez de bagues pour la démo. Son cardinal change avec les passages, mais par simplification, on garde A (réservoir de bagues)
Suite de passages successifs:
0000A
0001A
0002A
0010A   
0011A
0012A
0021A
0111A
etc...
quand le A est épuisé, on ira chercher un autre empilement (au moins 2 bagues) en aval.

On émet à partir de A une seconde bague qui recule à chaque passage et qui vient au bout occuper une case vide.

En aval:
A00000
A10000
A01000
A11000
A10100
A01100
A11100
A11010
A10110
A01110
etc..
quand le A est épuisé, on ira chercher un autre empilement (au moins 2 bagues) en amont.

C'est comme si on allait chercher la 1ère case vide et qu'on la ramenait jusqu'à A pour l'occuper.

En amont ou en aval, il y a bien étalement en largeur et grignotage des empilements.

Si entre 2 zones actives, il y a un nombre de cases vides disponibles inférieur à ce que peut occuper les zones actives, il y aura fusion des 2 zones actives.

Mention pour le cas particulier suivant:

Une succession de 02020, c'est à dire de zones actives minimales (1 case isolée de 2 bagues).
0202020
1020201
1102011
1110111
On a là encore une dégradation de la zone active en une suite de 1.

Fin du cas particulier.


Comme le nombre de cases est supérieur de 1 unité au nombre de bagues, toutes les cases moins 1 seront occupées par une seule bague.

Si le nombre de bagues était égal au nombre de cases, alors on ne pourrait pas mettre une bague dans chaque case.
Scénario des échanges dans ce cas:
11111211110
11112111101
11121111011
11211110111
etc...
la zone active reste à largeur constante. Elle n'est jamais éliminée.

En revanche, s'il y a une case de plus que de bagues:
11112111100
11121111010
11211110110
12111101110
21111011110
11110111111

Conclusion:
Le final des échanges sera, par disparition des zones actives démontrée, une suite de 1 dans chaque case + 1 case vide.

 #11 - 18-04-2015 18:33:47

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

Les cheavlières de la table ronde (étape 1)

@Vasimolo & nodgim : vous avec 2 méthodes très différentes. Les deux sont intéressantes, mais pour l'instant je ne peux en valider aucune. Je peux juste vous dire qu'il y en a une des deux dont je sais qu'elle aboutit (l'autre peut-être aussi, d'ailleurs, mais je ne sais pas comment).

@Vasimolo : comme tu dis, "à suivre". Bonne chance smile

@nodgim : tes définitions sont floues (ou mes lunettes sont sales cool ), ce qui fait que j'ai du mal à suivre ton raisonnement, et que je ne vois pas comment tu conclues. Est-ce que tu peux expliciter un peu ton raisonnement ?
PS : j'ai bien lu ta prose, la preuve, il y a une coquille à la dernière ligne smile

 #12 - 18-04-2015 19:20:51

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

kes chevalières de la table ronde (étape 1)

Salut Ebichu j'ai deux raisonnements jusqu'à maintenant et je ne sais pas comment conclure les deux, peut tu me dire si l'une des deux est bonne pour que j'essaie de conclure ou je dois chercher une autre méthode :
1)Supposons par absurde que les échanges ne s’arrêtent pas, ça veut dire que les nombres d'étapes sont infinies ce qui veut dire qu'il y a des répartitions qui se répètent, maintenant on doit démontrer que seuls les répartitions possibles qui se répètent sont du genre 0111111 qui signifie que les échanges se sont arrêtés ce qui est contradictoire à notre supposition.
2)Puisque les échanges vont s’arrêter ça veut dire que qu'il s’arrête dans la répartition 01111111 maintenant on doit démontrer qu'en commençant avec cette répartition on peut arriver à n'importe quelle répartition en inversant les règles.
Merci d'avance pour ton aide ^^
Je viens de remarquer une donnée dans l'énoncé que je n'ai pas pris en compte, j'espère que ça va être utile .

 #13 - 18-04-2015 21:16:56

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

Les chevalières de l table ronde (étape 1)

@dbab3000 : je ne connais aucune démo qui fonctionne selon une de ces deux méthodes ; cependant, ça ne prouve pas pour autant que ce sont des fausses pistes. Bon courage pour la suite.

 #14 - 18-04-2015 21:50:53

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

les chebalières de la table ronde (étape 1)

Cette fois ci je vais proposer une réponse, dans les répartitions on a au moins un zéro, mais pour faire des échanges on doit avoir au moins 2 zéros ,puisque on doit démontrer que les échanges vont s’arrêter ça veut dire qu'on doit démontrer que le nombre de zéros va atteindre 1. On suppose que f(n) est une fonction qui représente le nombre de zéro tel que n est représente le nombre d'étapes et des échanges effectués .Voici les cas (je vais prendre seulement une partie des nobliaux car on effectue seulement un échange par étape  les nombres représentent le nombre des chevalières):
-030 devient 111 f(n+1)=f(n)-2
-000 ou 111 pas de changement f(n+1)=f(n)
-130 devient 211 f(n+1)=f(n)-1
-121 devient 202 f(n+1)=f(n)+1
Ces les 4 cas possibles pour la fonction, on peut dire que la fonction a plus de chance de diminuer et de tendre vers 1.
PS:Je sais que la réponse n'est pas complète j'essaie de trouver un moyen pour prouver que f(n+1)=f(n)+1 n'est pas important.
A suivre.

 #15 - 19-04-2015 08:25:00

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

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

@Ebichu:
Ce n'est pas flou, mais peut être pas clair. A quel endroit est il nécessaire de donner une explication ou une précision ? J'ai ajouté ça et là qq remarques dans le texte.
PS: bien vu la coquille.

 #16 - 19-04-2015 09:37:01

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

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

La nuit porte conseil smile

On note C1 ; C2 ; Cn les n chevaliers dans le sens giratoire avec C1 et Cn voisins . On suppose par l’absurde que les échanges de chevalières sont interminables et on note Pi la première chevalière échangée entre Ci et C(i+1) ( en posant C(n+1)=C1 ) . On peut supposer aussi que la chevalière Pi restera entre les mains de Ci ou C(i+1) en effet si l’un doit la donner , il peut tout à fait la donner à l’autre . On a vu que tous les chevaliers participaient à la fête donc chaque paire CiC(i+1) va avoir sa chevalière numérotée i ce qui contredit le fait qu’il n’y a que n-1 chevalières .

Vasimolo

 #17 - 19-04-2015 10:39:32

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

les chevalières de la table robde (étape 1)

@Vasimolo : Joli ! Je ne connaissais pas cette preuve ; j'en ai une sous la main un peu équivalente, dans le sens où elle démontre directement ce que tu démontres par l'absurde, mais elle est nettement moins élégante que la tienne. Félicitations !

@nodgim : j'y vois un peu plus clair avec tes précisions ; tu vas me haïr mais je ne suis pas encore satisfait. Tu ne définis pas rigoureusement ce que tu appelles "zone active", "passage complet", or je pense que c'est nécessaire pour bien comprendre ton raisonnement. De plus, j'ai l'impression que ta démonstration ne tient pas compte du fait que ce sont les nobliaux qui choisissent dans quel ordre ils échangent leurs bagues, et qu'au contraire c'est toi qui leur impose l'ordre. Ce n'est pas parce que ça finit dans un certain ordre que ça finit dans tous les ordres.

 #18 - 19-04-2015 11:08:41

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

les chevzlières de la table ronde (étape 1)

J'avais en effet compris que l'échange se faisait dans un sens donné: tous ceux qui pouvaient échanger le faisaient. Du coup ma démo n'est plus valable.
Je regarde pour le cas d'échanges dans un ordre aléatoire.

 #19 - 19-04-2015 18:45:06

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

les chzvalières de la table ronde (étape 1)

Faut-il introduire une variable qui décroît à chaque tour?


Un promath- actif dans un forum actif

 #20 - 19-04-2015 18:55:58

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

Les chevallières de la table ronde (étape 1)

@Promath : c'est une façon de faire. Mais trouver cette variable n'est pas chose aisée, et faire une démo propre par la suite non plus smile

 #21 - 22-04-2015 11:03:50

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

Les chevalières de la table ronnde (étape 1)

Tout d'abord félicitations à Vasimolo, qui nous procure une démonstration élégante, et qui permet du même coup de démontrer que quelle que soit la répartition initiale, il existe (au moins) deux nobliaux voisins qui n'échangeront pas de chevalière.

La tentative de nodgim peut être menée à bien, mais elle nécessite une rédaction beaucoup plus longue que celle de Vasimolo pour être établie rigoureusement, et utilise des résultats que je vais vous demander de démontrer dans d'autres épisodes, donc je m'abstiens de la rédiger pour le moment.

Enfin, pour répondre à la demande de Promath, il existe une autre démonstration, assez élégante également, mais un peu plus longue à formaliser que celle de Vasimolo. Étant donnée une position comme [10003012], on appelle son "représentant" la position qui s'obtient à partir d'une rotation ou d'une symétrie, et qui soit minimale pour l'ordre lexicographique : ici, ce serait [00012103]. Alors, étant donnée une partie, la liste des représentants est strictement croissante pour l'ordre lexicographique, ce qui permet de conclure. Je vous le laisse en exercice smile

 #22 - 22-04-2015 18:07:37

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

led chevalières de la table ronde (étape 1)

Bravo Vasimolo et Ebichu !

 #23 - 22-04-2015 19:09:41

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

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

Félicitations! Je n'y aurais jamais pensé Vasimolo!


Un promath- actif dans un forum actif
 

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 : Pim, Pam 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