{"id":1648,"date":"2013-05-09T10:00:20","date_gmt":"2013-05-09T08:00:20","guid":{"rendered":"http:\/\/nicotupe.fr\/Blog\/?p=1648"},"modified":"2013-06-17T10:16:45","modified_gmt":"2013-06-17T08:16:45","slug":"ma-candidature-a-42-epreuve-5","status":"publish","type":"post","link":"http:\/\/nicotupe.fr\/Blog\/2013\/05\/ma-candidature-a-42-epreuve-5\/","title":{"rendered":"Ma candidature \u00e0 42 : Epreuve 5"},"content":{"rendered":"


\n<\/a>Xavier Niel fanfaronne et annonce la cr\u00e9ation d’une \u00e9cole, au doux nom de la r\u00e9ponse \u00e0 la question de l’univers et tout le reste : 42. Il n’en fallait pas plus pour m’attirer, alors…<\/p>\n

Le premier jour, je me suis inscrit.<\/a><\/p>\n

Le deuxi\u00e8me jour j’ai fait les 3 premi\u00e8res \u00e9valuations.<\/a><\/p>\n

Le troisi\u00e8me jour, j’ai fait la 4\u00e8me \u00e9valuation.<\/a><\/p>\n

La validation de la quatri\u00e8me \u00e9preuve d\u00e9bloquait la toute derni\u00e8re \u00e9valuation. Cette \u00e9valuation est de loin la plus int\u00e9ressante a mon go\u00fbt. Il est annonc\u00e9 qu’elle dure deux heures.<\/p>\n

Rencontre<\/h1>\n

Comme la plupart des \u00e9preuves, on arrive sur un \u00e9cran sans aucune instructions mais ici la r\u00e8gle se r\u00e9v\u00e8le tr\u00e8s simple.<\/p>\n

\"Capture_d'\u00e9cran_19_04_13_11_00\"<\/a><\/p>\n

On a un curseur, on le controle avec les fl\u00e8ches. A chaque fois qu’il passe sur une case, il l’a d\u00e9truit. Le but est de d\u00e9truire toutes les cases.<\/p>\n

Les game-designer de cette \u00e9preuve se sont encore \u00e9clat\u00e9s et tr\u00e8s vite \u00e7a se corse (du moins visuellement).<\/p>\n

\"Capture_d'\u00e9cran_19_04_13_11_06\"<\/a><\/p>\n

\"Capture_d'\u00e9cran_19_04_13_11_12\"<\/a><\/p>\n

 <\/p>\n

En fait, ce n’est pas si difficile. En s’y reprenant \u00e0 deux trois fois, on viens toujours au bout, du moins presque, comme on va rapidement le voir mais d’abord un peu de math!<\/p>\n

Les ponts de K\u00f6nigsberg<\/h1>\n

Ce probl\u00e8me est en fait extr\u00eamement classique en th\u00e9orie des graphes : il s’agit de parcourir toutes les connexions une et une seule fois.<\/p>\n

Tout commence \u00e0 K\u00f6nigsberg, une ville constitu\u00e9e de 7 ponts. L\u00e9onard Euler, en visite dans cette ville se demande s’il est possible de passer par les 7 ponts \u00a0en ne parcourant chaque pont qu’une seule fois. N’h\u00e9sitez pas \u00e0 vous y essayer sur la carte de la ville ci-dessous.<\/p>\n

\"\"<\/p>\n

(Image Wikimedia)<\/p>\n

Ce probl\u00e8me parait tout simple et pourtant, je vous offre tout simplement une bouteille de champagne si vous le\u00a0r\u00e9ussissez (ne pariez jamais avec un math\u00e9maticien).<\/p>\n

En th\u00e9orie des graphe, on repr\u00e9senterai la ville de la sorte :<\/p>\n

\"Untitled\"<\/a><\/p>\n

 <\/p>\n

Chaque rond orang\u00e9 repr\u00e9sente une partie de la ville et les traits noirs les 7 ponts de la ville. Euler voulait parcourir la ville sans revenir sur ses pas et quoi qu’on puisse dire, son parcours aura un d\u00e9but et une fin (propri\u00e9t\u00e9 extr\u00eamement importante).<\/p>\n

Mais oublions pour le moment cette histoire de d\u00e9but et de fin et pla\u00e7ons nous au milieu du parcours. A chaque fois qu’Euler arrive dans une des parties de la ville (les cercles oranges), il proviens d’un pont et se dirige vers un autre pont. Ainsi, si les morceaux de ville sont au milieu du parcours, il y aura un nombre pairs de ponts qui seront parcourus autour d’eux (celui dont on viens et celui o\u00f9 on va, plusieurs fois si l’on passe plusieurs fois par ce morceau de ville).<\/p>\n

Au d\u00e9part et \u00e0 l’arriv\u00e9e par contre c’est diff\u00e9rent. A l’arriv\u00e9e, on proviens d’un pont mais on s’arr\u00eate, on ne\u00a0parcourra\u00a0plus de ponts. De ce fait, le nombre de ponts parcourus autour de ce morceau de ville sera impair : Le nombre pairs de ponts parcourus dans un morceau de ville au milieu de parcours plus le pont final. Au d\u00e9part, m\u00eame chose, un nombre impair de pont parcourus : celui de d\u00e9marrage et ceux du milieu du parcours.<\/p>\n

Revenons en \u00e0 notre propri\u00e9t\u00e9 fondamentale d’un parcours : Il n’y a qu’un d\u00e9part et une arriv\u00e9e. De ce fait, il ne peut y avoir qu’exactement deux morceau de ville autour desquels il y a un nombre impair de ponts, on ne peut donc pas parcourir les 7 ponts de K\u00f6nigsberg sur un seul parcours en ne passant qu’une fois sur chaque pont!<\/p>\n

Remarquez qu’on peut aussi r\u00e9ussir ce type de parcours si tous les points ont un nombre pair de liaisons entre eux, il suffit que le d\u00e9part et l’arriv\u00e9e soient au m\u00eame endroit.<\/p>\n

Un probl\u00e8me insoluble<\/h1>\n

La d\u00e9monstration ci-dessus permet de trouver des cas impossibles (mais en aucun cas de prouver que les autres cas sont possible m\u00eame si dans les faits, il le sont). Et justement, le dernier niveau de l’\u00e9valuation de 42 est celui ci (le d\u00e9but est impos\u00e9, il est l\u00e0 ou est la fl\u00e8che noire) :<\/p>\n

\"Capture_d'\u00e9cran_19_04_13_11_18-2\"<\/a><\/p>\n

Vous reconnaissez le cas similaire aux ponts de\u00a0K\u00f6nigsberg? On a sur cette figure deux points avec un nombre impair de liaison dont aucune n’est le d\u00e9part :<\/p>\n

\"Capture_d'\u00e9cran_19_04_13_11_18\"<\/a><\/p>\n

 <\/p>\n

L’exercice est donc impossible! Impossible du moins dans le monde de la rigueur et des r\u00e8gles respect\u00e9es qu’est le monde math\u00e9matique mais qu’en est-il en informatique?<\/p>\n

Become a hacker<\/h1>\n

A ce stade de l’\u00e9preuve, j’avais commenc\u00e9 depuis 20 minutes environ et il me restait donc th\u00e9oriquement 1H40 d’\u00e9preuve. Connaissant la joyeuse ville aux 7 ponts, j’ai rapidement compris que la chose est impossible.<\/p>\n

Me voila donc un peu perplexe 80 minutes encore devant une \u00e9preuve impossible. Il y avait deux possibilit\u00e9s en fait :<\/p>\n