Énigme combinatoire

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
TheReveller
Membre Relatif
Messages: 114
Enregistré le: 14 Nov 2006, 06:21

Énigme combinatoire

par TheReveller » 06 Avr 2012, 18:52

Bonjour,

Je viens de regarder cette énigme : http://shkdee.info/fichiers/EnigmeCombinatoire.pdf

J'ai ensuite réalisé rapidement un petit algorithme simple pour faire des tests, mais les résultats me semblent incohérents.

Pourriez-vous me dire où je me trompe dans l'algorithme ou bien pourquoi l'algorithme converge aussi rapidement ?

Dans mon algorithme, la première partie consiste à ce que chacune des 500 personnes passe en revue 250 casiers aléatoirement. S'ils trouvent tous leur numéro, alors c'est gagné. Normalement, chaque personne devrait avoir une chance sur deux de trouver leur numéro et donc la probabilité que tous les gens aient trouvé leur numéro serait de (1/2)^500, soit 3x10^-151. Or, mon algorithme converge en une dizaine d'itérations !

Dans la deuxième partie, j'ai voulu implémenter la technique suggérée et là je converge souvent en une seule itération et très souvent en trois itérations ou moins !

Voici le code MATLAB :

Code: Tout sélectionner
close all;
clear all;
clc;

n = 500; % Nombre de personnes
maxit = 100; % Nombre maximal d'itérations

win = 0; % 0 : Partie non gagnée
trouve = zeros([1,n]); % Initialisation, tout à zéro (non trouvé)
it = 1; % Initialisation du compte d'itérations

while win == 0 && it <= maxit
    gens = randperm(n); % Les numéros des gens
    casiers = randperm(n); % Les numéros dans les casiers
    for i=1:n % Pour chaque personne
        j = 1; % Initialisation à la première visite d'un casier
        next = randperm(n); % Les casiers que visitera la personne
        while j <= n/2 && trouve(i) == 0 % Visitera au plus la moitié
            if casiers(next(j)) == gens(i)
                % Numéro dans le casier correspond au numéro de la personne
                trouve(i) = 1; % La personne a trouvé son numéro
            end
            j = j + 1; % Prochain casier
        end
    end
    if all(trouve) % Toutes les personnes ont trouvé leur numéro
        win = 1; % 1 : Partie gagnée
    else
        it = it + 1; % Prochaine itération
    end
end

if it <= maxit
    disp(['Aléatoire : Trouvé en ',num2str(it),' itérations']);
else
    disp(['Aléatoire : Non trouvé en ',num2str(maxit),' itérations']);
end

win = 0; % 0 : Partie non gagnée
trouve = zeros([1,n]); % Initialisation, tout à zéro (non trouvé)
it = 1; % Initialisation du compte d'itérations

while win == 0 && it <= maxit
    gens = randperm(n); % Les numéros des gens
    casiers = randperm(n); % Les numéros dans les casiers
    for i=1:n % Pour chaque personne
        j = 1; % Initialisation à la première visite d'un casier
        % La personne va au numéro de casier correspondant à son numéro
        next = gens(i);
        while j <= n/2 && trouve(i) == 0
            if casiers(next) == gens(i)
                % Numéro dans le casier correspond au numéro de la personne
                trouve(i) = 1; % La personne a trouvé son numéro
            else
                % Le prochain numéro de casier est celui qui était contenu
                % dans le casier actuel
                next = casiers(next);
            end
            j = j + 1; % Prochain casier
        end
    end
    if all(trouve) % Toutes les personnes ont trouvé leur numéro
        win = 1; % 1 : Partie gagnée
    else
        it = it + 1; % Prochaine itération
    end
end

if it <= maxit
    disp(['Cyclique : Trouvé en ',num2str(it),' itérations']);
else
    disp(['Cyclique : Non trouvé en ',num2str(maxit),' itérations']);
end

clear all;


À propos des fonctions de MATLAB : http://www.mathworks.com/help/techdoc/

Merci !



TheReveller
Membre Relatif
Messages: 114
Enregistré le: 14 Nov 2006, 06:21

par TheReveller » 08 Avr 2012, 02:27

Personne ne s'intéresse à cette intrigue ?

TheReveller
Membre Relatif
Messages: 114
Enregistré le: 14 Nov 2006, 06:21

par TheReveller » 10 Avr 2012, 08:12

J'ai trouvé mon erreur, elle était toute bête. J'oubliais de réinitialiser ma variable trouve à chaque nouvelle itération.

L'algorithme est donc :

Code: Tout sélectionner
close all;
clear all;
clc;

n = 500; % Nombre de personnes
maxit = 25; % Nombre maximal d'itérations

win = 0; % 0 : Partie non gagnée
trouve = zeros([1,n]); % Initialisation, tout à zéro (non trouvé)
it = 1; % Initialisation du compte d'itérations

while win == 0 && it <= maxit
    gens = randperm(n); % Les numéros des gens
    casiers = randperm(n); % Les numéros dans les casiers
    for i=1:n % Pour chaque personne
        j = 1; % Initialisation à la première visite d'un casier
        next = randperm(n); % Les casiers que visitera la personne
        while j <= n/2 && trouve(i) == 0 % Visitera au plus la moitié
            if casiers(next(j)) == gens(i)
                % Numéro dans le casier correspond au numéro de la personne
                trouve(i) = 1; % La personne a trouvé son numéro
            end
            j = j + 1; % Prochain casier
        end
    end
    if all(trouve) % Toutes les personnes ont trouvé leur numéro
        win = 1; % 1 : Partie gagnée
    else
        it = it + 1; % Prochaine itération
        trouve = zeros([1,n]); % Réinitialisation
    end
end

if it <= maxit
    disp(['Aléatoire : Trouvé en ',num2str(it),' itérations']);
else
    disp(['Aléatoire : Non trouvé en ',num2str(maxit),' itérations']);
end

win = 0; % 0 : Partie non gagnée
trouve = zeros([1,n]); % Initialisation, tout à zéro (non trouvé)
it = 1; % Initialisation du compte d'itérations

while win == 0 && it <= maxit
    gens = randperm(n); % Les numéros des gens
    casiers = randperm(n); % Les numéros dans les casiers
    for i=1:n % Pour chaque personne
        j = 1; % Initialisation à la première visite d'un casier
        % La personne va au numéro de casier correspondant à son numéro
        next = gens(i);
        while j <= n/2 && trouve(i) == 0
            if casiers(next) == gens(i)
                % Numéro dans le casier correspond au numéro de la personne
                trouve(i) = 1; % La personne a trouvé son numéro
            else
                % Le prochain numéro de casier est celui qui était contenu
                % dans le casier actuel
                next = casiers(next);
            end
            j = j + 1; % Prochain casier
        end
    end
    if all(trouve) % Toutes les personnes ont trouvé leur numéro
        win = 1; % 1 : Partie gagnée
    else
        it = it + 1; % Prochaine itération
        trouve = zeros([1,n]); % Réinitialisation
    end
end

if it <= maxit
    disp(['Cyclique : Trouvé en ',num2str(it),' itérations']);
else
    disp(['Cyclique : Non trouvé en ',num2str(maxit),' itérations']);
end

clear all;


Pour ceux qui aiment les problèmes de combinatoire, j'ai trouvé cette enigme fort intéressante.

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 8 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite