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 !