Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 231

Des enfants et des interrupteurs

Bonjour à tous,

Je ressors du placard un sujet que j'avais trouvé (en 2016) sur un forum dédié à la programmation Python.
(Pour faire plaisir tout particulièrement à ceux qui,  suite à la proposition de Bridgslam, n'arrivent pas s'empêcher de cligner de l’œil en cadence...)
---------------------------------------------------

Devoir de vacances en Python  (classe : Terminale S option ISN) :

276 lampes sont numérotées de 1 à 276. Pour passer le temps, 25 enfants appuient sur les interrupteurs à tour de rôle. Le premier enfant presse chaque interrupteur. Le second presse les boutons 2,4,6, etc, (il presse les interrupteurs ayant un numéro multiple de 2). Le troisième appuie sur les interrupteurs 3, 6, 9, etc, (multiples de 3). Le quatrième presse tous les interrupteurs ayant un numéro multiples de 4, et ainsi de suite jusqu'au 25ème enfant. Avant le passage du premier enfant, toutes les ampoules sont éteintes.
Combien d'ampoules seront allumées après le passage des 25 enfants ?

(J'ajoute un pt'it quelque chose à la question) Et lesquelles ?

-------------------------------------------------------

Mais, (et je pense aux non-programmeurs), ne serait-il pas intéressant également de proposer une solution arithmétique ?
(Je ne pense pas qu'il soit nécessaire d'interpeller une IA pour la version Python...)

@+

[EDIT]
Afin d'éviter de tuer tout suspense, Fred avait (ça date !) beaucoup travaillé pour ajouter une balise. Voici ce qu'il en disait :

J'ai ajouté au forum une nouvelle balise, la balise [ spoiler]  [ /spoiler] (sans les espaces).
Elle permet de donner la solution à une énigme, sans il faudra cliquer sur un bouton pour obtenir la solution.
Par exemple :

▼Texte caché

Voici la solution de l'énigme

Il est possible de changer ce qui est affiché sur le bouton. Par exemple [ spoiler=Indication] donnera...

▼Indication

Voici une indication pour résoudre l'énigme

Dernière modification par yoshi (05-01-2025 21:31:01)

---

Arx Tarpeia Capitoli proxima...

Ernst

Membre

Inscription : 30-01-2024

Messages : 191

Re : Des enfants et des interrupteurs

Bonsoir,

Problème amusant, merci de l’avoir proposé.

Pour ma part, j’ai choisi de faire cette simulation en html + javascript plutôt qu’en Python, histoire de pouvoir tourner dans n’importe quel navigateur.

▼simulation

Ceux qui préfèrent chercher par eux-même la logique du truc peuvent encore attendre avant d’aller sur cette page. Une fois sur celle-ci, il suffira de cliquer « départ » pour obtenir le résultat et le nombre de fois que chaque lampe aura été manipulée.

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 581

Re : Des enfants et des interrupteurs

Bonjour,

▼une méthode ?

En numérotant les lampes de 1 à 276:
Si on s'intéresse aux lampes allumées, cela revient à chercher les $n , 1 \le n \le 276 $ dont l'ensemble des diviseurs d $ d \le 25$ est de cardinal impair.
Par exemple 276 sera bien allumée, avec 7 actions d'interrupteur ( ses diviseurs inférieurs ou égaux à 25 sont 1,2,3,4,6,12,23).
Les nombres premiers jusqu'à 23 seront éteints ( 2 actions), les autres premiers subissant une seule action seront allumés.

Il y a peut-être une astuce arithmétique pour effectuer le dénombrement de lampes allumées ou éteintes (que je ne vois pas présentement).
Dans l'absolu les entiers ayant un nombre impair de diviseurs sont les carrés, mais ici la contrainte de majoration par 25 des diviseurs complique la chose.

Dans notre affaire on peut néanmoins simplifier la recherche en séparant en deux les cas:

