Voici le premier défi mathématique de la saison. Il nous est proposé par Adrien, vainqueur de la saison 1.
''Homer travaille dans une centrale nucléaire, il est chargé de la sécurité. Pour cela il a à sa disposition 100000 boutons (numérotés de 1 à 100000). Tous les boutons ont deux positions, une enfoncée (actif) et une ressortie (non actif). Homer s'ennuyant dans la centrale décide de jouer avec sa console.Voici les règles : il passe son doigt sur les boutons (de manière croissante), si il en rencontre un actif il le désactive et vice versa. Il décide de passer son doigt sur la console 100000 fois (il s'ennuie beaucoup!). Initialement tous les boutons sont inactifs.
- Au premier passage il active tous les boutons ;
- Au deuxième, il s'arrête sur un bouton sur deux (en commençant par le deuxième : 2-4-6...) ;
- Au troisième, il s'arrête sur un bouton sur trois (en commençant par le troisième : 3-6-9...) ;
- et ainsi de suite jusqu'à faire ses 100000 passages...''
Défi : combien de boutons seront actifs à la fin de ses 100000 passages ? Le bouton 60025, si il est activé à la fin de son jeu va provoquer la fusion du réacteur, Homer va-t-il provoquer la destruction du monde ?
Proposer vos réponses en commentaires à ce message. Les réponses des PC seront prises en compte mais ne seront publiées qu'un peu plus tard pour laisser une chance aux PCSI.
4 réactions
1 De Foulques Geraud - 08/11/2015, 01:13
J'ai trouvé !
Enfin, je crois...
Observons les boutons au k par k (cas par cas pour ceux qui n'ont pas compris, c'est une blague extrêmement (j'aurais bien aimé souligner ce dernier mot) rigolote) :
Le bouton n°k (rappelons qu'ils sont numérotés à partir de 1) ne subit le doigt d'Homère lors du n-ième passage si et seulement si il est divisible par n : en effet Homer s'arrête tous les n boutons... Aussi les boutons de 1 à n-1 sont épargnés... Puis il touche le n-ième bouton... Les boutons de n+1 à n+n-1 sont épargnés... Il touche donc le bouton 2n, puis 3n... Jusqu'à dépasser 100 000, et alors il s'arrête.
Ainsi, les x passages où Homère s'arrête sur le k-ième bouton sont les x passages où k est divisible par n. Cet ensemble x est l'ensemble des diviseurs de k (ce blog manque vraiment d'un panneau de mise en page, j'aurais aimé souligner le mot "diviseurs" aussi).
Si on réfléchit plus, on sait que le bouton est actif s'il est touché un nombre impair de fois (0=inactif, 1=actif, 2=inactif, 3=actif...) et donc inactif s'il est touché un nombre pair de fois ! Pour connaître l'activité (pas l'activité chimique, M.Ducassou je vous vois venir !) du k-ième bouton à la fin des passages de Homer, il faut donc s'intéresser à la parité du cardinal de x l'ensemble de ses diviseurs.
Or, que remarquons nous ? Que si jamais a est divisible par b, alors a est aussi divisible par a/b ! On devine alors que les cardinal de x sera forcément... Pair ? FAUX ! Car il y a le cas où b=a/b, c'est à dire où le diviseur est la racine carrée de a...
J'introduis ici une parenthèse utile pour l’algorithmique : On vient de comprendre que la moitié des diviseurs d'un nombre se trouvent au-dessous (ou égaux) à sa racine... Ainsi pour les jeunes malandrins qui comme moi utilisaient leur calculatrice au lycée pour faire des programmes de recherche de diviseurs d'un nombre ou de recherche de nombres premiers, il est utile de ne plus chercher les diviseurs du nombre x au-dessous de sa racine, ainsi la recherche est en O(√x) plutôt qu'en O(x), ce qui est tout de même très plus mieux.
Mais revenons à nos boutons (Admirez le jeu de mots =D), si le nombre k a une racine carrée entière, alors il a deux fois sa racine comme diviseur, ce qui compte pour un seul : il a alors un nombre impair de diviseurs. Donc, tout entier a un nombre pair de diviseurs, sauf si sa racine carrée est elle aussi entière.
Dès lors, seuls les boutons ayant un nombre impair de diviseurs seront actifs à la fin du jeu d'Homer. Ce qui nous permet de dire que les numéros des boutons actifs à la fin sont {n ∈ℕ|√n∈ℕ}
Combien y en a-t-il pour 100 000 boutons ? Réfléchissons... Nous cherchons les nombres entiers inférieurs à 100 000 dont la racine soit entière... Soit l'ensemble des entiers dont le carré soit inférieur à 100 000 ! Donc les entiers inférieurs à √100 000 ... or √100 000 ≃ 316,23 ;
Il y a donc 316 boutons actifs à la fin du jeu de Homer Simson.
Pour la seconde partie, la réponse est non, tout simplement parce que la fusion d'un réacteur n'entraîne pas la destruction du monde... Bon, admettons, sachant que cela se passe aux états-unis, Que Kim Jong Un parti à la recherche d'un cerveau passe par-là, son irradiation pouvant déclencher l'ire de ses alliés et donc un conflit mondial... On veut savoir si le bouton n°60 025 est actif, ce qu'on calcule aisément : il suffit de voir si son nombre de diviseurs est pair... Donc de voir s'il est un carré d'entier.
√60 025 = 245.
60 025 a un nombre impair de diviseurs...
TOUS AUX ABRIS !!!
2 De olivier - 09/11/2015, 15:52
316 boutons actifs
Le 60 025 est bien activé, la fusion du réacteur aura lieu.
Notons juste que fusion du réacteur n'est pas forcément égale à destruction du monde. Bien que pénible, cette situation ne devrait garder qu'un impact relativement local SI les bâtiments autour conservent leur intégrité. (Voir Tchenobyl, Three Miles Island, Fukushima) =)
Le code python à tout hasard :
n=100000
boutons=n*1
passage=2
i=1
while(passage<=n):
while(i*passage<=n): if boutons[i*passage-1]==1: boutons[i*passage-1]=0 elif boutons[i*passage-1]==0: boutons[i*passage-1]=1 i=i+1 i=1 passage=passage+1
boutons.count(1)
boutons60024
3 De Jean-Baptiste Chagnoleau - 09/11/2015, 19:51
A l'aide d'un algorithme je trouve que 316 boutons seront activés à la fin. Le bouton 60025 sera activé.
4 De Romain Validire - 10/11/2015, 20:08
Le jury s'est réuni en conclave aujourd'hui et après une longue délibération a décidé d'attibuer 1 point à Foulques et 1 point à Jean-Baptiste.
Félicitations à tous les deux !!! Rendez-vous au prochain défi.
Quant à ce mystérieux Olivier, il faut nous en méfier car il résout très souvent les défis...
PS pour Foulques : comme indiqué un peu au-dessous, vous pouvez utiliser une syntaxe wiki simplifiée pour la mise en forme de vos commentaires. Par exemple :
__gras__ et ''italique''