Inscription / Connexion Nouveau Sujet
eclairage public
Bonjour
Je vous propose l'exercice suivant , dans un soucis d'économie , une petite commune souhaite maitriser ses dépenses d'eclairage publique .
Sur une artère se trouve 50 luminaires , la commune souhaite éteindre 15 de ses luminaires la nuit sauf les luminaires situés aux deux extremités de l'artère qui doivent foncctionner et avec la contrainte que deux liminaires adjacents ne doivent jamais être allumés ensembles .
Combien existe t il de facons de faire ?
rectification lire :
Sur une artère se trouve 50 luminaires , la commune souhaite allumer 15 de ses luminaires la nuit , les luminaires situés aux deux extremités de l'artère doivent fonctionner et avec la contrainte que deux liminaires adjacents ne doivent jamais être allumés ensembles .
Combien existe t il de facons de faire ?
Cliquez pour afficher
C'est beaucoup plus que ça dpi.
Regarde mes messages et 
Denombrement.
Je traite un des cas que tu as envisagé : 20 luminaires en tout dont 6 vont rester en activité.
Le premier et le dernier restent en activité.
Un codage d'une possibilité, avec a pour allumé et e pour éteint :
a e e a e a e e e e e e a e e e a e e a
On enlève un e entre les a car il y en a au moins un :
a e a a e e e e e a e e a e a
On enlève le premier et le dernier a qui sont déterminés :
e a a e e e e e a e e a e
On obtient 13 lettres parmi lesquelles il y a 4 lettres a.
Opération inverse à partir de 13 lettres a ou e avec 4 lettres a :
a a a a e e e e e e e e e
On ajoute les deux a des extrémités :
a a a a a e e e e e e e e e a
On ajoute un e entre les a :
a e a e a e a e a e e e e e e e e e e a
On a donc 715 possibilités pour le cas de 20 luminaires dont 6 vont restent en activité.
De rien, et je corrige ma coquille :
715 possibilités pour le cas de 20 luminaires dont 6 restent en activité.
Bonne fin de week-end 
Suite
Toujours sur le test (20;6)
Une idée en utilisant le binaire (1 allumé et 0 éteint )on voit
que les positions vont de 529749 à 699009 .
On devrait trouver l'incrément qui fait passer du premier au dernier.
Bonsoir dpi,
Peux-tu être plus explicite sur l'utilisation du binaire ?
Il ne faut pas que deux 0 se suivent.
Comment obtiens-tu 529749 et 699009 ?
>Sylvieg
Toujours dans mon modèle (20;6)
On pose 1 =allumé et 0=éteint
on va donc de 10101010101010000001
à 10000001010101010101
soit en décimal de 699009 à 529749.
(Déjà on est sûr que la solution est <169260 )
Reste à trouver comment éliminer les 11 successifs.
Ce n'est qu'une idée ,mais je pense qu'elle n'est pas jouable...
Au passage...
715 positions pour (20;6) me parait plus que mon bidule qu'y en trouve 435 (sauf erreur) .
Un programmeur validera t-il la bonne réponse
Bonjour,
Après une semaine de réflexion,j'ai enfin trouvé la solution pour 20 luminaires dont 6 allumés non consécutifs en ayant en plus le premier et le dernier toujours allumés.
En utilisant le codage binaire pour les 16 luminaires concernés ,il y a exactement 462 possibilités et non 715 issus du calcul initial.
J'en déduis la formule suivante:
soit N les luminaires de la rue et n ceux qu'on veut allumer sans en
avoir deux consécutifs:
C(N-n-3;n)
soit pour N=20 et n=6
C(11;6)=462
pour l'énoncé N=50 et n=15
C(32;15)= 565 722 720
Pour tester:
N=30 et n=9
C(18;9) =48620
Bonsoir dpi , avec N luminaires , ceux des extremités doivent etre allumés donc les luminaires 2 et N-1 sont forcement eteints. il reste donc N-4 luminaires dont il faut s'occuper sans que deux luminaires consecutifs soient allumés , comme les luminaires 1 et N sont allumés , et qu'on doit en allumer 15 , on va donc travailler sur 13 luminaires à allumer sur les N-4 sans avoir deux luminaires consecutifs allumés , ce qui peut se faire de C(N-4 - 13 +1 , 13)=C(N-16,13) si N = 50 , on a donc C(34,13) facons de faire
....avec tes données (N , n ) la formule qui en découle serait C(N-4-(n-2)+1, n-2)=C(N-n-1,n-2) donc avec N=30 et n = 9 ca donne C(20,8)=125970 facons de faire
Bonjour flight,
Justement...NON
Sylvieg pour 20 luminaires dont premier et derniers allumés +6 non consécutifs m'avait donné 715 comme réponse.
comme à ce stade ,on peut avec astuce binaire faire un plan complet,
on arrive à 462 façons.
Comme je la croyais j'ai d'ailleurs répondu C(34.13) le 12 à 8 h 08
soit 927 983 760 façons.
Le doute m'habitant ,j'ai revérifié pour 20;6
et je confirme qu'il n'y a pas 715 façons ,mais 462
Je donne les 20 premières et les 20 dernières....
Comme j'avais déjà vu pour 10;6
Je confirme que la bonne combinaison est C(N-3-n;n)
20 luminaires dont premier et derniers allumés +6 non consécutifs
sur 20 luminaires tu dois allumer en tout 8 luminaires ( 6+2)
tout va se jouer ensuite sur 16 luminaires et 6 non consecutifs parmi ces 16 là .
soit ici C(16-6+1,6)=462 possibilités ce que tu a trouvé , ma formule
generale C(N-n-1,n-2) donne C(20-8-1,6)=C(11,6)= 462
je ne vois pas en quoi "justement non" ce justifie dans ton precedent post
On est donc d'accord pour 20;6 et on tombe sur la même combinaison :C(11;6)=462
Mais alors pourquoi pour le test à 30 tu trouves 77520
alors qu'avec la mienne je trouve 48620 =C(18;9)
Je pense que nous fatiguons....
On vérifie :
10;3 4 solutions qui viennent de C(4;3) =4 avec4= 10-3-3 et 3 qui demeure
20;6 462 solutions qui viennent de C(11;6)=462 avec 11=20-3 -6et 6 qui demeure.
30;9 48620 solutions qui viennent de
C(18;9) 48620 avec 30-3-9=18 et 9 qui demeure
Pour l'énoncé initial:
50;15 565 722 720 solutions qui viennent de C(32;15)=565 722 720
avec 50-3-9=32 et 9 qui demeure.
Bonjour,
Ce qui m'a motivé ,c'est que d'habitude je fais confiance à Sylvieg
qui pour mon exemple 20;6 trouvait 715 alors que mon bidule donnait 462 .
Cela voulait dire que sa formule n'était pas la bonne...
Je suis surpris que personne ne soit venu ,certainement en pensant
que cela n'en voulait pas la peine .
Je confirme mes réponse tant que la réponse officielle pour 50;15
n'est pas donnée.
Cette réponse:
927 983 760 ,je l'ai donnée le 12 à 8 h 08
Mais je la conteste pour une raison très simple:
Je l'ai donnée sur une déduction du calcul de Sylvieg or il
se trouve que sa répons est fausse pour 20;6 à savoir 715 (avec la même formule).
Nous savons formellement que c'est 462 =C(11;6)
Par ailleurs un modèle 10 luminaires avec 3 allumés en plus des deux
extrêmes donne C(4;2) =4
On obtient le 4 en faisant( comme pour 462 que tu as validé)
10-3-3 =4
Pour 50 je donne donc 565 722 720 tant qu'on ne m'aura pas
dit où je me trompe dans mon raisonnement.
Je vais me reposer 15 jours au Québec
Bonjour dpi,
J'espère ne pas troubler ton repos au Québec.
Pour 20 et 6, nous ne parlons pas de la même chose.
Je traite ce cas où il y a 6 luminaires allumés :
715 possibilités pour le cas de 20 luminaires dont 6 restent en activité.
la solution pour 20 luminaires dont 6 allumés non consécutifs en ayant en plus le premier et le dernier toujours allumés.
Pour 20 luminaires dont 8 allumés, la réponse est bien 462
Pour ton exemple avec 10 luminaires dont 3 allumés en plus des deux extrêmes, on trouve bien 4.
Bonjour ,
De retour reposé
Effectivement (merci le repos....)
*Je notais N le nombre d'emplacements pour réverbères
*n le nombre de réverbères à allumer
*en respectant la règle initiale:
2 extrémités toujours allumées et n sans être voisins .
Ainsi pour n=20 et n=6 le nombre d'emplacements possibles est 462
Je confirme pour N=30 et n=9 C(N-3-n;n)= 48620
Pour mémoire pour l'énoncé initial:
Je n'avais pas lu la remarque de flight du 22/06 15-->13
N=50 et n=13----> C(50-3-13;15)=927 983 760
Bonjour,
J'ai eu du temps au Québec
J'ai définitivement la preuve pour N=30 et n=9
C'est à dire :
30 emplacements
2 extrémités toujours allumées
9 à allumer sans en avoir deux consécutives.
Ceci au passage vérifie ma formule C(N-3-n;n )
Ici C(18;9)=48620.
Je garde mon bidule....
Bonjour
Pour N=30 et n=9 luminaires à allumer, si ceux des extrémités doivent être allumés c'est forcément 30-4 ampoules dont ont ne s'occupe pas, puisque les 2 lampes situés à côté de celles situées au extrémités ne doivent pas fonctionner, il reste donc en réalité 7 ampoules à allumer parmi 26 en faisant en sorte que deux ampoules consécutives ne soient pas allumées cela peut donc se faire de C(26-7+1,7)=C(20,7) façons soit 77520 façons de faire.
Depuis le début tu n'as pas vu ma définition malgré mes explications...
On est tombé d'accord pour 20 voir ta citation.
Donc 462 et non 715.
Pour 30 j'ai suivi la même logique en donnant à n le nombre
des ampoules à allumer étant bien entendu que nous ne parlons plus
des 2 extrémités qui sont une constante ainsi que les deuxième et avant dernière éteintes.
Ceci m'a simplifié le travail en testant sur 26 et 9
Tu peux voir le résultat de mon bidule qui confirme.
je ne sais pas si ton erreur est ici mais il me semble que si
"J'ai définitivement la preuve pour N=30 et n=9
C'est à dire :
30 emplacements 'oui au debut
2 extrémités toujours allumées ' donc on travail sur 30-4=26 ampoules
9 à allumer sans en avoir deux consécutives." ...non ici c'est 7 à allumer car les extremités comptent aussi
Bonjour,
Sylvieg peut arbitrer car elle a bien compris la confusion.
L'exemple 20 en est la preuve. Je disais 20/6 en pensant 20 dont 2+6
et je notais N=20 et n=6 car je ne tenais plus compte des 2 extrémités.
Pour 30/9 il s'agit bien de 30 dont 2+9 en notant N=30 et n=9.
Je dois donc m'excuser d'avoir voulu prendre de exemples exploitables en vue d'une vérification....
Annuler
connectez vous