Bonjour, voilà un petit problème assez drôle.
Une file d'attente est constituée de n personnes.
La première personne reste toujours debout.
Au départ, toutes les autres personnes sont assises.
Toutes les minutes, l'état de la file se modifie :
*la première personne reste toujours debout.
*La personne n+1 s'assoit (ou reste assis) si la personne n est dans la même position qu'elle.
*La personne n+1 se lève(ou reste debout) si la personne n est dans une position différente d'elle.
1°) Montrer que l'état de la file est cyclique(périodique dans le temps)
2°) Etablir le lien entre la parité des coefficients du binôme de Newton et la période de la file....
Voilà....
Amusez-vous bien.
Pour bien me faire comprendre, voilà ce que ca donne :
t=0 debout/assis/assis/assis/assis/........
t=1min debout/debout/assis/assis/assis/......
t=2min debout/assis/debout/assis/assis/........
t=3min debout/debout/debout/debout/assis/assis/assis/assis/.....
t=4min debout/assis/assis/assis/debout/assis/assis/assis/....
etc.....
Une drôle de file d'attente
24 messages
- Page 1 sur 2 - 1, 2
par ThSQ » 07 Nov 2007, 00:07
Ca a l'air amusant mais j'imagine qu'il n'y a pas de rapport entre le premier 'n' est les autres et "la personne n+1 se lève(ou reste debout) si la personne n+1" ne semble suspect 
Sinon quel que soit le procédé comme il n'y a qu'un nombre fini de disposition (au plus
) on finit toujours par retomber sur une disposition déjà vue et ça recommence à l'identique.
Sinon quel que soit le procédé comme il n'y a qu'un nombre fini de disposition (au plus
par ThSQ » 07 Nov 2007, 01:14
A mon avis la périodicité est la plus petite puissance de 2 immédiatement supérieure ou égale à n (ie si n=31 la périodicité est 32, si n=32 c'est 32).
Lemme : le seul cas où tous les coefficients du binôme sont pairs (sauf les 2 extrêmes) est quand n est une puissance de 2.
Si n = N*2^a avec N impair, C(n,2^a) est impair (écrire le binome sous forme de rapport). Si N=2^a il n'y a pas assez de puissance de 2 au dénominateur pour "killer" toutes celles du numérateur.
Le procédé revient à :
(u1,u2, ..., un) -> (u1,u1+u2,u2+u3, ..., u(n-1)+u(n)) en codant 0 = assis, 1 = debout et en raisonnant modulo 2.
Maintenant c'est une affaire de récurrence de voir qu'au k_ième tour on a en position l,
modulo 2.
Donc toutes les puissances de 2 = 2^N et seulement dans ce cas là (lemme) on revient dans la position d'origine pour les N premiers termes de la série.
Lemme : le seul cas où tous les coefficients du binôme sont pairs (sauf les 2 extrêmes) est quand n est une puissance de 2.
Si n = N*2^a avec N impair, C(n,2^a) est impair (écrire le binome sous forme de rapport). Si N=2^a il n'y a pas assez de puissance de 2 au dénominateur pour "killer" toutes celles du numérateur.
Le procédé revient à :
(u1,u2, ..., un) -> (u1,u1+u2,u2+u3, ..., u(n-1)+u(n)) en codant 0 = assis, 1 = debout et en raisonnant modulo 2.
Maintenant c'est une affaire de récurrence de voir qu'au k_ième tour on a en position l,
Donc toutes les puissances de 2 = 2^N et seulement dans ce cas là (lemme) on revient dans la position d'origine pour les N premiers termes de la série.
par duchere » 07 Nov 2007, 02:05
Oui , voilà, tu as trouvé l'astude qui est de modéliser la situation par une telle suite récurrente, en remarquant que 1+1=0(mod 2) 0+0=0 , 0+1=1 et 1+0=1
Par contre, il n'est pas nécessaire que tous les coefficients du binôme soient pairs (a part les extremum), car la file d'attente ne contient que n personnes.
Ainsi, si T est la période, il faut juste que les "k parmis T" soient pairs de 1 à n-1, si je ne me trompe pas.
Donc, tu donnes là un majorant de la période mais qui est une période, c'est donc un multiple de la période.
Bonne nuit.
Par contre, il n'est pas nécessaire que tous les coefficients du binôme soient pairs (a part les extremum), car la file d'attente ne contient que n personnes.
Ainsi, si T est la période, il faut juste que les "k parmis T" soient pairs de 1 à n-1, si je ne me trompe pas.
Donc, tu donnes là un majorant de la période mais qui est une période, c'est donc un multiple de la période.
Bonne nuit.
par duchere » 07 Nov 2007, 02:09
Ah, oui, j'ajoute qu'il n'y a pas besoin de faire de formule de récurrence pour montrer qu'on a les coefficients du binôme.
Puisque
et 
pour tout k>0 et 
est une caractérisation des coefficients du binôme.
Puisque
par ThSQ » 07 Nov 2007, 10:22
Ouais tu as raison mais tu demandais pas la plus petite période ;)
C'est tiré de quoi cet exo ? Ca ressemble à un oral d'info.
C'est tiré de quoi cet exo ? Ca ressemble à un oral d'info.
par SimonB » 07 Nov 2007, 11:16
Je dirais même plus, ça ressemble à un oral d'algorithmique d'ens ;)
par duchere » 07 Nov 2007, 12:24
Je le tire de moi lol....
Au départ, je me suis mis à étudier cette suite en modulo 10; ensuite, j'ai voulu trouver un exemple pratique de cette suite, et j'ai trouvé cette file d'attente. Et je trouve que tu as du mérite d'avoir fait le chemin en sens inverse.
Voili Voilo.
Mais c'est vrai que ça ferait un bon exercice d'oral qui sélectionnerait bien les candidats !
Qui sait, peut-être que mon futur examinateur tombera sur ce post et me posera cet exo...
Bonne journée.
Au départ, je me suis mis à étudier cette suite en modulo 10; ensuite, j'ai voulu trouver un exemple pratique de cette suite, et j'ai trouvé cette file d'attente. Et je trouve que tu as du mérite d'avoir fait le chemin en sens inverse.
Voili Voilo.
Mais c'est vrai que ça ferait un bon exercice d'oral qui sélectionnerait bien les candidats !
Qui sait, peut-être que mon futur examinateur tombera sur ce post et me posera cet exo...
Bonne journée.
par ThSQ » 07 Nov 2007, 14:50
duchere a écrit:Je le tire de moi lol....
Pas mal ! Résoudre des exos c'est bien. En inventer c'est mieux !
Trop simple pour un oral d'ENS non ? (j'ai pas d'idée là-dessus en fait).
par SimonB » 07 Nov 2007, 15:32
ThSQ a écrit:Trop simple pour un oral d'ENS non ? (j'ai pas d'idée là-dessus en fait).
En informatique fondamentale, ça dépend des sujets. Parfois je trouve ça hyper-compliqué, parfois...
par ThSQ » 07 Nov 2007, 15:41
SimonB a écrit:En informatique fondamentale, ça dépend des sujets. Parfois je trouve ça hyper-compliqué, parfois...
Ah ok, merci.
Un exemple de truc hyper-compliqué ?
par SimonB » 07 Nov 2007, 15:50
ThSQ a écrit:Ah ok, merci.
Un exemple de truc hyper-compliqué ?
Dans quelques heures, quand mes vacances seront terminées (et que mes bouquins d'annales seront arrivés chez moi
).par duchere » 07 Nov 2007, 16:14
Au fait, on pourrait un peu compliquer le problème en partant d'un état initial quelconque.
Dans ce cas là, et ne lisez pas la suite de mon message si vous voullez y réfléchir tout seul, si on veut démontrer les choses simplement, ce qui est toujours préférable, il faut se servir de la linéarité de l'application que nous avons définie.
Elle est clairement linéaire, il n'y a là dessus aucun doute.
Donc, on peut décomposer tout état initial de la file sur la base canonique.
Un vecteur de la base canonique est donc du genre)
avec le 1 en kième position
A partir de là, si on appelle f l'application que nous avons définie,
)
est clairement connue.
C'est la kième ligne du triangle du Pascal sauf qu'il y a k-1 colonnes de zéro à gauche.
Donc, finalement, pour tout état initial de la file, l'état d'une personne dépend de la parité d'une certaine somme de coefficients du binôme en se servant de la linéarité.
Voilà, pour encore étendre le problème, on pourrait aussi réfléchir à une condition nécessaire et suffisante pour que deux vecteurs quelconques appartiennent au même cycle.
En effet, on a vu que la période est la plus part du temps supérieure au cardinal de l'ensemble.
Donc ce serait quelque chose d'intéressant à étudier.
Enfin bon, on pourrait faire plein de choses pour transformer ce petit exo en problème.
Mais je n'ai pas le temps.
je suis en spé....
Et je dois faire de la chimie.
Bonne journée.
Dans ce cas là, et ne lisez pas la suite de mon message si vous voullez y réfléchir tout seul, si on veut démontrer les choses simplement, ce qui est toujours préférable, il faut se servir de la linéarité de l'application que nous avons définie.
Elle est clairement linéaire, il n'y a là dessus aucun doute.
Donc, on peut décomposer tout état initial de la file sur la base canonique.
Un vecteur de la base canonique est donc du genre
A partir de là, si on appelle f l'application que nous avons définie,
C'est la kième ligne du triangle du Pascal sauf qu'il y a k-1 colonnes de zéro à gauche.
Donc, finalement, pour tout état initial de la file, l'état d'une personne dépend de la parité d'une certaine somme de coefficients du binôme en se servant de la linéarité.
Voilà, pour encore étendre le problème, on pourrait aussi réfléchir à une condition nécessaire et suffisante pour que deux vecteurs quelconques appartiennent au même cycle.
En effet, on a vu que la période est la plus part du temps supérieure au cardinal de l'ensemble.
Donc ce serait quelque chose d'intéressant à étudier.
Enfin bon, on pourrait faire plein de choses pour transformer ce petit exo en problème.
Mais je n'ai pas le temps.
je suis en spé....
Et je dois faire de la chimie.
Bonne journée.
par SimonB » 07 Nov 2007, 16:39
duchere a écrit:Mais je n'ai pas le temps.
je suis en spé....
Et je dois faire de la chimie.
Bon courage ! Ya des fois où je suis heureux d'être en spé à ne préparer que l'ENS info
par ThSQ » 07 Nov 2007, 16:53
SimonB a écrit:Bon courage ! Ya des fois où je suis heureux d'être en spé à ne préparer que l'ENS info
Grrrrr :cry2:
C'est vrai que la chimie ça gave un peu .... (je reste poli)
par duchere » 07 Nov 2007, 17:20
Pendant ma chimie, j'ai pensé à un état initial particulièrement sympa
)
En numérotant les lignes et les colonnes à partir de 0,
Le terme diagonale numéro i vaut alors)
Les termes diagonaux sont tous nuls. sauf le premier.
Au premier abord cela semble extraordinaire...
Mais en fait....
111111111111
100000000000
110000000000
101000000000
.....
C'était plus qu'une évidence vu que 111111111 est l'antécédent de 1000000000
et qu'il était donc évident que les termes diagonaux étaient nuls....
Donc je ne sers à rien.
En numérotant les lignes et les colonnes à partir de 0,
Le terme diagonale numéro i vaut alors
Les termes diagonaux sont tous nuls. sauf le premier.
Au premier abord cela semble extraordinaire...
Mais en fait....
111111111111
100000000000
110000000000
101000000000
.....
C'était plus qu'une évidence vu que 111111111 est l'antécédent de 1000000000
et qu'il était donc évident que les termes diagonaux étaient nuls....
Donc je ne sers à rien.
par duchere » 07 Nov 2007, 18:40
J'ai trouvé un truc sympa là par contre.
Mais on revient à des files dont l'état initial est (10000000....)
Soit une file de n personnes dont la période vaut)
Alors la période de la file de n+1 personnes a la période si  \\ n\end{pmatrix})
est pair et une période )
s'il est impair.
Donc en définitive, On a=2^{\sum_{k=0}^{n-1} c_k})
avec
si  \\ k\end{pmatrix})
est pair et 
sinon.
Maintenant, il serait sympa de savoir quand les
valent 0 et quand il valent 1.... peut-être est-ce simple.
PS : Pour établir la formule de récurrence, j'ai utilisé la formule donnant la somme d'une colonne du triangle de Pascal.(cf wikipedia ou vous-même si vous la connaissez)
En effet, si la somme d'une colonne est paire(en faisant la somme de la 1e ligne jusqu'à retomber sur la première ligne, mais en ne la recomptant pas), alors cela signifie que si on rajoute une personne, cela ne modifie pas la période. Si en revanche, on tombe sur un nombre impair, on double la période.
exemple :
(1) a une période de 1
1
1
La somme de la 1e ligne jusqu'à la 1e ligne vaut 1 impair. Donc on va doubler la période.
En effet 10 a pour période 2
10
11
10
On continue.
On fait la somme des termes de la dernière colonne et ce de la première ligne jusqu'à la 2e.
S=1 => période doublée
en effet
100
110
101
111
100
On continue.
Maintenant S=2 pair => La période d'une file à 4 personnes ne va pas être doublée.
En effet :
1000
1100
1010
1111
1000
S=1 => la période va être doublée pour 5 personnes
En effet :
10000
11000
10100
11110
10001
11001
10101
11111
10000
S=4 pair, la période ne va pas être doublée pour 6 personnes.
100000
110000
101000
111100
100010
110011
101010
111111
100000
etc....
En définitive, pour connaître la période d'une file d'attente de n+1 personnes, on n'a plus qu'à étudier la parité de
Or T est pair car puissance de 2.
Donc sa représentation binaire ne comptient qu'un 1.
Or, d'après le théorème ici ,
est impair si et seulement si à tous les 1 de la représentation binaire de n correspond un 1 en même positin dans la représentation binaire de T.
Comme il n'y a qu'un seul 1 dans la représentation binaire de T, il faut et il suffit carrément que n=T !!
Donc, en fait, il se passe un phénomène assez extraordinaire.
Au départ, la période prend une valeur, et elle stagne tant que n ne repasse pas par une puissance de 2. Et quand n passe par une puissance de 2, alors la période et multipliée par 2.
Elle stagne encore, puis elle rencontre de nouveau une puissance de 2, alors elle est multipliée par 2, etc....
On a donc un graphique en escalier, et la taille des marches grandit très vite car
croit très vite.
En définitive, au final T est
où m est le plus petit entier tel que inférieur ou égal à n.
D'où=2^{E(\frac{ln(n)}{ln(2)})})
Et voilà, on a terminé.
Ouf.
Bonne soirée à tous.
Désolé d'avoir été long, mais je n'avais pas trouvé le résultat quand j'ai commencé ce post !
Mais on revient à des files dont l'état initial est (10000000....)
Soit une file de n personnes dont la période vaut
Alors la période de la file de n+1 personnes a la période
Donc en définitive, On a
avec
Maintenant, il serait sympa de savoir quand les
PS : Pour établir la formule de récurrence, j'ai utilisé la formule donnant la somme d'une colonne du triangle de Pascal.(cf wikipedia ou vous-même si vous la connaissez)
En effet, si la somme d'une colonne est paire(en faisant la somme de la 1e ligne jusqu'à retomber sur la première ligne, mais en ne la recomptant pas), alors cela signifie que si on rajoute une personne, cela ne modifie pas la période. Si en revanche, on tombe sur un nombre impair, on double la période.
exemple :
(1) a une période de 1
1
1
La somme de la 1e ligne jusqu'à la 1e ligne vaut 1 impair. Donc on va doubler la période.
En effet 10 a pour période 2
10
11
10
On continue.
On fait la somme des termes de la dernière colonne et ce de la première ligne jusqu'à la 2e.
S=1 => période doublée
en effet
100
110
101
111
100
On continue.
Maintenant S=2 pair => La période d'une file à 4 personnes ne va pas être doublée.
En effet :
1000
1100
1010
1111
1000
S=1 => la période va être doublée pour 5 personnes
En effet :
10000
11000
10100
11110
10001
11001
10101
11111
10000
S=4 pair, la période ne va pas être doublée pour 6 personnes.
100000
110000
101000
111100
100010
110011
101010
111111
100000
etc....
En définitive, pour connaître la période d'une file d'attente de n+1 personnes, on n'a plus qu'à étudier la parité de
Or T est pair car puissance de 2.
Donc sa représentation binaire ne comptient qu'un 1.
Or, d'après le théorème ici ,
est impair si et seulement si à tous les 1 de la représentation binaire de n correspond un 1 en même positin dans la représentation binaire de T.
Comme il n'y a qu'un seul 1 dans la représentation binaire de T, il faut et il suffit carrément que n=T !!
Donc, en fait, il se passe un phénomène assez extraordinaire.
Au départ, la période prend une valeur, et elle stagne tant que n ne repasse pas par une puissance de 2. Et quand n passe par une puissance de 2, alors la période et multipliée par 2.
Elle stagne encore, puis elle rencontre de nouveau une puissance de 2, alors elle est multipliée par 2, etc....
On a donc un graphique en escalier, et la taille des marches grandit très vite car
En définitive, au final T est
D'où
Et voilà, on a terminé.
Ouf.
Bonne soirée à tous.
Désolé d'avoir été long, mais je n'avais pas trouvé le résultat quand j'ai commencé ce post !
par duchere » 07 Nov 2007, 19:13
Pensez-vous qu'en base p, la formule se généralise et
=2^{E(\frac{ln(n)}{ln(p)})})
Je pense que c'est possible.
Je vérifie et vous préviens.
Je pense que c'est possible.
Je vérifie et vous préviens.
24 messages
- Page 1 sur 2 - 1, 2
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 38 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :