Voisins, voisines, (code sur énigme freddy)

totomm · 16-09-2011 11:41:34

Bonjour,

Pour faire plaisir à freddy :-)

# Python 3.2

# Propapation : 2n coquillages, 2n+1 participants

# libre de tous droits. totomm sur Bibm@th le 16/09/2011

N = 10 # CHOISIR N de 1 à 10

récurrence=[] # pour mémoriser les résultats de 1 à N

cercle=[0]*(N+1) # 0 est le centre, 1 à n pour un coté

nb,cercle[0]=0,2*N # nb sera un résultat intermédiaire, et initialisation des coquillages

print("N =",N,", nb =",nb,cercle)

def tous1(n): #teste si aucun participant de 1 à n n'a aucun coquillage (est à 0)

    global cercle

    nbun=0 #pour compter le nombre de 1

    for i in range(1,n+1):

        if cercle[i]==0:

            return 0

    return 1

for Npartiel in range(1,N+1): # de 1 à N partiel on veut des 1 

    while tous1(Npartiel)==0: # on teste s'il y a (s'il reste) un 0

        for i in range(Npartiel,-1,-1): # alors on teste où se trouve un 2

            coefficient=2 #sera 1 pour étape simple

            if cercle[i]>=2: # et on le répartit

                if i==0:

                    cercle[0]-=2

                    cercle[1]+=1

                    nb+=1 # on compte 1 étape

                    coefficient=1

                elif i==1:

                    cercle[0]+=2

                    cercle[1]-=2

                    cercle[2]+=1

                    nb+=2 # on compte 2 étapes par symétrie

                else:

                    cercle[i-1]+=1

                    cercle[i]-=2

                    cercle[i+1]+=1

                    nb+=2 # on compte 2 étapes par symétrie

                break 

        print("N =",N,", nb =",nb,cercle,", x",coefficient) # pour chaque étape

    print("Des 1 jusqu'au rang",Npartiel,", nb =",nb,"***********")

    récurrence.append(nb)

print("fin du programme. récurrence =",récurrence)

freddy · 16-09-2011 15:03:50

salut,

je ne connais pas python, je ne le comprends pas. Donc si tu ne m'expliques pas en clair ce qu'il fait ...

yoshi · 20-09-2011 17:53:45

Salut freddy,

J'ai décidé de te fournir une version du programme qui répond à ton cahier des charges précis :

(A chaque tour, on choisit) au hasard une personne qui a au moins deux coquillages ; celle-ci doit alors donner un coquillage à chacun de ses deux voisins (voisines)

Mais mon programme Python, ce faisant, n'est valable que pour les tirages concernés et ne peut prétendre à être une "démonstration" puisque non exhaustive (et de loin).
On pourrait le relancer autant de fois qu'on veut qu'on n'obtiendrait qu'un exemple à chaque fois.

Donc en langage clair (même si les noms choisis sont transparents), voici ce qui s'y passe...
D'abord, en Python comme dans beaucoup de langages, les indices des tableaux (ici des listes) démarrent à 0.
J'ai donc créé 2 listes :
* l'une nommée Globalite qui conserve l'état des possessions de chacun des membres, repéré par son indice :
21 membres numérotés de 0 à 20
* L'autre D2plus, conserve les indices des heureux possesseurs de 2 coquillages ou plus.

J'initialise mon programme en créant la première liste composée de 21 zéros.
Je tire au sort un nombre (variable nommée pos) entre 0 et 20 (inclus), et j'affecte 20 coquillages à l'individu repéré par l'indice pos.
J'initialise D2plus en lui affectant en première position la valeur pos, indice du seul individu qui possède deux coquillages ou plus.

Pour la "gestion des stocks", j'utilise 3 sous-programmes (des fonctions) :
1. tirage_aleatoire. Sans commentaire.
2. calcule_positions_voisins.
A chaque tour :
* Si l'indice tiré au sort (pos) est 20, je passe les voisins à 0 et 19.
* Si l'indice tiré au sort est 0, je passe les voisins à 1 et 20.
* Si l'indice n'est ni 20, ni 0, je me contente d'ajouter et enlever 1 à la position tirée au sort pour trouver celles (i et k) des voisins.
3. maj_possessions
A chaque tour, je mets à jour les possessions de chacun en enlevant 2 coquillages à l'individu pos et en ajoutant 1 et enlevant aux individus i et k.
Je vide la liste des personnes possédant 2 coquillages ou plus.
Je scrute l'état des possessions de chacune et je réinscris dans la liste ad hoc chaque personne possédant 2 coquillages ou plus.

