Montées d'une permutation
Bonjour,
Je ne comprends pas d'où sort le $1 \leq M(a) \leq n$ et $1 \leq D(a) \leq n$.
Pour la question je trouve :
$E_n(1)=1$ c'est la liste $(n,n-1, \cdots 1)$
Par exemple, si pour $n=3$ et la liste $(3,2,1)$ l'unique montée est $(1)$
Puis $E_n(n)=0$ j'ai essayé pour $n=3$ je ne vois pas de liste à $n$ montées.
Est-ce correct ?
Je ne comprends pas d'où sort le $1 \leq M(a) \leq n$ et $1 \leq D(a) \leq n$.
Pour la question je trouve :
$E_n(1)=1$ c'est la liste $(n,n-1, \cdots 1)$
Par exemple, si pour $n=3$ et la liste $(3,2,1)$ l'unique montée est $(1)$
Puis $E_n(n)=0$ j'ai essayé pour $n=3$ je ne vois pas de liste à $n$ montées.
Est-ce correct ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans l'exemple qui est donné , (2,5,7,6,1,4,3,8) , on a 8 nombres.
Quand ils listent les montées, ils font des regroupements, et ils font apparaître les 8 nombres.
Pareil, quand ils listent les descentes, ils font des regroupements, et ils font apparaître les 8 nombres.
Tous les nombres apparaissent.
Et toi, quand tu fais la liste de toutes les montées, tu ne fais apparaître qu'un nombre, au lieu de 3.
L'exemple qu'ils donnent est très important. Il faut le lire, le décrypter complètement pour comprendre la mécanique.
Pas lire de façon superficielle et foncer tout de suite aux questions.
Essaie de donner la liste des montées, et la liste des descentes, avec la même présentation que dans l'exercice, pour cette série : (1,4,6,2,3,8,7,5)
Même si la question n'est pas posée, tu aurais dû toi-même essayer de faire quelques exemples comme ça, au brouillon, pour bien être sûr que tu as compris l'énoncé.
Je te disais un truc il y a une semaine ou 2 :
Dans l'ordre :
1. il faut lire l'énoncé, lentement (2 minutes)
2. lire les questions superficiellement (1 minute)
3. relire l'énoncé, ligne à ligne, mot à mot. Décrypter chaque phrase, chaque mot, chaque exemple, griffonner des trucs au brouillon pour voir si on a bien tout compris (5 minutes)
4. répondre aux questions (2 minutes par question).
Tu ne fais pas l'étape 3 alors que ça devrait être la plus longue, tu vas directement à l'étape 4. Tu ne peux pas réussir.
Ok je prends la liste $(1,4,6,2,3,8,7,5)$
Je trouve comme montées : $(7)$, $(1,4,6)$, $(2,3,8)$, $(7,5)$, et comme descentes $(1)$, $(4)$, $(3)$, $(6,2)$
On part de (2,5,7,6,1,4,3,8). On recopie les même chiffres, dans le même ordre. Mais on ajoute des séparateurs. Puis on compte le nombre de séparateurs (ou le nombre de groupes, c'est quasiment pareil)
Pour les montées, ils ont décidé de mettre des séparateurs comme ça : (2,5,7 ||| 6 ||| 1,4 ||| 3,8)
Essaie de trouver la logique pour les séparateurs, sachant qu'ils appellent ça les montées.
Dans notre exemple à nous, on veut appliquer la même mécanique à la liste (1,4,6,2,3,8,7,5)
On va donc recopier les mêmes chiffres, dans le même ordre, en ajoutant des séparateurs aux bons endroits.
A toi de jouer. Où mettre les séparateurs pour les montées ? Où mettre les séparateurs pour les descentes ?
Ce travail, c'est la partie compréhension de l'énoncé. C'est l'étape 3 dans le schéma de travail que je proposais.
C'est l'étape indispensable. Il faut y passer le temps nécessaire. Tant que cette étape là n'est pas 100% claire, ça ne sert à rien d'essayer de répondre aux questions, les réponses seront forcément fausses.
Soit la liste $(1,4,6,2,3,8,7,5)$
Je trouve comme montées : $(1,4,6), (2,3,8), (7),(7,5)$ et comme descentes ($1),(4),(6,2),(3)$
Il faut recopier les 8 chiffres dans le même ordre que la liste initiale. Et ajouter des séparateurs.
Tu ne sais pas où mettre les séparateurs, ok, admettons. Mais tu ne sais pas non plus recopier les 8 chiffres, dans le même ordre que la liste initiale !
(1,4,6),(2,3,8),(7),(7,5) : 7 est en double. C'est faux.
(1),(4),(6,2),(3) : il manque 8, 7 et 5 à la fin, c'est faux.
$L=(1,4,6,2,3,8,7)$
Montées $(1,4,6),(2,3,8),(7,5)$
Descentes : $(1),(4),(6,2),(3),(8,7,5)$
$E_n(1)=1$ pour la liste $(1,2, \ldots, n)$ et $E_n(n)=1$ pour la liste $(n,n-1, \ldots, 1)$.
Est-ce correct ?
Dans le sujet , on te demande de compter le nombre de montées possibles.
Si on considère que (1,4,6)(2,3,8)(7,5) est une montée valide , on aura un certain résultat.
Et si on considère que ce n'est pas une montée valide, on aura un autre résultat.
Tant qu'on n'est pas capable de dire si c'est une montée valide ou pas, on ne peut pas répondre à la question. Ou alors, on répond au hasard, et on passe à l'exercice suivant.
Faut être sérieux! $E_n(1)=1$ est-ce que c'est juste? Et bien commences par justifier.
Sinon pourquoi on va te dire si c'est vrai ou faux?
Des topics en jachère plus simples dont tu te fous complètement parce que tu préfères gaspiller ton temps à donner ton avis sur des sujets de concours qui te dépassent de 1000 km :
celui-ci
celui-là
ou encore this one (tu n'as pas fait l'exo de logique que tu avais promis de faire par exemple).
L'inclusion réciproque m'a l'air trop dure.
Si au lieu des mots "montées" et "descentes" on avait mis "zorglub" et "bulgroz", j'aurais pu comprendre que tu hésites, mais là, c'est on ne peut plus clair !
http://www.les-mathematiques.net/phorum/read.php?3,2037242,2039962#msg-2039962
La grande accolade, j'ai lu ... et j'ai zappé. Je suis arrivé sur la ligne d'après, avec l'exemple : montées=(2,5,7)(6)(1,4)(3,8) ...
descentes=(2)(5)(7,6,1)(4,3)(8)
Je suis resté 1 minute ou 2 sur cette ligne, celle que je viens de recopier... et j'ai compris.
Ensuite j'ai relu l'énoncé au complet : une montée est une sous-liste, ok ; ensuite, la grande accolade, je me suis dit : ok, ça a plus ou moins l'air de confirmer ce que dit l'exemple. Banzai, c'est bien ça.
Mais vouloir continuer l'exercice, sans savoir avec certitude déterminer les montées ou les descentes à partir d'une suite quelconque, ça n'a pas de sens.
J'étais obnubilé par la définition, je fais comme vous je raisonne à partir de l'exemple.
$L=(1,4,6,2,3,8,7,5)$
Les montées sont $(1,4,6),(2,3,8),(7),(5)$ et les descentes sont $(1),(4),(6,2),(3),(8,7,5)$
Un autre, pour vérifier si c'est un coup de chance, ou pas : (4;6;9;11;2;1;5;7;3;8;10)
$L=(4;6;9;11;2;1;5;7;3;8;10)$
Les montées sont $(4,6,9,11),(2),(1,5,7),(3,8,10)$
Les descentes sont $((4),(6),(9),(11,2,1),(5),(7,3),(8),(10)$
La liste ayant une unique montée est $(1,2, \cdots ,n-1, n)$ et celle ayant $n$ montées est $(n,n-1, \cdots 2,1)$
En effet, si une liste a une montée, on a $\forall i \in [|1,n-1|] \ a_{i+1} > a_i$ il n'y a qu'une seule façon de créer cette liste.
Si une liste a $n$ descentes, on a $\forall i \in [|1,n-1|] \ a_{i+1} < a_i$ et il n'y a qu'une façon de créer cette liste.
Ressaisis toi ca a rien à voir avec le niveau Ens pour l'instant
Exemple : $n=7$ et $k=3$
$l=(1, 2, 3 ,4 ,5 ,6, 7)$
$\sigma(l)=(2, 1 ,3 ,4 ,5 ,6 ,7)$
Exemple numéro 2 :
$n=8$ et $k=5$
$l=(1 ,2, 3, 4, 5, 6, 7, 8)$
$\sigma(l)=(4, 3, 2, 1, 5, 6, 7)$
Les exemples confirment bien mon intuition.
C'était la réponse à ce que je demandais il y a 21 H . Oui ça fait presque 2 jours pour avoir quelque chose qui approche. .
Combien y a-t-il de montées dans $\sigma(l)=(2,1,3,4,5,6,7)$ ? Est-ce cohérent avec votre choix de $k=3$ ?
Et dans l'autre exemple ? Il est très facile de réparer ce petit problème. Voyez-vous comment faire ?
Dans 4 jours, si tout va bien, on aura une réponse élégante à la question 2.
Intuition ?
Guigeek je vois je n'aurais pas du prendre une liste de nombres ordonnés.
Pour la question 2 j'ai trouvé une idée, la voici :
Soit $i \in [|1,n-1|]$ et soit $l=(a_1, \cdots a_i)$
Posons $l'=(a_1, \cdots a_i,a_{i+1})$
Si $a_{i+1} >a_i$ alors il y a une descente en plus et le nombre de montée de varie pas, ainsi $s_{i+1}=s_i +1$
Si $a_{i+1} < a_i$ alors il y a une montée en plus et le nombre de descente de varie pas, ainsi $s_{i+1}=s_i +1$
Dans tous les cas $\forall i \in [|1,n-1|] \ s_{i+1}=s_i +1$
$s_i$ est donc une suite arithmétique de raison $1$ et de premier terme $s_1 = 2$ donc :
$M(a)+S(a)=s_1 + (n-1) = 2+ n-1 $ enfin $\boxed{M(a)+D(a)= n+1}$
Vérifions la cohérence sur un exemple :
Soit la liste $(4,6,3,1,5,2)$ une liste de $S_6$ donc $n=6$
Il y a 4 montées : $(4),(2,6),(3),(1,5)$ et 3 descentes $(4,2),(6,3,1),(5)$
On a bien $M(a)+D(a)=3+4=7=6+1$
Tu peux corriger ce que tu as écrit pour la 1b? Donner un exemple pour n = 7 et k = 3 ?
Soit $n=7$ et $k=3 \in [|1,7|]$.
Soit la liste $(7,6,1,2,3,4,5)$
Les montées sont $(7),(6),(1,2,3,4,5,6)$
On a bien $M(a)=3$
Il y a une suite, j'espère que ce n'est pas trop dur.
Montrons que $\psi$ est bijective.
Injectivité : soit $(a,b) \in S_n$ tel que $\psi(a)=\psi(b)$ ce qui donne $(n+1-a_1, \cdots ,n+1-a_n)=(n+1-b_1, \cdots ,n+1-b_n)$ donc $\forall i \in [|,n|] \ n+1-a_i=n+1-b_i \implies a_i=b_i$ donc $a=b$ et $\psi$ est bien injective.
Surjectivité :
Soit $b=(b_1, \cdots b_n) \in S_n$ tel que $b=\psi(a)$.
On a alors $(n+1-a_1, \cdots ,n+1-a_n)=(b_1, \cdots b_n)$ d'où $\forall i \in [|1,n|] \ n+1-a_i=b_i \implies a_i = n+1-b_i$
On a trouvé $a \in S_n$ tel que $\psi(a)=b$ avec $a=(n+1-b_1, \cdots ,n+1-b_n)$
$\psi$ est surjective.
Je réfléchis à la 3)b) pour l'instant je ne vois pas comment faire.
Tfacon lexemple que tu donnes est faux
As-tu essayé de VOIR ce qui pouvait bien relier les montées et les descentes d'un élément et celles de son image par cette bijection ?
Mais il s'intéresse maintenant à l'Agrégation Agreg externe
Pour le topic ici, on peut s'attendre à ce qu'il fasse comme par exemple ici proba
Il a laissé tomber le sujet. Quel manque de respect envers celui (ou ceux) qui a (ont) fait l'effort de l'aider.
Je suis juste intéressé par les exercices qui sont tombés qui étaient sur ce l'algèbre linéaire car j'ai bossé ça tout le confinement.
Ok je vais tester sur un exemple.
Non je ne laisse tomber aucun sujet, je vais revenir dessus.
Soit $n=7$ et $k=3$ et $n+1=8$.
Soit la liste $(7,6,1,2,3,4,5)$
Les montées sont $(7),(6),(1,2,3,4,5,6)$
$\psi(a)=(8-7,8-6,8-1,8-2,8-3,8-4,8-5)=(1,2,7,6,5,4,3)$
Les montées sont $(1,2,7),(6),(5),(4),(3)$ il y en a $8-3=5$
Je vois que ça marche sur l'exemple mais je n'ai pas d'idées pour la démonstration théorique, je ne vois toujours pas comment utiliser la bijection.
Les descentes sont $(7,6,1),(2),(3),(4),(5)$ il y en a $5$
$\psi(a)=(1,2,7,6,5,4,3)$
Les descentes de $\psi(a)$ sont $(1),(2),(7,6,5,4,3)$ il y en a $8-5=3$
Comment pourrais-tu utiliser ce lien et la bijection pour répondre à la question ?
Le nombre de montées de $\phi(a)$ est égal au nombre de descentes de $a$.
En effet, si pour tout $i \in [|1,n-1|]$ $a_i < a_{i+1}$ alors $-a_i > - a_{i+1}$ et $n+1 - a_i > n+1 - a_{i+1}$
Je ne trouve pas comment utiliser la bijection.
C'est ce qui a fait naître l'idée même de bijection, puis la notion généralisée de cardinal lorsque l'ensemble est infini.
Mais quel rapport entre la bijection de $\psi$ de $S_n$ sur $S_n$ et les $E_n(k)$ $E_n(n+1-k)$ ?
Comme phi est bijective, il y a autant de a vérifiant Mn(a)=k que de a'=phi(a) vérifiant Mn(a') = n+1-k
Ca te donne que En(k) = En(n+1-k)
Pour la question 4a ça m'a l'air dur sans indication.
Je sais que le nombre de parties de $[|1,n|]$ est $2^n$ donc le nombre de parties non vides est $2^n-1$. Mais après je ne vois pas comment faire.