Retournement en cascade.

[Ben314]

Salut,

Sur le pourtour d'une grande pièce circulaire sont situées portes donnant sur des bureaux (numérotés dans le sens trigonométrique de 1 à ). Sur chaque porte est suspendue une pancarte où il est écrit "Ouvert à la clientèle" d'un coté et "Fermé à la clientèle" de l'autre.
Le premier jour, un des employés retourne les pancartes sur les portes, porte après porte (dans le sens trigo.), en commençant par la sienne et en s'arrêtant dés qu'il a retourné une pancarte du coté "Ouvert"
Le deuxième jour, un autre employé fait de même en commençant lui aussi par la porte de son propre bureau.
Idem pour le troisième jour où un autre(=distinct des deux premiers) employé fait de même
Et ainsi de suite jusqu'au -ième jour.

Quel sera l'état final des pancartes (en fonction de l'état initial) ?
(Énigme tiré d'un livre)

EDIT : J'ai modifié l'énoncé après les premières réponses. Dans le premier énoncé, le jour 1, c'était l'employé du bureau 1 qui inversait les pancartes, le jour deux, celui du bureau 2, etc...

[aviateur]

bjr
L'état final est le même que l'état initial.

[Ben314]

A une exception prés, oui.
Preuve ?

EDIT : entre temps j'ai un peu généralisé l'énoncé (ça ne change rien à la soluce que je connaît)

[beagle]

…………………………..

[aviateur]

La preuve grosso modo en quelques mots. Une pancarte fermée est représentée par F, ouvert O.

Si on suppose qu'il y a au moins un O dans les pancartes. L'employé 1 va voir une liste de la forme
FF...FO (la première lettre correspond à la porte de l'employé) de longueur p=1,2,....
p=1 correspond correspond au cas où la porte de l'employée est O (il n'y pas de F dans cette liste)

Cette liste est transformée en "son opposée" i.e O....OF (quand p= 1 cette liste est = F )

C'est clair que les employés 2,...,p-1 vont agir successivement sur une seule pancarte qu finalement sera
O FFFFF
On recommence les mêmes opération partir de l'employé numéro p qui va voir une liste de la forme
FFFFFFFO est ainsi de suite. Finalement le processus s'arrêtera quand on rencontre le premier O après avoir fait un tour (en fait il correspond au plus petit numéro de porte qui avait un F)
Finalement on voit bien qu'on est retombé sur l'état initial.

Remarque s'il n'y a pas de O je n'avais pas regardé mais le cas est particulier est facile à traiter.

Ceci étant dit, est-ce qu'on peut formaliser un peu tout ça?

[Ben314]

Ceci étant dit, est-ce qu'on peut formaliser un peu tout ça?

Oui, on peut.
Sinon, là tu répond correctement à l'énoncé tel que je l'avais mis au début, mais je sais pas si ça s'adapte facilement au nouvel énoncé...

[aviateur]

Non je n'ai pas vu le nouvel. Là faut réfléchir un peu, mais j'arrête pour aujourd'hui. ça laisse vivre l'énigme.
Mais j'aimerais bien comment on peut écrire ça "plus mathématiquement"

[Lostounet]

A une exception prés, oui.
Preuve ?

EDIT : entre temps j'ai un peu généralisé l'énoncé (ça ne change rien à la soluce que je connaît)

Salut Ben,

Après avoir passé pas mal de temps à essayer de formaliser j'ai pas trop réussi (même si j'ai compris comment ça marchait intuitivement).

On travaille dans Z/2Z avec une suite qui soit "n" périodique.
(0 pour ouvert et 1 pour fermé).

L'objectif est de prendre les n premiers termes de la suite et leur ajouter une combinaison linéaire de "suites" du type (....,1,1,....) avec un certain nombre de 1.

Ce nombre de 1 (la longueur de la chaine) est obtenu en trouvant la différence entre le jour n et le plus petit indice > n tel que la composante vale 1. Je sais pas si c'est super clair ?


