L'énigme des 7 bougies

[Lostounet]

Bonjour,

Petit problème niveau collège.


7 bougies allumées sont disposées sur un gâteau circulaire.
On peut à un moment donné souffler pour éteindre 1 bougie, mais alors les deux bougies adjacentes s'éteignent.
On suppose que souffler sur une bougie déjà éteinte rallume la bougie soufflée (ainsi que celles qui lui sont adjacentes, si jamais elles sont déjà éteintes).
En d'autres termes, souffler sur une bougie inverse l'état de cette bougie ainsi que celui des deux autres qui lui sont adjacentes.


Quel est le nombre minimal de fois qu'il faut souffler pour éteindre toutes les bougies ?
Quel est le meilleur outil du supérieur pour formaliser ce genre de configurations? Est-ce que cela peut avoir une application en électricité ?

[nodgim]

L'énoncé n'est pas complet il me semble: est ce qu'une bougie allumée à coté d'une bougie éteinte qu'on souffle s'éteint ?

[beagle]

"Quel est le meilleur outil du supérieur pour formaliser ce genre de configurations"
matrices-vecteurs

[nodgim]

Sinon, on souffle 1 fois et 1 seule sur chaque bougie.

PS : Des ampoules électriques et des interrupteurs seraient plus réalistes que ces bougies qu'on allume en les soufflant...

[beagle]

en vectoriel, matrice 7x7, chaque bougie est soufflée 3 fois en 7 coups

[fatal_error]

pour ma part
1111111 (indexé en 0...6 de gauche à droite)
souffle sur 1
0001111
souffle sur 4
0000001
souffle sur 5
0000111
souffle sur 5
0000000

souffler en deux coups pas possibles (car 7 bougies et au plus on éteint 2)
donc il reste 3 coups à checker.
le premier coup aligne 000 quelque part. par permute circulaire on peut alors considérer
0001111 à éliminer en deux coup.
puis ici, au cas par cas pour voir que c'est pas possible.

D'un point de vue algo, on peut s'en sortir avec des graphes.
un noeud est un vecteur donné.
on transitionne en soufflant sur un des bits.
puis on prend le plus court chemin de 1111111 vers 0000000

[Intégrer]

Quand tu souffles la première fois sur 5 tu éteins la dernière bougie...

[beagle]

si souffler c'est agir, on le note 1, et zero pour ne rien faire
alors la matrice 7x7, pour un bète décalage de une case:

1110000
0111000
0011100
0001110
0000111
1000011
1100001

avec un décalage de 2:
1110000
0011100
0000111
1100001
0111000
0001110
1000011

une action éteint, la deuxième rallume, la troisième éteint
si tout le monde est à trois, tout est éteint.

PS:on peut prendre l'ordre des rangées que l'on veut, donc a priori déjà 7! solutions différentes, non?

[nodgim]

@ Fatal Error : agir 2 fois sur la même bougie, c'est n'avoir rien fait !

@ Beagle: L'ordre est sans importance. Il faut que chaque bougie soit actionnée un nombre impair de fois.

