Pouvez-vous réussir ce test d’entretien d’embauche en finance ?

Le joli casse-tête de cette semaine a été porté à mon attention par l’un de nos lecteurs, Nicolas Audet. Nicolas dit que cela a été utilisé comme casse-tête pour un entretien d’embauche en finance. Je dois le confier à Wall Street sur ce point : c’est un délicieux petit casse-tête. Merci pour le partage, Nicolas!

C’est une excellente occasion de vous rappeler que si vous connaissez un puzzle sympa, original ou autre, envoyez-le-moi et il sera peut-être présenté ici. Vous ne savez pas si votre puzzle est approprié pour cette série ? Essayez-moi et je vous le ferai savoir. Vous pouvez m’envoyer un message sur Twitter @JackPMurtagh ou envoyez-moi un e-mail à gizmodopuzzle@gmail.com

Vous avez raté le puzzle de la semaine dernière ? Vérifiez-le ici, et trouvez sa solution au bas de l’article d’aujourd’hui. Attention à ne pas lire trop loin si vous n’avez pas encore résolu celui de la semaine dernière !

Puzzle #18 La Longue Salle

Il y a un couloir avec 100 portes étiquetées 1, 2, 3, etc. jusqu’à 100 dans l’ordre. Au début, toutes les portes sont fermées. Par basculer une porte, je veux dire changer sa position (c’est-à-dire l’ouvrir si elle est fermée et la fermer si elle est ouverte). Vous marchez dans le couloir et actionnez toutes les portes (dans ce cas, vous les ouvrez toutes). Ensuite, une deuxième personne entre et bascule toutes les 2 portes (portes 2, 4, 6, etc.). Ensuite, une troisième personne bascule toutes les 3 portes (3, 6, 9, etc.). Cela continue jusqu’à ce que la 100ème personne ne bascule que la 100ème. porte. Quelles portes sont ouvertes à la fin ?

Vous pouvez bien sûr résoudre ce problème en forçant brutalement une simulation du couloir et en observant simplement quelles portes finissent par s’ouvrir. Il sera bien plus satisfaisant de réfléchir au problème et de découvrir les raison qu’une porte finisse par s’ouvrir ou se fermer.

Nous reviendrons lundi prochain avec la solution et une nouvelle énigme.

Solution à l’énigme n°17 : Empoisonner des zombies

La semaine dernière, vous sacrifié les morts-vivants pour sauver votre clan de la soif. Pour identifier le baril empoisonné sur 1 000 en une journée, il suffit étonnamment de 10 zombies. Vous nourrirez les zombies avec des gouttes d’eau provenant de plusieurs barils et garderez une trace des barils que vous nourrissez à quels zombies. L’idée clé est d’attribuer à chaque baril un groupe unique de zombies pour y goûter. Pour avoir une idée de comment cela fonctionne, imaginons que nous n’ayons que quatre barils 1, 2, 3, 4 et deux zombies A et B. Nous ne nourrissons aucun des zombies du baril 1 ; nous alimentons le baril 2 uniquement au zombie A ; baril 3 vers le zombie B uniquement ; et baril 4 aux deux zombies. Ensuite, nous observons qui meurt. Si aucun des deux ne meurt, alors le baril 1 est le coupable. Si seul A meurt, le baril 2 est le coupable, et ainsi de suite. Le sous-ensemble de zombies qui meurt est une empreinte digitale unique liée à un baril spécifique.

Notez que deux zombies ne suffiraient pas si nous avions cinq barils, car il n’y a que quatre sous-ensembles uniques qui peuvent être formés à partir de deux zombies. Pour étendre la méthode, la question devient : combien de sous-groupes uniques pouvez-vous former à partir de 10 zombies ? La réponse est 2^dix, soit 1 024, plus que suffisant pour tester les 1 000 barils. Si 2^dix est nouveau pour vous, pensez encore une fois à moins de zombies pour plus d’intuition. Avec un seul zombie, il y a deux groupes possibles (2 = 2¹), à savoir le zombie lui-même et pas de zombie du tout. Avec deux zombies, nous avons vu que nous obtenions quatre sous-ensembles possibles (4 = 2²). Chaque zombie a deux états possibles : dans le groupe ou non dans le groupe, donc chaque zombie supplémentaire double le nombre de groupes possibles que nous pouvons former.

