Uncategorized

Sous la douche

Sous la douche, je pense à des trucs bizarres.

Imaginez un grand chateau carré, de n pièces de côté, pièces disposées en quadrillage. Toutes les pièces ont quatre portes, une à l’ouest, une au sud, une à l’est et une au nord qui les relient entre elles. Sauf bien sûr celles qui sont sur les bords et qui n’ont que trois issues, et celles dans les coins (donjons) qui n’en ont que deux. A l’exception des donjons Sud-Est et Nord-Est qui ont une sortie vers l’exterieur.

Un prince est emprisonné dans le donjon Nord-Ouest. Il possède une clé qui ouvre une porte sur deux dans le chateau. On ne sait pas lesquelles, mais on sait que exactement la moitié des portes le laisseront passer et que l’autre moitié le bloqueront. Et on sait qu’il existe forcément un chemin pour aller du cachot où est le prince jusqu’à chacune des sorties. On ajoute que le Prince n’a pas le droit de passer deux fois par la même pièce : si il se retrouve bloqué, il est renvoyé à son point de départ.

Ma question est : combien y a-t-il, en moyenne, de chemins pour s’échapper ? Combien au maximum ? Et si le chateau n’est plus un carré mais un cube ? Et si en plus chaque pièce contient une série de téléporteurs permettant de circuler d’une pièce distante à l’autre du chateau (fonctionnant toujours avec la clé) ? Et si au lieu de une porte/téléporteur sur deux ouverts par la clé, on passe à deux sur trois ? un sur trois ?

Standard

3 thoughts on “Sous la douche

  1. Ju(...) says:

    En fait non, c’est en rapport avec le calcul de l’efficacité d’un programme que j’ai écrit et qui fait exactement ça, sauf que lui il essaie tous les chemins possibles. Le problème c’est que je suis dans le dernier cas et que je ne sais pas combien il va en prendre. J’espère juste que c’est pas trop grand… sinon mes utilisateurs vont gueuler un peu :-)

Comments are closed.