Montées d'une permutation — Les-mathematiques.net The most powerful custom community solution in the world

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 ?104872
«1

Réponses

  • Non c'est faux
  • Relis l'énoncé. Essaye de comprendre la mécanique.
    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.
  • Lourran, j'ai passé au moins 30 minutes à essayer de comprendre, je trouve la définition compliquée.

    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)$
  • Regarde l'exemple donné dans l'énoncé de l'exercice.

    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.
  • Ok merci. Je n'ai pas compris à quoi servent les séparateurs mais je suis le modèle.

    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)$
  • Mais pourquoi (7,5) ???? Et dans les descentes t'as pas terminé??
  • C'est désespérant.
    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.
  • Ok je corrige ça je n'avais pas compris que tous les chiffres apparaissaient.

    $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)$
  • Encore faux, corrige le vite de toi même avant qu'on se dise que tu n'as encore rien compris.
  • Je ne sais pas, de toute façon ce n'est même pas la question du sujet.

    $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 ?
  • ce n'est même pas la question du sujet.

    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.
  • Ma solution est elle juste ?
  • Bonjour
    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?
  • J'ai donné mes justifications en exhibant les listes
  • Lourran je ne comprends pas votre remarque. La suite de l'exercice :105000
    2.png 456.5K
  • Je pense que j'ai pas vraiment compris la définition compliquée d'une descente ou d'une montée. Je ne vois pas ça représente quoi et à quoi ça sert.
  • Quand tu dis $E_n(1)=1$, il faut montrer qu'il n'existe qu'une seule $n$ liste de $1,n$ ayant une seule montée, existence et unicité. Tu montres l'existence mais pas l'unicité. T'es toujours pas au point sur la logique de base, on dirait. Tu montres que $(1,..,n) \in \{a \in S_n,\ M(a)=1\}$ mais pas l'inclusion réciproque, tu comprends ? Du coup, ta solution n'est pas une solution mais un résultat donc dans une copie de concours, ta réponse ne vaut rien. Ce n'est pas une solution, ce n'est pas un raisonnement.

    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).
  • Je te propose une expérience. Tu vas dans un collège. Tu demandes au 1er élève qui passe par là, et tu lui montres l'exercice. Tu lui dis de chercher, et tu lui promets 20€ s'il trouve la solution, et tu le recontactes le lendemain. Pour 20€, il va chercher, et le lendemain, il t'expliquera le système des montées et descentes.
  • Lourran non un élève de collège il ne comprendra jamais la définition donnée avec les accolades qui n'est pas claire.

    L'inclusion réciproque m'a l'air trop dure.
  • Oshine : tu exagères !! Peut-être que l'élève de collège moyen ne comprendra pas la définition avec l'accolade (encore que je pense que certains sont tout-fait capables de le faire) mais, il est quasi certain qu'il comprendra l'exemple !

    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 !
  • Tiens... Par une coïncidence amusante, le sujet d'ENS d'hier traite (un petit peu) d'un sujet similaire :
    http://www.les-mathematiques.net/phorum/read.php?3,2037242,2039962#msg-2039962
  • Tout à fait Bisam.
    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.
  • C'est trop dur pour moi les sujets ENS. Le maximum que je peux comprendre c'est les épreuves de Mines Ponts et encore c'est super dur pour moi.

    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)$
  • Bravo !!!!!!

    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)
  • Merci.

    $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)$
  • On a $E_n(1)=E_n(n)=1$

    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.
  • 2 jours pour ça!!!!!

    Ressaisis toi ca a rien à voir avec le niveau Ens pour l'instant
  • Pour la question 2, voici ma proposition. On range les $k-1$ premiers termes dans l'ordre strictement décroissant à l'aide d'une permutation et on garde fixé les $n-k+1$ éléments restants.

    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.
  • Oshine a écrit:

    > J'ai donné mes justifications en exhibant les
    > listes

    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. .
  • OShine, c'est une bonne idée, cependant il faut prendre le temps de vérifier vos résultats avant de les poster.
    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 ?
  • On sait maintenant quelle est la mécanique derrière ces montées et descentes.
    Dans 4 jours, si tout va bien, on aura une réponse élégante à la question 2.
    Les exemples confirment bien mon intuition.
    Intuition ?
  • Depuis que j'ai arrêté de me concentrer sur la formule j'ai mieux compris.

    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$
  • Bien joué pour la 2.

    Tu peux corriger ce que tu as écrit pour la 1b? Donner un exemple pour n = 7 et k = 3 ?
  • Ok merci.

    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.105080
    1.png 281.4K
  • Non tu peux corriger ce que tu as fait à la 1b? Tu vois pas que ta suite est fausse? Y a juste un truc à corriger, corrige le

    Tfacon lexemple que tu donnes est faux
  • Oui j'ai fait une erreur je viens de corriger.
  • Je sèche un peu pour la 3)b) je ne vois pas comment utiliser la bijection donnée.
  • Encore une fois, as-tu essayé de VOIR ce que faisait la bijection sur un ou plusieurs exemples ?
    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 ?
  • Pour lui donner un coup de pouce, on a envie de dire à @Oshine que la bijection $\psi$ transforme une montée en descente.

    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.
  • Non je ne m'intéresse pas à l'agrégation externe.
    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.
  • Ok je me lance.

    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.
  • Détermine les montées ET les descentes pour ta liste $a$ ET son image, dans ton exemple.
  • Pourquoi les descentes alors qu'on veut juste calculer $E_n$ ?

    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$
  • Toujours bloqué à la 3)b)
  • Ne vois-tu pas un lien entre les montées de $a$ et les descentes de $\psi(a)$ ? Entre les descentes de $a$ et les montées de $\psi(a)$ ?
    Comment pourrais-tu utiliser ce lien et la bijection pour répondre à la question ?
  • Le nombre de descentes de $\phi(a)$ est égal au nombre de montées de $a$.
    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.
  • Si deux ensembles sont en bijection, ils ont le même cardinal.
    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.
  • Oui ça je le sais. J'ai étudié le cours sur les ensembles et applications.

    Mais quel rapport entre la bijection de $\psi$ de $S_n$ sur $S_n$ et les $E_n(k)$ $E_n(n+1-k)$ ?
  • Mn(a) = k si et seulement si Mn(phi(a)) = 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)
  • Merci j'ai compris. J'aurais revenir à la définition de l'ensemble $E_n$ pour mieux voir les choses.

    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.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!