Je pars pour 384 tours avec une boucle de 1 à 385 (il s'arrête à 384)...
A chaque tour, je tire au sort une position entre 0 et la longueur de la liste D2plus (diminuée de 1) me donnant l'indice de l'heureux élu.
Je calcule alors les positions de ses voisins.
Puis je mets à jour les possessions des 3 personnes concernées

En fin de programme, j'affiche les nombre maximum et minimum de coquillages possédés par les personnes autour de la table ronde, respectivement 2 et 0.

#!/usr/bin/env python

# -*- coding: CP1252 -*-

import random

def tirage_aleatoire(nb):

    x =random.randint(0,nb)

    return x

def calcule_positions_voisins(pos):

    if pos==0:

        i=20

        k=1

    elif pos==20:

        i=19

        k=0

    else:

        i=pos-1

        k=pos+1

    return i,k

def maj_possessions(Globalite,i,j,k):

    Globalite[j]-=2

    Globalite[i]+=1

    Globalite[k]+=1

    Dp=[]

    for l in range(21):

        if Globalite[l]>1:

            Dp.append(l)

    return Globalite,Dp[:]

nb=21

Globalite=[0]*nb

D2plus=[]

pos=tirage_aleatoire(20)

Globalite[pos]=20

D2plus.append(pos)

for i in range(1,385):   

    no=tirage_aleatoire(len(D2plus)-1)

    pos=D2plus[no]

    i,k=calcule_positions_voisins(pos)

    Globalite,D2plus=maj_possessions(Globalite,i,pos,k)

print "Maximum :",max(Globalite)

print "Minimum :",min(Globalite)

Voilà, est-ce que j'ai été clair ? Je me suis efforcé de l'être et de me montrer didactique dans ma programmation.
Pour arriver à l'exhaustivité dans ce cas précis, je devrais à chacun des 384 tours, refaire une boucle sur la totalité des membres de D2plus et les choisir un par un comme si c'était par un tirage au sort, mais je n'ai pas envie de me prendre le chou à gérer ça, sauf si tu le souhaitais...
Bon, il y a 21 possibilités de départ, je me contenterais d'un tirage aléatoire à l'initialisation : inutile de passer en revue les 21 personnes : il suffirait d'effectuer une permutation circulaire des numéros.

@+

freddy · 21-09-2011 10:51:07

Salut yoshi,

ok, je comprends bien la démarche, la procédure telle que tu l'expliques est claire pour moi.

Pour le pgm, je te fais confiance ; un jour peut être, j'essaierai d'apprendre à pitonner !!!

Donc, dans tous les cas, on arrive à cette solution.

Je vais tâcher de le démontrer en langage mathématique.

Bis bald !

totomm · 21-09-2011 11:09:49

Bonjour,

Programme tout à fait OK. On peut même vérifier que la position du 2 final est bien celle initiale des n=20 !
(Je lui ai ajouté un affichage de chaque étape avec numéro de l"étape)

Mais ce programme ne permet, ni de démontrer que le résultat est indépendant de l'ordre dans lesquel les coquillages sont répartis, ni le pourquoi de 384 (ou (somme-1) des n/2 premiers carrés d'entiers), ni le fait que le bouclage circulaire est inutilisé quand on fixe initialement la position des n avec n/2 personnes de chaque coté.

Ce programme est un algorithme "correct", qui se "termine en un temps fini". il n'est pas "complet" dans le domaine traité. (ce que yoshi signale bien à juste raison....)

Mais je maintiens que vaut "démonstration" un algorithme possédant les 3 notions essentielles : "Correction, Terminaison et Complétude."

Cordialement.

Edit : télescopage avec la réponse précédente de freddy dont la démonstration - hors tout programme - sera tout à fait bienvenue.

Dernière modification par totomm (21-09-2011 11:13:36)

yoshi · 21-09-2011 13:03:43

Bonjour,

Programme tout à fait OK. (...)
Ce programme est un algorithme "correct",(...)

C'est vrai que j'ai la triste manie de faire des erreurs non seulement mathématiques, mais aussi de programmation et donc de publier des codes incorrects : une certification extérieure était donc tout à fait indispensable ! Je dois combien ?
J'ai toujours fait attention et si j'en redouble maintenant, allez savoir pourquoi...
Pourquoi "correct" entre guillemets, du bout des lèvres, à prendre avec des pincettes ?

il n'est pas "complet" dans le domaine traité. (ce que yoshi signale bien à juste raison....)

Absolument indispensable aussi d'ajouter "à juste raison" :
1. Voir commentaire ci-dessus.
2. Pour bien enfoncer le clou sur la hiérarchie des codes

Ça commence à devenir lassant...

Mais ce programme ne permet, ni de démontrer que le résultat est indépendant de l'ordre dans lesquel les coquillages sont répartis, ni le pourquoi de 384 (ou (somme-1) des n/2 premiers carrés d'entiers), ni le fait que le bouclage circulaire est inutilisé quand on fixe initialement la position des n avec n/2 personnes de chaque coté.

