Vous êtes face à une grande rangée de 12486 diodes bleues.
Au début, seule celle située complètement à gauche est allumée. Ensuite, toutes les secondes, l'opération suivante est réalisée:
Chaque diode change d'état si et seulement si celle située à sa gauche était allumée une seconde avant.
La diode située le plus à gauche reste allumée tout le temps. Le processus s'arrête lorsque la diode située à l'extrémité droite s'allume pour la première fois.
Combien de diodes sont alors allumées ?
2007-06-22 23:52:14 · 12 réponses · demandé par Anonymous dans Sciences et mathématiques ➔ Mathématiques
la diode de droite s'alume à la 12485 ième seconde
(chaque seconde ça se décale d'un cran)
pour la nième seconde, le nombre de diodes allumées est égal à 2 pussance fois le nombre de 1 qu'il y a dans l'expression de la valeur de cette seconde en binaire
(je saurais pas prouver pourquoi mais c'est ce que j'obtiens en simulant les 40 premières diodes sur un tableur)
12485 en binaire ça donne
11000011000101
il y a 6 fois le chiffre 1 dans ce nombre
donc il y a 2^6 lampes allumées soit 64
2007-06-23 01:06:36 · answer #1 · answered by jam63112 6 · 1⤊ 4⤋
C'est Jam63112 qui a raison !
Je cherche la démonstration de son résultat...
______________________________________________
J'ai trouvé mais c'est super tordu !
On associe à l'état des diodes un polynome. La diode n allumée donne le monôme X^(n-1) sinon 0 si elle est éteinte. Puis on additionne les résultats
Ainsi l'état 100101000...0 donne le polynome: 1+X^3+X^5
Notons P(k) le polynome correspondant à l'état des diodes après k secondes. (Attention, k n'est pas la variable mais l'indice)
on va montrer par recurrence sur n la propriété suivante:
pour tout a : 0
La récurrence est facile en constatant que l'hypothèse de récurrence appliquée n fois implique que:
P(2^(n+1)-1)=1+X+X^2+....+X^(2^(n+1)-1) (que des 1 !)
On a donc P(2^(n+1))=1+X^(2^(n+1))
Le reste de la récurrence est élémentaire (il suffit d'écrire)
A partir de là le calcul de l'état des diodes se fait de proche en proche en se servant de la décomposition du nombre de secondes en puissances de 2
Comme 12485=8192+4293 alors
P12485=P4293(1+X^8192)
4293=4096+197 donc P4293=P197(1+X^4096)
P12485=P197*(1+X^8192)(1+X^4096)
Il y aura autant d'étapes que de puissances de 2 dans la décomposition en somme de puissances. Et le nombre de coefficients non nul du polynome double à chaque étape ! (il n'y a pas de "retenue" pour une évidente question de degré)
Voilà voilà... on retrouve bien les 64 diodes allumées
2007-06-23 04:05:49 · answer #2 · answered by Angelique 6 · 3⤊ 1⤋
Si j'ai bien compris le fonctionnement, j'en trouve 64.
Note: étant donné que je ne suis pas trop matheux, j'ai du faire un petit algorithme. Je pense que la solution analytique ne doit pas être si simple : ))
Note: pour 12485, il n'y en aura que 32. Mais ça aurait été plus simple pour 16384 diodes ou 32768 ; - )
2007-06-23 11:52:57 · answer #3 · answered by Anonymous · 1⤊ 1⤋
En tout cas, on retrouve un chouette triangle de Sierpinski dans cette histoire...
2007-06-23 05:25:56 · answer #4 · answered by El Jj 2 · 0⤊ 1⤋
Ca y est j'ai sais le truc !
A t=0 : seule la diode de gauche est allumée
A t=1s : la 2e diode s'allume : 2 diodes allumées
A t=2s : la 2e diode d'éteint, la 3e s'allume : toujours 2 diodes allumées
A t=3s : la 2e se rallume, la 3e s'éteint, la 4e s'allume : 3 diodes allumées
Et ainsi de suite...
A t=n secondes, si n est impair, ((n+1)/2)+1) diodes sont allumées, et autant de diodes sont allumées 1 seconde après (mais pas les mêmes, sauf la 1re)
De plus, à t=n secondes, la (n+1)e diode de la barrette s'allume. L'opération s'arrête donc à 12485 secondes, nombre impair, lorsque la dernière diode est allumée, et lorsque 6244 diodes sont allumées, c'est-à-dire toutes les diodes paires plus la première !
Ah, Cristiana a trouvé 6245... Qui s'est planté d'une unité ??? (ça peut arriver très vite dans ce genre de problèmes ;-))
Tintin : "le processus s'arrête" ne veut pas dire qu'on débranche le système, ça veut dire que les diodes ne changent plus d'état, en l'occurence suivant la règle énoncée !
Donc tu n'es pas dispensé de calculs ;-)
POST : Ouh là là en effet on est complètement à l'ouest, vu les réponses qu'il vient d'y avoir. J'ai refait le raisonnement plus précisément, et en effet, la 3e diode n'a aucune raison de s'éteindre au bout de 3s !!! Du coup toute la suite foire...
J'ai d'autant plus la honte que j'utilise ce genre de codage dans mon boulot (mais à l'envers...)
1 étoile pout la peine !!
2007-06-23 00:42:25 · answer #5 · answered by Anonymous · 1⤊ 3⤋
Question interssante parce que on ne sait pas jusqu'a quel point il faut chercher..
Je pense plutot sur une semi-blague (voir les "forts en maths") mais:
1) si celle située à gauche etait allumée 1 s avant (la question):
=> toutes les diodes sont allumées
2) si celle située à gauche s'est allumée 1 s avant: (question alors mal posée)
=> 1 diode allumée
Bonne continuation!
2007-06-23 04:53:28 · answer #6 · answered by regard0169 2 · 0⤊ 3⤋
0 puisque le procesus s'arrete apres l'allumage de la derniere a droite
pourquoi faire des calculs savant alors qu'il suffit de lire correctement la question
2007-06-23 02:20:27 · answer #7 · answered by tintin 76 4 · 0⤊ 4⤋
très bien
2007-06-23 02:10:31 · answer #8 · answered by Anonymous · 0⤊ 4⤋
Toutes.
2007-06-23 01:19:18 · answer #9 · answered by Anonymous · 0⤊ 4⤋
tu peux préciser un peu est ce que combien de diodes se sont allumées avant la dernière ou bien combien de diodes sont allumées lorsque la dernière s'allume??
2007-06-23 00:21:42 · answer #10 · answered by clémence 2 · 0⤊ 4⤋