- on fait le tri parmi les nombres $\le 276$ dont le plus grand facteur premier est au plus 23, en regardant leurs diviseurs selon leur décomposition en produit de facteurs premiers.
Il faut considérer la liste suivante:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 81, 84, 85, 88, 90, 91, 92, 95, 96, 98, 99, 100, 102, 104, 105, 108, 110, 112, 114, 115, 117, 119, 120, 121, 125, 126, 128, 130, 132, 133, 135, 136, 138, 140, 143, 144, 150, 152, 153, 154, 156, 160, 161, 162, 165, 168, 169, 170, 171, 175, 176, 180, 182, 184, 186, 187, 189, 190, 192, 195, 196, 198, 200, 204, 207, 208, 209, 210, 216, 220, 224, 225, 228, 230, 231, 234, 238, 240, 242, 243, 245, 247, 250, 252, 253, 255, 256, 260, 264, 266, 270, 272, 273, 275, 276.

- pour les autres, après division par tous leurs facteurs premiers au moins égaux à 29, la question se ramène au tri précédent (plus facile).

Par exemple pour $261 = 3^2 \times 29 $ , comme 9 est allumé (cas traité par le tri précédent) on est sûr que 261 aussi...
Le cas de $254 = 2 \times 127$ se ramène au cas de 2, donc 254 est éteint etc

Informatiquement la méthode ci-dessus n'est pas forcément très efficace, mais si on s'appuie sur des subroutines arithmétiques rapides préexistantes, le code doit être assez compact, en évitant d'écrire des boucles qui parcourent plusieurs fois le même tableau.
Enfin elle donne un critère pour dire directement avec  E enfants et une lampe n° L si elle sera allumée ou éteinte, sans lancer forcément la grosse artillerie.
Pouvez-vous dire avec E = 35 et L = 513 si L est allumée ou éteinte ?

▼réponse

.
$L = 3^3 \times 19$ les diviseurs de L ne dépassant pas 35 sont 1,3,9,19,27 (quantité impaire)
$L$ est donc allumée.

Bonne journée
A.

Dernière modification par bridgslam (06-01-2025 19:16:31)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Ernst

Membre

Inscription : 30-01-2024

Messages : 191

Re : Des enfants et des interrupteurs

Bonsoir,

Voici un raisonnement :
- avec un seul enfant, les lampes sont toutes allumées
- le deuxième en éteint exactement la moitié, il en reste donc la moitié d’allumées
- le troisième modifie une lampe sur trois, un tiers des lampes allumées et un tiers des lampes éteintes, ce qui s’annule bien sûr
- le quatrième modifie une lampe sur quatre aussi bien dans le groupe d’allumées que dans le groupe des lampes éteintes, ces groupes étant identiques, là encore cela ne change rien
- etc.

À l'arrivée, on devrait donc avoir la moitié des lampes allumées pour peu que leur nombre soit grand devant celui des enfants.

▼simulation

Avec cent millions de lampes :

 1 : 100 000 000
 2 :  50 000 000
 3 :  49 999 999
 4 :  58 333 333
 5 :  54 999 997
 6 :  54 999 999
 7 :  53 571 427
 8 :  48 214 287
 9 :  51 785 714
10 :  49 007 938
etc.

Aïe. On peut admettre un effet de bord, mais pas dans de telles proportions surtout avec si peu d’enfants. Problème compliqué donc, qui invalide un raisonnement pourtant pas si illogique que cela vu des répartitions parfaitement uniformes...

Ernst

Membre

Inscription : 30-01-2024

Messages : 191

Re : Des enfants et des interrupteurs

Bonjour,

Bon, je me suis amusé avec d’autres valeurs que celle du problème présenté, mais au bout d’un moment un affichage uniquement numérique n’est pas pratique, on se perd un peu dans la ribambelle de chiffres.

▼variations