Le max est 7 (on n'agit pas 2 fois sur la même bougie). Comme on n'agit pas 2 fois sur la même bougie, chaque bougie est actionnée 3 fois max, et donc 1 fois ou 3 fois. Or ...131....n'est pas possible. Donc la seule solution est 3333333.

[chan79]

si on a plus de souffle, on peut souffler 9 fois
6,2,4,1,5,4,3,7,4

[nodgim]

Sans doute, mais c'est ballot de souffler 3 fois sur la 4, alors qu'une seule fois suffit. Pourquoi s'acharner comme ça ?

[fatal_error]

au risque de paraitre complètement débile, non?

Quand tu souffles la première fois sur 5 tu éteins la dernière bougie...

bougie 5: (avant souffler) 0

On suppose que souffler sur une bougie déjà éteinte rallume la bougie soufflée (ainsi que celles qui lui sont adjacentes, si jamais elles sont déjà éteintes).

donc bougie 4,5,6 prennent valeur 1.

@ Fatal Error : agir 2 fois sur la même bougie, c'est n'avoir rien fait !

non plus.
001
je souffle sur bougie 1:
111
(car On suppose que souffler sur une bougie déjà éteinte rallume la bougie soufflée (ainsi que celles qui lui sont adjacentes, si jamais elles sont déjà éteintes).)

je resouffle sur bougie 1:
000
(car On peut à un moment donné souffler pour éteindre 1 bougie, mais alors les deux bougies adjacentes s'éteignent.)

[beagle]

pas clair ça:
"non plus.
001
je souffle sur bougie 1:
111
(car On suppose que souffler sur une bougie déjà éteinte rallume la bougie soufflée (ainsi que celles qui lui sont adjacentes, si jamais elles sont déjà éteintes).)

je resouffle sur bougie 1:
000"
.................................................................................................................
pour moi si la 1 est à gauche
001 tu souffles bougies 1:
111
tu resouffles bougies 1:
001

ou alors ta bougies 1 est celle du milieu (comme cela on voit les deux adjacents):
001
souffle sur la milieu
110
tu resouffles sur celle milieu
001

adjacent = les bougies de chaque coté de celle soufflée.

[Pseuda]

Bonjour,

L'énoncé n'est pas clair. Pour résumer, si on souffle sur une bougie, est-ce que cela change le switch (allumée=>éteinte, éteinte=>allumée) de la bougie et des 2 adjacentes ?

[beagle]

Bonjour,

L'énoncé n'est pas clair. Pour résumer, si on souffle sur une bougie, est-ce que cela change le switch (allumée=>éteinte, éteinte=>allumée) de la bougie et des 2 adjacentes ?

pour moi c'est cela tout a fait
tu souflles sur une bougie et cela change celle soufflée et les deux de chaque coté.

[WillyCagnes]

bjr Lostounet

tu me fais sourire quand tu dis :Petit problème niveau collège.

alors que ce sont les vétérans et cracks en maths qui ont répondu

[nodgim]

@ fatal error: tu n'as pas bien compris ma remarque: si tu souffles 2 fois sur la même bougie, la 5, c'est comme si tu n'avais rien fait sur cette bougie là, je ne parlais pas des voisines. Et integrer avait raison de signaler une erreur dans ta liste.

J'ai expliqué les raisons pour lesquelles tu ne peux pas le faire en moins d'une action par bougie, j'espère que tu es d'accord.

[Lostounet]

Bonjour,

L'énoncé n'est pas clair. Pour résumer, si on souffle sur une bougie, est-ce que cela change le switch (allumée=>éteinte, éteinte=>allumée) de la bougie et des 2 adjacentes ?

Bonjour,
Oui oui.
Souffler sur la bougie inverse l'état de la bougie et des deux adjacentes. Pas de piège là dessus.

[chan79]

Sans doute, mais c'est ballot de souffler 3 fois sur la 4, alors qu'une seule fois suffit. Pourquoi s'acharner comme ça ?

c'est vrai mais je me suis amusé à faire un petit programme (certes un peu idiot) qui souffle au hasard jusqu'à ce que tout soit éteint ...

[fatal_error]

@nodgim
si tu souffles 2 fois sur la même bougie, la 5, c'est comme si tu n'avais rien fait sur cette bougie là

Ben je suis d'accord avec toi mais je vois pas en quoi ma liste est pas bonne.
avant avoir soufflé deux fois sur 5
0000001
apres avoir soufflé deux fois sur 5
0000000
la bougie n'a pas changé ce qui est correcte.

Et integrer avait raison de signaler une erreur dans ta liste.

ben au risque de tjs paraitre stupide je vois pas en quoi.
Pe parce que il part sur le principe du switch (ce dont j'aimerais confirmation) auquel cas ok (car je suis parti sur principe qu'il n'y a __pas__ de switchau sens de lostounet). Sinon je comprends tjs pas.