Au fait cela ne pourrait-il pas avoir un rapport avec l'énigme des bougies sur le gateau ? D'il y a quelques mois...
En fait j'arrive pas à trouver le fil où tu expliquais comment faire avec les "chaînes de Markov" ou plutôt des matrices ?

Bon le temps que je comprenne comment ça marchait tu as déjà généralisé l'énoncé.. :p

[Ben314]

Si, c'est à peu prés clair. Par contre, je pense pas que ce soit trop lié aux truc des bougies : là, le truc qui semble pas mal merdique, c'est que le nombre de pancartes retourné par chaque mec. dépend de la dispo. dans laquelle sont les portes. Je pense qu'on peut faire à peu prés comme à fait aviateur même dans le nouveau contexte (mais ça risque éventuellement d'être assez chiant à rédiger).
Et effectivement, comme tout le monde s'en doute, il y a une manière "très simple" (et très mathématique) d’appréhender le bidule (mais faut trouver laquelle...) qui fait en particulier qu'on a rien à f... de l'ordre dans lesquels les mecs sortent de leur bureau.

EDIT :
https://docs.google.com/spreadsheets/d/ ... sp=sharing
Les zones sur font rose sont modifiables.

[aviateur]

Rebonjour
Bon pendant le film, j'ai réfléchi à cette nouvelle version. Alors j'ai supposé qu'il y a au moins une pancarte ouverte (si tout est fermé à réfléchir).
La solution est que chaque pancarte subit 2 transformations exactement, alors à la fin des opérations on retrouve l'état initial.
Pour mettre un peu de formalisme je désigne par
les portes.
Pour visualiser la situation on peut supposer que
On définit la fonction tel que si la pancarte est "ouverte" , sinon.
Sans restreindre la généralité on suppose que
f définit une suite "d'intervalles adjacents" de E ,
tel que I_1=[z_1,...,z_q] , I_2=[z_{q+1},....,z{q+h],....
et et
En particulier ici et par la suite un intervalle est tel que seuls sont dernier élément a une image par f égale à 0.

On choisit au hasard un élément de E, Pour simplifier mes explications je vais supposer que appartient à mais cela sera suffisant pour comprendre la généralité.
L'opération consiste à retourner les pancartes de j à q, c'est à dire à "redéfinir f", c'est à dire que
et

Ce qui redéfinit une suite d'intervalles consécutifs adjacents de E.
et est ajouté à (puisque maintenant f(z_q)=1)
i.e
Le fait que est ouvert à droite signifie que ne pourra plus être tiré.

On réitère l'opération et on voit bien que chaque élément de E va être retourné 2 fois et deux fois seulement.

[Ben314]

La vision avec des intervalles, pourquoi pas, mais je comprend pas franchement le "on voit que" de la fin.
A la limite, concernant qui ont déjà été modifiés une fois et qui sont maintenant à 0, on va évidement les modifier une deuxième fois plus tard (quand ça sera eux le "départ" de la suite de modif.), et on peut éventuellement dire qu'on "voit" que c'est le seul cas par la suite où ils vont être modifié (encore que ça me semble pas archi. clair sans plus d'argument). A peu prés idem pour .
Pareil pour qui pour le moment n'a lui aussi été modifié qu'une fois : autant à la rigueur on peut "voir" qu'il va forcément être modifié une deuxième fois dans la suite, autant il me semble qu'il faudrait avancer quelques arguments pour expliquer pourquoi il ne sera modifié qu'une seule fois.

Personne ne voit à quel "phénomène classique" des math. ça correspond cette suite de modif. en cascade ?

[Lostounet]

Personne ne voit à quel "phénomène classique" des math. ça correspond cette suite de modif. en cascade ?

Les cycles et les permutations ? :p

Sinon j'ai aussi eu du mal avec la fin du post d'aviateur: j'ai pas trop compris l'argument final. Même si j'ai l'impression que je le vois assez bien sur des exemples.

[beagle]

…………………………………….

[beagle]

………………………...

[aviateur]

Bonjour
J'ai "mis on voit que" pour abréger la rédaction car il était tard. J' ai mis juste ce qu'il fallait de façon à que ceal soit possible de voir la comment ça se termine.
En effet pour les étapes suivantes, pour un employé tiré au hasard il faut envisager différentes situations.
S'il est tiré dans un autre intervalle que I_1. Et bien la situation est analogue à ce que j'ai expliqué pour I_1.
Si on regarde maintenant les employées [z_{k+1}].... si l'un d'entre eux est tirée au hazard il reprenne la valeur initiale 1 et je représente la situation par ]z_{k+1}[ indiquant qu'il ne seront plus tirés.

S'il est tiré dans l'intervalle [z_1,...,z_k[ (intervalle issu de I_1, (z_k ne peut plus être tiré)
on aboutira à une nouvelle situation de la forme [z_1,z_2[ [z_3]...[z_{k-1}] ]z_k[ (z_k a retrouvé sa situation) initiale) il ne pourra + être retourné car il y a toujours un ouvert avant lui.

Il a un travail à faire pour bien ficeler ça mais on est sur un forum et vu la longueur je m'arrête là.
Maintenant il y a peut être une façon de formaliser ça plus simplement.

[Ben314]

J'ai ajouté une "Feuille 2" contenant une façon (maline) de voir les choses sur la google sheet :
https://docs.google.com/spreadsheets/d/ ... sp=sharing

Après, en voyant la solution proposée par Aviateur, je me demande si l'énoncé ne serait pas plus intéressant sous la forme :
- Les gus qui sortent de leur bureau pour inverser les pancartes, on sait pas du tout lesquels c'est (ça peut être plusieurs fois le même ; certain peuvent ne jamais sortir ; etc...)
- Et la question, c'est maintenant de montrer que l'ordre dans lesquels les gus sortent n'a pas d'influence sur le résultat.
Posé comme ça, ça me semble bien plus difficile de faire un raisonnement du style de celui d'Aviateur avec ces intervalles.

P.S. Autre option pour rendre le truc plus compliqué à faire sans l'astuce : Se placer au bout de jours avec comme hypothèse que chaque gus est sorti exactement fois pour inverser les pancartes.

[beagle]

"- Les gus qui sortent de leur bureau pour inverser les pancartes, on sait pas du tout lesquels c'est (ça peut être plusieurs fois le même ; certain peuvent ne jamais sortir ; etc...)
- Et la question, c'est maintenant de montrer que l'ordre dans lesquels les gus sortent n'a pas d'influence sur le résultat.

cela devient plus compliqué, et je ne suis plus
prenons un exemple simple
O, F, O
et le gars en deuxième sort 3 fois, cela donne quoi???

[FLBP]

prenons un exemple simple
O, F, O
et le gars en deuxième sort 3 fois, cela donne quoi???

O,O,O 1
F,O,F 2
O,F,O 3

on revient bien à l'état initial

Edit : correction d'une erreur

[beagle]

argh c'est dimanche mais quand même pourquoi je vois pas clair?

O, F, O
le deuxième sort trois fois
je suis ok pour la premiere sortie, il retourne sa porte
O , O, O

il ressort le deuxième jour , faire O,F,O il continue O,F,F il continue F, F , F , il continue F, O, F
le deuxième jour est F, O, F non?

[beagle]

Bon sinon outre le truc de la rotation dont je parlais hier, ma matrice m'a dit.
rotation 45° juste après le premier O, puisque si premier O est en k iem position en rotation = la diago c'est inversé sur les k premières colonnes, puis ordre normal.
a tel point que l'on retrouve le cas d'exception = si tout est fermé, pas de O, ben c'est niqué.

Mais ça c'était hier, aujourd'hui par rapport à l'ordre qui ne compte pas, j'ai regardé un truc, les O de retournement, dans la matrice nxn sont un seul par rangée bien sur, et un seul par colonne,
et c'est en partie là que se joue le fait de l'existence de seuls deux changements d'états = inverse puis retours

et il est probable que c'est pour cela que l'ordre ne joue pas.

Mais comme j'ai rien compris à plusieurs fois le meme personnage, regardez bien ce message il va mourir dans quelques heures