Merci d'en avoir bien signalé les manques...

Cela dit
1. Je n'ai jamais prétendu le contraire : j'ai bien précisé au contraire que j'avais essayé de faire simple et didactique en respectant le cahier des charges déposé par freddy : à chaque tour, l'heureux distributeur de coquillages est choisi au "hasard".
Bon, le hasard et les langages de programmation... quoique Python ait évolué depuis ses débuts en la matière.

2. La complétude n'était pas mon propos. Il faut arrêter d'enfoncer les portes ouvertes (sauf s'il s'agit d'asseoir la supériorité d'un code sur l'autre. Vais-je encore oser publier mes insignifiances ?) : j'avais pensé avoir été clair là-dessus !
Quant à l'autre programme qui lui, apparemment, va faire partie des merveilles du monde qui fait tout et plus encore (même si je suis un peu déçu : il ne repeint pas la cuisine à ma place), n'ayant pas été capable, en deux lectures, de voir l'idée qui le sous-tendait, j'ai laissé courir... Voilà qui ajoute une pierre de plus à mon jardin... Ce n'est pas grave, j'ai encore de la place !

3. Freddy n'a pas demandé de montrer que le résultat est indépendant de l'ordre dans lesquel les coquillages sont répartis,

4. Freddy n'a pas demandé le pourquoi de 384,

5. Freddy n'a pas demandé de montrer que le bouclage circulaire est inutilisé quand on fixe initialement la position des n avec n/2 personnes de chaque coté.

Freddy avait dit :

Vingt et une personnes, dont Paul et Virginie, du club Med' de Peysey Nancroix, sont assises autour d'une table circulaire pour participer à un jeu "step by step".
Une étape consiste à choisir au hasard une personne qui a au moins deux coquillages ; celle-ci doit alors donner un coquillage à chacun de ses deux voisins (voisines).
Au départ du jeu, une personne a 20 coquillages, les autres n'ont rien.
A l'issue de 384 étapes, Virginie a deux coquillages de plus que Paul.
Combien ont ils respectivement ?

Moi, j'étudie seulement à chaque relance du programme, une situation due à un tirage (pseudo) aléatoire à chaque tour sur 384 tours.

Par contre, une question de freddy me semble toujours pendante (j'espère ne pas avoir aussi des insuffisances en lecture) :

position 6 heures, le gars qui en a 20.
Il est choisi au hasard 4 fois, il lui en reste donc 12, à sa droite il y en a 4 et à sa gauche autant.
Maintenant, comment poursuit-on ?
Où est passé le tirage aléatoire du petit problème ?

@+ (peut-être)

freddy · 21-09-2011 14:33:18

Salut,

je viens de prendre connaissance des deux derniers échanges.

En effet, la question est bien celle soulevée par le dernier échange : "combien de coquillages ont Paul et Virginie à l'issue de la 384ième étape, sachant que l'un a deux coquillages de plus que l'autre ? "

Aurais je fait une co(q)uille ?

totomm · 22-09-2011 12:26:57

Bonjour,

Dans Accueil Enigmes, casse-têtes, curiosités et autres bizarreries, Voisins / Voisines

freddy #post 1 a écrit :

...., A l'issue de 384 étapes, Virginie a deux coquillages de plus que Paul.
Combien ont ils respectivement ?

totomm #post 2 a écrit :

certainement 2 et 0, et ensuite chacun(e) aura 1 coquillage sauf un(e).

freddy #post 3 a écrit :

Peux tu le prouver ? C'est important de le prouver,…

Alors vous pouvez reprendre vos remarques mal venues…je n'ai fait qu'évoquer la preuve demandée !
.....dont je pensais bien que freddy aurait à coeur de la publier, car

freddy 21/09/2011 09:51:07 a écrit :

Donc, dans tous les cas, on arrive à cette solution.
Je vais tâcher de le démontrer en langage mathématique

Cordialement

Dernière modification par totomm (22-09-2011 12:36:47)

totomm · 22-09-2011 12:36:07

re Bonjour,

yoshi a écrit :

Par contre, une question de freddy me semble toujours pendante (j'espère ne pas avoir aussi des insuffisances en lecture)

J'ai répondu post #14 à cette question posée post #13 dans
Accueil Enigmes, casse-têtes, curiosités et autres bizarreries, Voisins / Voisines
Cordialement

freddy · 23-09-2011 13:00:06

Salut,

puisque nous en sommes à échanger nos codes, voici le mien :

DEFINITION DES VARIABLES ET SORTIES
data A (keep =cpt i table1-table27);array table(27);cpt=0;
INITIALISATION DU VECTEUR TABLE
do p= 1 to 27;
table(p)=0;
end;
table(14)=20;
output; ( écrit le résultat dans le fichier de données A)
REALISATION
do i= 1 to 10000; génére autant de tirages aléatoires selon une loi uniforme que nécessaires
alea=int(ranuni(-1)*27)+1;
if table(alea) >=2 then do;
cpt=cpt+1;
table(alea-1)=table(alea-1)+1;
table(alea)=table(alea)-2;
table(alea+1)=table(alea+1)+1;
output;
end;
if i >= 10 then do;
test=0;
do p=1 to 27;
test=max(0,table(p),test);
end;
if test =1 then i=10000; pour sortir de la boucle en vérifiant que le jeu est terminé
end;
end;

Je pense que la mécanique est conforme à celle du jeu.

Et je vois bien ce qui se passe, mais je n'ai toujours pas démontré pourquoi je suis sûr que ça donnera toujours le même résultat.

Et je trouve fantastique qu'on puisse annoncer que ce sera toujours comme ça sans le démontrer !

Prochaine étape, la démonstration mathématique.

Dernière modification par freddy (23-09-2011 14:29:48)

totomm · 23-09-2011 21:04:46

Bonsoir,

Comparaisons entre le programme VBA de freddy, celui de yoshi et celui de totomm :

Dans le programme "VBA" de freddy, il y a 27 positions et non 21 et pas de rebouclage en cercle, sans doute pour avoir une marge de 3 positions à chaque extrémité.

Le tirage au hasard est fait sur les 27 positions, et réitéré si la position tirée n'a pas au moins 2 coquillages
alors que yoshi tire au hasard sur les seules personnes ayant au moins 2 coquillages. On comprend alors pourquoi les itérations du programme nécessitent chez freddy i de 1 à 10000 et non i de 1 à 384
Comme aucune contrainte n'était données sur la loi à suivre pour les tirages, totomm fixe les tirages successifs(choisis par lui pour démontrer pourquoi 384) tout autant valables que les tirages variables.

Yoshi a pris 384 comme condition d'arrêt (voir l'énoncé de l'énigme), alors que freddy et totomm testent s'il n'y a plus que des 1 (ou des 0) dans chaque position.

Donc maintenant : Prochaine étape annoncée par freddy....

Cordialement

Dernière modification par totomm (23-09-2011 21:05:14)

totomm · 23-09-2011 21:11:02

Bonsoir,

@yoshi : Fred m'avait prévenu de mettre "Code=Python" pour avoir la couleur...

Cordialement

freddy · 23-09-2011 22:28:57

Re,

deux remarques :

- statistiquement, il faut environ 2750 tirages pour arriver à l'étape 385 numérotée par le compteur cpt ; quelle que soit la manière de s'y prendre, c'est toujours le même résultat au bout de 385 étapes. C'est ce point que la démonstration doit établir. C'est ce point qui permet de déduire la réponse à l'étape 384. Et il faut établir pourquoi, malgré le choix aléatoire du joueur concerné.

- ce n'est pas du VBA, mais de la programmation sous SAS.

Le serveur dédié est tellement puissant (il permet de traiter des fichiers de très grosses tailles) que les calculs prennent un temps machine infinitésimal, même si je prévois au maximum 10.000 tirages pour m'assurer que ça s'arrête toujours à l'étape 385.

Bb

Dernière modification par freddy (23-09-2011 22:30:00)

totomm · 25-09-2011 12:12:08

Bonjour,

freddy a écrit :

statistiquement, il faut environ 2750 tirages pour arriver à l'étape 385 numérotée par le compteur cpt

Cette valeur de 2750 est statistiquement tirée de i. D'après votre programme elle serait donc différente si vous preniez une autre valeur que 27 pour votre table et vos tirages. Si vous faisiez vos tirages come yoshi, vous auriez toujours 385 au lieu de 2750.

Le nombre de répartitions différentes des coquillages auquelles on peut arriver (en tirant au hasard) à une étape donnée est au moins de l'ordre de 30000 à chaque étape intermédiaire (entre étapes 150 et 190 par exemple).

i de 1 à 10000 est une bonne sécurité (étant vus les 2750) puisque votre condition d'arrêt est "aucune position n'a plus de 1 coquillage"
Note : Pour être entièrement valable vous devriez écrire :
if (test =1 AND i<10000) then i=10000 else message d'erreur
afin d'être averti si 10000 était insuffisant...

Cordialement.

freddy · 25-09-2011 17:40:29

totomm a écrit :

Bonjour,
freddy a écrit :
statistiquement, il faut environ 2.750 tirages pour arriver à l'étape 385 numérotée par le compteur cpt
Cette valeur de 2.750 est statistiquement tirée de i. D'après votre programme elle serait donc différente si vous preniez une autre valeur que 27 pour votre table et vos tirages. Si vous faisiez vos tirages comme yoshi, vous auriez toujours 385 au lieu de 2750.
Le nombre de répartitions différentes des coquillages auxquelles on peut arriver (en tirant au hasard) à une étape donnée est au moins de l'ordre de 30.000 à chaque étape intermédiaire (entre étapes 150 et 190 par exemple).
i de 1 à 10000 est une bonne sécurité (étant vus les 2750) puisque votre condition d'arrêt est "aucune position n'a plus de 1 coquillage"
Note : Pour être entièrement valable vous devriez écrire :
if (test =1 AND i<10.000) then i=10000 else message d'erreur
afin d'être averti si 10.000 était insuffisant...
Cordialement.

Salut,

si tu peux (et seulement si) me montrer comment tu arrives à 30.000, je me coucherais moins bête ce soir.

Dernière modification par freddy (25-09-2011 17:41:12)

totomm · 25-09-2011 19:51:19

Bonsoir,

J'ai écrit un programme qui mémorise toutes les répartitions possibles à l'étape n en fonction de toutes les répartitions de l'étape (n-1), qui ne garde qu'un exemplaire d'une répartition obtenue plsieurs fois, et qui compte.
(Note : Les configurations symétriques sont conservées). Le fichier des configurations est donc énorme !

Voici quelques lignes de résultats sur le nombre de configurations (pour 2N coquillages) :
N = 10 , Etape = 0 , nbconfigs = 1
N = 10 , Etape = 1 , nbconfigs = 1
N = 10 , Etape = 2 , nbconfigs = 1
N = 10 , Etape = 3 , nbconfigs = 3
N = 10 , Etape = 4 , nbconfigs = 4
N = 10 , Etape = 5 , nbconfigs = 4
N = 10 , Etape = 6 , nbconfigs = 6
N = 10 , Etape = 7 , nbconfigs = 10
N = 10 , Etape = 8 , nbconfigs = 13
N = 10 , Etape = 9 , nbconfigs = 19
N = 10 , Etape = 10 , nbconfigs = 24
......
N = 10 , Etape = 162 , nbconfigs = 32104
N = 10 , Etape = 163 , nbconfigs = 32161
N = 10 , Etape = 164 , nbconfigs = 32203
N = 10 , Etape = 165 , nbconfigs = 32266
N = 10 , Etape = 166 , nbconfigs = 32264
N = 10 , Etape = 167 , nbconfigs = 32251
....
N = 10 , Etape = 377 , nbconfigs = 22
N = 10 , Etape = 378 , nbconfigs = 15
N = 10 , Etape = 379 , nbconfigs = 11
N = 10 , Etape = 380 , nbconfigs = 7
N = 10 , Etape = 381 , nbconfigs = 5
N = 10 , Etape = 382 , nbconfigs = 3
N = 10 , Etape = 383 , nbconfigs = 2
N = 10 , Etape = 384 , nbconfigs = 1
N = 10 , Etape = 385 , nbconfigs = 1

Cordialement

totomm · 26-09-2011 10:35:41

Bonjour,

totomm a écrit :

Note : Pour être entièrement valable vous devriez écrire :
if (test =1 AND i<10000) then i=10000 else message d'erreur
afin d'être averti si 10000 était insuffisant...

Un de mes fils m'a regardé en riant et m'a dit : "ça ne te ressemble pas, ce message d'erreur sortira à chaque passage !"

Au temps pour moi !
Mieux vaut se fier à l'examen des données ou ajouter un message d'avertissement (if i=9999 then...) avant "if test=1 then..."

Je reconnais volontiers que mon intervention cette fois est du genre "mouche du coche" (cette fois seulement :-)
Cordialement

freddy · 26-09-2011 12:26:20

Salut,

dans ma procédure, le traitement s'arrête automatiquement quand la boucle "do" atteint le nombre de 10.000 et écrit le dernier résultat dans le fichier de sortie.

C'est comme ça que je sais qu'elle n'a pas besoin d'aller au delà de 3.000 tirages aléatoires.

De la même manière, je savais d'avance que je n'avais pas besoin d'avoir plus de 10 positions à droite et à gauche de 14, à cause de la démonstration fournie par ailleurs, dans la rubrique "énigme, ...".

Forum de mathématiques - Bibm@th.net

#1 16-09-2011 11:41:34

Voisins, voisines, (code sur énigme freddy)

#2 16-09-2011 15:03:50

Re : Voisins, voisines, (code sur énigme freddy)

#3 20-09-2011 17:53:45

Re : Voisins, voisines, (code sur énigme freddy)

#4 21-09-2011 10:51:07

Re : Voisins, voisines, (code sur énigme freddy)

#5 21-09-2011 11:09:49

Re : Voisins, voisines, (code sur énigme freddy)

#6 21-09-2011 13:03:43

Re : Voisins, voisines, (code sur énigme freddy)

#7 21-09-2011 14:33:18

Re : Voisins, voisines, (code sur énigme freddy)

#8 22-09-2011 12:26:57

Re : Voisins, voisines, (code sur énigme freddy)

#9 22-09-2011 12:36:07

Re : Voisins, voisines, (code sur énigme freddy)

#10 23-09-2011 13:00:06

Re : Voisins, voisines, (code sur énigme freddy)

#11 23-09-2011 21:04:46

Re : Voisins, voisines, (code sur énigme freddy)

#12 23-09-2011 21:11:02

Re : Voisins, voisines, (code sur énigme freddy)

#13 23-09-2011 22:28:57

Re : Voisins, voisines, (code sur énigme freddy)

#14 25-09-2011 12:12:08

Re : Voisins, voisines, (code sur énigme freddy)

#15 25-09-2011 17:40:29

Re : Voisins, voisines, (code sur énigme freddy)

#16 25-09-2011 19:51:19

Re : Voisins, voisines, (code sur énigme freddy)

#17 26-09-2011 10:35:41

Re : Voisins, voisines, (code sur énigme freddy)

#18 26-09-2011 12:26:20

Re : Voisins, voisines, (code sur énigme freddy)

Réponse rapide

Pied de page des forums