Je suis donc passé à l’affichage graphique qui permet une vision plus globale. Celui-ci permet de :
- visualiser les évolutions
- obtenir les valeurs en y mettant la souris
- zoomer en traçant un cadre autour des valeurs qui nous intéressent
- changer le nombre de lampes et d’enfants

Les curieux s’amuseront à essayer d’en tirer des règles générales. Moi j’aime bien ce genre de récréation, merci Yoshi.

(ah oui, pour ce qui est de mon raisonnement précédent, il est évident que les multiples de 4 par exemple ne cibleront aucun nombre impair, donc raisonner en terme d'équi-répartition n'est pas valide)

Ernst

Membre

Inscription : 30-01-2024

Messages : 191

Re : Des enfants et des interrupteurs

Bonsoir,

J’avais dit qu’il y a avait peut-être des choses à découvrir, quelques pistes :

▼exemples

Ici j’ai pris 10 000 lampes, mais ça marchera tout aussi bien avec 1 000… En fait la structure reste similaire et dépend essentiellement du ratio nombre de lampes / nombre d’enfants. Au début, un creux :

Ensuite une remontée progressive qui dépasse la moitié des lampes :

Redescente ensuite et à partir du quart, stabilisation horizontale sur cette moitié :

Quand le nombre d’enfants est supérieur à la moitié du nombre de lampes, descente rectiligne :

Et au-delà, stabilisation avec un résidu continu :

En agrandissant certains parties, on peut observer des fluctuations très irrégulières, d’autres fois des progressions quasiment linéaires qui forment un profil de ligne brisée, des segments de droite qui se succèdent. L’avantage du zoom non proportionnel permet d’amplifier la chose, ici avec 100 000 lampes et 26 000 enfants pas moins :

Devoir de vacances hein...

renéb

Membre

Inscription : 16-01-2023

Messages : 30

Re : Des enfants et des interrupteurs

Bonjour,

voici un programme en Python capable, me semble-t-il, de résoudre l'énigme proposée .

On peut y changer le nombre d'interrupteurs et le nombre d'enfants.

a,b,c,d,e,f,g=0,0,0,0,0,0,0
A,B,C,D=[],[],[],[0]
E=5                                 #Nbre d'élèves
I=76                                #Nbre d'interrupteurs
B=([0])*I
C.append(B)
for u in range(1,E+1,1):
    B=([0])*I
    for t in range(u-1,I,u):        
        B[t]=1
    C.append(B)
for w in range(0,I,1):
    for v in range(0,E+1,1):
        b+=C[v][w]
        c+=1
    D.append(b)
for d in range(1,I+1,1):
    e=D[d]-D[(d-1)]
    f+=1
    if e%2!=0:
        g+=1        
        print("lampes allumées en position:",f,"/",I,"interrupteurs")
print(g,"lampes allumées")      
 

Résultats pour 25 enfants et 275 interrupteurs:

153 lampes allumées
lampes allumées en position: 1 / 275 interrupteurs
lampes allumées en position: 4 / 275 interrupteurs
lampes allumées en position: 9 / 275 interrupteurs
lampes allumées en position: 16 / 275 interrupteurs
lampes allumées en position: 25 / 275 interrupteurs
lampes allumées en position: 26 / 275 interrupteurs
lampes allumées en position: 27 / 275 interrupteurs
lampes allumées en position: 28 / 275 interrupteurs
lampes allumées en position: 29 / 275 interrupteurs
lampes allumées en position: 30 / 275 interrupteurs
lampes allumées en position: 31 / 275 interrupteurs
lampes allumées en position: 32 / 275 interrupteurs
lampes allumées en position: 33 / 275 interrupteurs
lampes allumées en position: 34 / 275 interrupteurs
lampes allumées en position: 35 / 275 interrupteurs
lampes allumées en position: 37 / 275 interrupteurs
lampes allumées en position: 38 / 275 interrupteurs
lampes allumées en position: 39 / 275 interrupteurs
lampes allumées en position: 40 / 275 interrupteurs
lampes allumées en position: 41 / 275 interrupteurs
lampes allumées en position: 42 / 275 interrupteurs
lampes allumées en position: 43 / 275 interrupteurs
lampes allumées en position: 44 / 275 interrupteurs
lampes allumées en position: 45 / 275 interrupteurs
lampes allumées en position: 46 / 275 interrupteurs
lampes allumées en position: 47 / 275 interrupteurs
lampes allumées en position: 48 / 275 interrupteurs
lampes allumées en position: 50 / 275 interrupteurs
lampes allumées en position: 51 / 275 interrupteurs
lampes allumées en position: 53 / 275 interrupteurs
lampes allumées en position: 55 / 275 interrupteurs
lampes allumées en position: 57 / 275 interrupteurs
lampes allumées en position: 59 / 275 interrupteurs
lampes allumées en position: 61 / 275 interrupteurs
lampes allumées en position: 63 / 275 interrupteurs
lampes allumées en position: 64 / 275 interrupteurs
lampes allumées en position: 65 / 275 interrupteurs
lampes allumées en position: 67 / 275 interrupteurs
lampes allumées en position: 69 / 275 interrupteurs
lampes allumées en position: 71 / 275 interrupteurs
lampes allumées en position: 73 / 275 interrupteurs
lampes allumées en position: 75 / 275 interrupteurs
lampes allumées en position: 77 / 275 interrupteurs
lampes allumées en position: 78 / 275 interrupteurs
lampes allumées en position: 79 / 275 interrupteurs
lampes allumées en position: 81 / 275 interrupteurs
lampes allumées en position: 83 / 275 interrupteurs
lampes allumées en position: 84 / 275 interrupteurs
lampes allumées en position: 85 / 275 interrupteurs
lampes allumées en position: 89 / 275 interrupteurs
lampes allumées en position: 90 / 275 interrupteurs
lampes allumées en position: 91 / 275 interrupteurs
lampes allumées en position: 95 / 275 interrupteurs
lampes allumées en position: 96 / 275 interrupteurs
lampes allumées en position: 97 / 275 interrupteurs
lampes allumées en position: 100 / 275 interrupteurs
lampes allumées en position: 101 / 275 interrupteurs
lampes allumées en position: 102 / 275 interrupteurs
lampes allumées en position: 103 / 275 interrupteurs
lampes allumées en position: 104 / 275 interrupteurs
lampes allumées en position: 107 / 275 interrupteurs
lampes allumées en position: 109 / 275 interrupteurs
lampes allumées en position: 112 / 275 interrupteurs
lampes allumées en position: 113 / 275 interrupteurs
lampes allumées en position: 114 / 275 interrupteurs
lampes allumées en position: 115 / 275 interrupteurs
lampes allumées en position: 116 / 275 interrupteurs
lampes allumées en position: 119 / 275 interrupteurs
lampes allumées en position: 124 / 275 interrupteurs
lampes allumées en position: 125 / 275 interrupteurs
lampes allumées en position: 126 / 275 interrupteurs
lampes allumées en position: 127 / 275 interrupteurs
lampes allumées en position: 128 / 275 interrupteurs
lampes allumées en position: 130 / 275 interrupteurs
lampes allumées en position: 131 / 275 interrupteurs
lampes allumées en position: 133 / 275 interrupteurs
lampes allumées en position: 135 / 275 interrupteurs
lampes allumées en position: 136 / 275 interrupteurs
lampes allumées en position: 137 / 275 interrupteurs
lampes allumées en position: 138 / 275 interrupteurs
lampes allumées en position: 139 / 275 interrupteurs
lampes allumées en position: 143 / 275 interrupteurs
lampes allumées en position: 144 / 275 interrupteurs
lampes allumées en position: 148 / 275 interrupteurs
lampes allumées en position: 149 / 275 interrupteurs
lampes allumées en position: 151 / 275 interrupteurs
lampes allumées en position: 152 / 275 interrupteurs
lampes allumées en position: 156 / 275 interrupteurs
lampes allumées en position: 157 / 275 interrupteurs
lampes allumées en position: 161 / 275 interrupteurs
lampes allumées en position: 163 / 275 interrupteurs
lampes allumées en position: 164 / 275 interrupteurs
lampes allumées en position: 165 / 275 interrupteurs
lampes allumées en position: 167 / 275 interrupteurs
lampes allumées en position: 168 / 275 interrupteurs
lampes allumées en position: 170 / 275 interrupteurs
lampes allumées en position: 172 / 275 interrupteurs
lampes allumées en position: 173 / 275 interrupteurs
lampes allumées en position: 176 / 275 interrupteurs
lampes allumées en position: 179 / 275 interrupteurs
lampes allumées en position: 181 / 275 interrupteurs
lampes allumées en position: 182 / 275 interrupteurs
lampes allumées en position: 184 / 275 interrupteurs
lampes allumées en position: 187 / 275 interrupteurs
lampes allumées en position: 188 / 275 interrupteurs
lampes allumées en position: 189 / 275 interrupteurs
lampes allumées en position: 190 / 275 interrupteurs
lampes allumées en position: 191 / 275 interrupteurs
lampes allumées en position: 192 / 275 interrupteurs
lampes allumées en position: 193 / 275 interrupteurs
lampes allumées en position: 195 / 275 interrupteurs
lampes allumées en position: 196 / 275 interrupteurs
lampes allumées en position: 197 / 275 interrupteurs
lampes allumées en position: 199 / 275 interrupteurs
lampes allumées en position: 204 / 275 interrupteurs
lampes allumées en position: 209 / 275 interrupteurs
lampes allumées en position: 211 / 275 interrupteurs
lampes allumées en position: 212 / 275 interrupteurs
lampes allumées en position: 221 / 275 interrupteurs
lampes allumées en position: 223 / 275 interrupteurs
lampes allumées en position: 224 / 275 interrupteurs
lampes allumées en position: 227 / 275 interrupteurs
lampes allumées en position: 228 / 275 interrupteurs
lampes allumées en position: 229 / 275 interrupteurs
lampes allumées en position: 230 / 275 interrupteurs
lampes allumées en position: 231 / 275 interrupteurs
lampes allumées en position: 233 / 275 interrupteurs
lampes allumées en position: 234 / 275 interrupteurs
lampes allumées en position: 236 / 275 interrupteurs
lampes allumées en position: 238 / 275 interrupteurs
lampes allumées en position: 239 / 275 interrupteurs
lampes allumées en position: 240 / 275 interrupteurs
lampes allumées en position: 241 / 275 interrupteurs
lampes allumées en position: 243 / 275 interrupteurs
lampes allumées en position: 244 / 275 interrupteurs
lampes allumées en position: 245 / 275 interrupteurs
lampes allumées en position: 247 / 275 interrupteurs
lampes allumées en position: 250 / 275 interrupteurs
lampes allumées en position: 251 / 275 interrupteurs
lampes allumées en position: 252 / 275 interrupteurs
lampes allumées en position: 253 / 275 interrupteurs
lampes allumées en position: 255 / 275 interrupteurs
lampes allumées en position: 256 / 275 interrupteurs
lampes allumées en position: 257 / 275 interrupteurs
lampes allumées en position: 260 / 275 interrupteurs
lampes allumées en position: 261 / 275 interrupteurs
lampes allumées en position: 263 / 275 interrupteurs
lampes allumées en position: 266 / 275 interrupteurs
lampes allumées en position: 268 / 275 interrupteurs
lampes allumées en position: 269 / 275 interrupteurs
lampes allumées en position: 270 / 275 interrupteurs
lampes allumées en position: 271 / 275 interrupteurs
lampes allumées en position: 273 / 275 interrupteurs
153 lampes allumées.

Reneb

Dernière modification par renéb (11-01-2025 22:57:47)