La solution sous forme d’œuvres écrites. Mais si vous souhaitez une manière systématique et astucieuse d’attribuer un groupe unique de zombies à chaque baril, vous pouvez utiliser des nombres binaires.

Numérotez les barils de 0 à 999, puis convertissez chaque numéro de baril en binaire. Les 1 dans la représentation binaire de chaque numéro de baril nous indiqueront quels zombies nourrir dans ce baril, et les 0 nous diront quels zombies ignorer pour ce baril. Ainsi par exemple, 771 en binaire vaut 1100000011. Faites correspondre cette séquence de 10 chiffres aux 10 zombies. En alignant les zombies d’affilée, nous alimenterons le baril 771 uniquement sur les deux premiers et les deux derniers (correspondant à ceux de la représentation binaire de 771). Si, par exemple, seuls les 3ème et 5ème zombies à gauche meurent, alors nous savons que le baril 0010100000 = 160 est le coupable.

Bravo à Eugène pour repérer la solution des nombres binaires et bien l’expliquer.

Solution à l’énigme n°17b

Avoir deux jours pour exécuter des tests augmente la complexité. Pour trouver le tonneau contaminé parmi les 2 000, il suffit de sept zombies ! Nous emprunterons notre astuce des nombres binaires au premier casse-tête. Cette fois cependant, pour chaque baril, chaque zombie a trois actions possibles : n’en buvez pas, n’en buvez pas le jour 1 ou n’en buvez pas le jour 2. Nous attribuerons donc à chaque baril une étiquette unique à 7 chiffres composée de 0, de 1 et de 2. Encore une fois, imaginez que nous ayons deux zombies A et B. Lorsque nous n’avions qu’une seule journée pour effectuer des tests, nous ne pouvions gérer que quatre barils avec deux zombies. Avec deux jours, nous pourrons en tester neuf. Voici nos neuf étiquettes de fûts :

00, 01, 02, 10, 11, 12, 20, 21, 22

Le zombie A boira selon les chiffres les plus à gauche, ce qui signifie qu’il ne boira pas du tout dans les trois premiers barils, il boira dans les trois suivants le jour 1 et les trois derniers le jour 2. Le zombie B boira selon le chiffre le plus à gauche. chiffres les plus à droite. Notez que le zombie A peut mourir après le premier jour et ne jamais atteindre le jour 2. Mais ce n’est pas grave ! Parce que si A meurt dès le premier jour, alors nous savons que seuls les barils 10, 11 et 12 pourraient être le coupable (A n’a pas bu dans les barils commençant par 0 ou 2 le jour 1). Nous n’avons donc plus besoin de tester les barils dont A était responsable le jour 2. Si B ne meurt jamais, alors 10 est le coupable, si B meurt après le jour 1, alors 11 est le coupable, et si B meurt après le jour 2, alors 12 est le coupable.

Ce phénomène s’amplifie. Si le nième zombie meurt après le jour 1, cela signifie que le nième chiffre de l’étiquette du baril empoisonné est un 1. Si le nième chiffre du zombie meurt après le jour 2, alors le nième chiffre est un 2. Si le nième zombie ne meurt jamais, le Le nième chiffre est un 0. En observant quels zombies meurent quels jours, nous pouvons reconstituer l’étiquette.

Encore une fois, cela se réduit à la question suivante : combien d’étiquettes uniques à 7 chiffres (correspondant à sept zombies) composées de 0, de 1 et de 2 pouvons-nous créer ? Ceux-ci sont appelés ternaire nombres car ils utilisent trois chiffres différents (0, 1 et 2), tout comme les nombres binaires en utilisent deux (0 et 1). Il y a 3⁷ = 2187 étiquettes à 7 chiffres, largement suffisantes pour tester 2000 fûts.

Eugène a également résolu la partie b de manière instructive, sans utiliser l’approche des nombres ternaires et en découvrant par inadvertance cette solution intéressante identité combinatoire.