L'as en tête

[Imod]

Bonsoir :zen:

Encore une petite énigme très simple , tant pis pour les couche-tôt

On dispose d'un paquet de cartes numérotées de 1 à et consciencieusement mélangées .
On retourne la première carte sur laquelle on peut lire une valeur , on inverse alors l'ordre des premières cartes .
On retourne la première carte sur laquelle on peut lire la valeur , on inverse alors l'ordre des premières cartes ...

Montrer qu'à un moment donné il n'y aura plus de cartes à inverser .

Imod

[Lemniscate]

Bonjour,

Je suis un lève-tôt aujourd'hui !

Euh j'ai pas tout compris. Que se passe-t-il si m=1 ?
On ne peut plus rien mélanger. C'est cela le point auquel on "veut" aboutir ?

Je suppose que oui.

Quand tu dis "inverser" l'ordre des m premières cartes, c'est l'odre de gauche à droite ? (en supposant que la "première" carte soir celle la plus à gauche). Et "inverser" veut-il dire mettre la plus à droite, à gauche et la plus à gauche, à droite ? (et même méthode pour les cartes intermédiaires...)

Je suppose aussi que oui.

Je pense qu'on devrait noter :

,,..., les positions que prennent les cartes de la gauche vers la droite.
Et ,,...,,... le numéro de la carte (entre et donc) tirée lors du k - ième "tirage".

A ce moment là :

On veut montrer que est stationnaire en 1 (constante égale à 1 à partir d'un certain rang).

lors du k-ième tirage, on "inverse" les premières cartes. Donc la carte à la position (où compris entre et ) se retrouve en . On tire alors la carte en position , ce qui constitue le (k+1)-ième tirage...

Voila, je pense avoir posé de bonnes notations, je vais réfléchir maintenant !

[Lemniscate]

Je mets juste un exemple pour voir si j'ai compris :

Si n=6.

Au début : [2 3 5 1 4 6]
k=1 :
et [2 3 5 1 4 6] devient [3 2 5 1 4 6]

k=2 :
et [3 2 5 1 4 6] devient [5 2 3 1 4 6]

k=3 :
et [5 2 3 1 4 6] devient [4 1 3 2 5 6]

k=4 :
et [4 1 3 2 5 6] devient [2 3 1 4 5 6]

k=5 :
et [2 3 1 4 5 6] devient [3 2 1 4 5 6]

k=6 :
et [3 2 1 4 5 6] devient [1 2 3 4 5 6]
, donc 7 est le rang à partir duquel on a le résultat demandé.

J'ai bon ?

Et je rêve ou bien ? (à démontrer une fois qu'on a démontré que existe bel et bien (but du problème d'ailleurs) ).

[Imod]

Juste un mot pour dire à Lemniscate qu'il a bien compris le problème :we:

Imod

[ThSQ]

Pas encore bien réveillé mais ça se tue sans effort par une bonne vieille récurrence, ou bien ?

Je prends mon litre de café et je reviens


Suite : donner le nombre max (ou au moins un (bon ...) majorant) du nombre de permutations nécessaires pour terminer

[nodgim]

Bonjour à tous.
Oui, il y a des matinaux ce dimanche! :ptdr:
En fait, il est évident que tant qu'on n'est pas arrivé à 1, il faudra recommencer. Et la question est de donc de savoir si on peut tourner en boucle sans jamais tomber sur 1....

[ffpower]

oula comme j avais compris completement entre chose lol.En gros,je croyais que chaque carte était soit face visible,soit face cachée,et qu a chaque étape,on regardais le nombre k sur la premiere carte visible,et on retourne les k premieres cartes(cad face cachée devient face visible et face visible devient face),et qu il fallait montrer qu au bout d un moment toutes les cartes seront face cachée.Bref,j étais fatigué je crois,je retourne donc sur le vrai énoncé^^

[ThSQ]

Donc par récurrence :

n=1,2 ça marche !

Ou bien 'n' apparait en première place à un moment : on est ramené 1..n-1
Si 'n' n'apparait jamais en première place ça veut dire qu'on travaille sur les n-1 premières cardes et que le 'n' ne sert à rien.

[Imod]

Oui la récurrence marche , on peut aussi se dire que la plus grande carte qui apparaît au sommet du tas ne peut y apparaître qu'une seule fois ...

Imod

[nodgim]

Il y a aussi un bel invariant dans l'histoire, et une autre valeur qui est décroissante à chaque opération :id:

[ThSQ]

Extensions de mon cru :
- Mq le nombre maximum de tours pour terminer est (ça j'ai fait), F = Fibonacci.
- A-t-on ? (pas fait mais ça semble douteux)

[nodgim]

Bon je donne ma solution.
On donne un rang de classement de 1 à N de la gauche vers la droite.
On attribue la valeur 2^k au rang k. Cette valeur est validée si la carte k est à son rang k. A l'issue d'une permutation, on valide donc une nouvelle valeur 2^j au rang j, et on efface toutes les valeurs validées antérieurement qui se trouvent à la droite de j.
La somme des valeurs validées est strictement croissante, le total étant 2^(N+1)-1. On n'est pas obligé de s'arrêter quand on a obtenu le 1, on continue pour obtenir le 2, le 3 et ainsi de suite jusqu'à N.

Voila j'espère que c'est assez clair.

[nodgim]

Extensions de mon cru :
- Mq le nombre maximum de tours pour terminer est (ça j'ai fait), F = Fibonacci.
- A-t-on ? (pas fait mais ça semble douteux)

Ta première proposition semble bonne, quoique je sois infoutu de la démontrer. Peux tu nous faire part de ta démo ?
Pour la 2ème question, c'est quoi O(n^alpha) ?

[ThSQ]

c'est quoi O(n^alpha) ?

Ben la question est de savoir si c'est ~polynomial ou non. Fibonacci c'est exponentiel et trop gros.

Pour le 1er point, je laisse chercher un peu (des fois que ça intéresse kekun, on peut rêver )

Indice blanké : regarder le nombre de valeurs distinctes prises par la première carte

[nodgim]

Je peux garantir que pour 2c cartes, il faudra m=5(c-1) manipulations à partir de c=3. Par ailleurs, une autre méthode donne un nombre de manipulations < 3, (mais sans la certitude absolue du maximum) avec une tendance à la baisse quand le nombre de cartes augmente.
La limite serait elle m=c*e ?