Bonjour et merci pour ce casse-tête

 Cliquez pour afficher

A priori les numérateurs et dénominateurs de  S(10) seront exponentiels mais je présume que le quotient sera de l'ordre de 10

Bonjour

Le problème risque de ne pas être simple . S'intéresser directement au nombre moyen de lancers n'est pas forcément l'approche la plus simple . En fait chaque agrafage équivaux à une réduction du nombre de cartes on part donc d'un jeu J(10) à 10 cartes et on évolue vers un jeu avec 10 cartes ou moins , avec une probabilité donnée .

Il y a T=10! répartitions des 10 cartes , cette répartition aboutie à :

J(1) avec une probabilité 1/T .
J(2) avec une probabilité 9/T .
J(3) avec une probabilité 36/T .
...

Séparer les blocs revient à placer des bâtons entre les éléments rangés en ordre croissant .  Le calcul n'est pas compliqué mais plutôt long .

Imod

En fait le calcul n'est pas aussi direct que ça car il faut séparer les blocs et les mélanger pour qu'ils ne fusionnent pas , il faut donc ajouter un dérangement . Je disais bien : pas simple .

Imod

J'ai essayé le problème par une autre voie

 Cliquez pour afficher

si on a prend l'exemple de 3 cartes seul 1,2,3 convient les  5 autres permutations exigent en moyenne:
132  4 coups
213   4 coups
231  2 coups
312  2 coups
321   4 coups
on a donc  16 coups sur 6  
J'ai fait un tableau jusqu'à S(8)

L'exercice fait penser aux automates ou aux chaînes de Markov , le calcul direct est un travail d'Hercule . Les données fournies nous annoncent un lien mystérieux entre S(10) et certains des éléments fournis . Personnellement , le nombre moyen d'étapes ne parle pas , c'est un renseignement secondaire et je ne connais pas grand chose aux probas . Un travail pour Flight , Verdurin , Jandri ...

Imod

Je cherche . . .

J'ai extrapolé jusqu'à S(10)

Si mon approche donnée  le 01/04  est correcte
Avec 10 cartes il faudrait  environ 15 coups pour avoir la chaine complète:

 Cliquez pour afficher

Tes résultats ne sont pas en accord avec les données fournies

Imod

Je pense avoir trouvé un moyen de calculer de proche en proche les différentes probabilités mais c'est vraiment lourd .

Il y a deux éléments à prendre en compte :

O(n) : nombre de façons d'ordonner n entiers consécutifs de façon à ce que le successeur de k ne soit jamais k+1 .
O(1) = O(2) = 1 et O(n+2) = (n+1).O(n+1) + n.O(n) .

: nombre de façons de séparer n+1 entiers consécutifs en k+1 blocs d'entiers consécutifs .

Après on construit récursivement l'arbre de probabilités et on a la réponse  . C'est très long  et on n'utilise pas les renseignements fournis .

Imod

Je n'ai pas utilisé les S(2 à 5 ) donnés car je ne retrouve pas leur logique ,en effet
Pour S(4) 47/13   je trouve   108/24

En fait l'encadré que tu donnes est exactement ce que j'expliquais dans mon message précédent :









Ensuite l'arbre de probabilité est simple car les 4 blocs peuvent rester 4 avec une probabilité 11/24 et un chemin qui s'allonge à l'infini ou alors descendre vers un nombre moindre dont la longueur moyenne est déjà connue .

On peut donc calculer S(10) de proche en proche .

Imod

Comme je sais que je suis rarement clair dans mes explications , j'illustre le cas avec n=4 pour montrer la récursivité :



Bien entendu , les deux dernière flèches ont pour longueur S(2) et S(3) .

Je pense que la mécanique du problème est démontée , après les calculs ne sont vraiment pas emballant  

Imod

Pour mémoire pour S(8)  je donne mes valeurs (je n'ai qu'extrapolé pour S(9)  et S(10) sans grande certitude).
J'ai:
1  8  63   385  1855  6489 14832 16687  sur   40320

Bonsoir,
en ce moment je n'arrive plus à penser.
J'ai fait une simulation et je trouve que s(10)10,53 avec un million de tirages.
Le code python :

from random import sample

def un_tour(nbCa):
    k  = nbCa 
    prec=-2
    per=sample(range(k),k)
    for suiv in per:
        if suiv == prec+1:
            k=k-1
        prec=suiv
    return k

def un_tri(depart):
    compte=0
    reste=un_tour(depart)
    while reste > 1 :
        compte+=1
        reste=un_tour(reste)
    return compte

def moyenne(taille, nb_ca):
    total=0
    for i in range(taille):
        total+=un_tri(nb_ca)
    return total/taille

[1, 1]
[1, 2, 3]
[1, 3, 9, 11]
[1, 4, 18, 44, 53]
[1, 5, 30, 110, 265, 309]
[1, 6, 45, 220, 795, 1854, 2119]
[1, 7, 63, 385, 1855, 6489, 14833, 16687]
[1, 8, 84, 616, 3710, 17304, 59332, 133496, 148329]
[1, 9, 108, 924, 6678, 38934, 177996, 600732, 1334961, 1468457]

Un inconvénient quand on vit dans un coin isolé  , plus de réseau pendant toute une journée et personne ne s'en tracasse

Je pense que la méthode que j'ai exposé fonctionne et les calculs ne sont pas compliqués mais un peu long . Il suffit de regarder le triangle de Pascal et les différentes valeurs de O ( c'est immédiat ) . Il faut ensuite faire un graphique comme celui que j'ai donné avec n=4 pour chacun des entiers jusqu'à 10 ( là encore rien de monstrueux ) . Ensuite on calcule la longueur moyenne du parcours et on passe à l'étape suivante . J'avais commencé le calcul pour n=4 mais je ne trouvais pas le résultat annoncé avant de comprendre  que je ne comptais pas les longueurs comme il fallait . Le choix de la modélisation est calamiteux : pourquoi ne pas considérer la position initiale comme un premier lancer ?

Imod

>verdurin,

Je vois que pour S(8) nous arrivons aux mêmes chiffres si ce n'est ton total 40319 au lieu de 40320 ...
Donc  on peut retenir ton S(10)  qui donnerait   une moyenne de 16.2*
obtenir la suite de 1 à 10  (58 786 562/3 628 800 )
On attend bilbo (et les autres).

* Il faut environ 16 lancers pour obtenir la suite dans l'ordre.

Excuses : ton total pour  8 est bien  40320

Un point d'accord avec toi , le manque de réactions de Bilbo aux diverses interventions frise l'impolitesse

Imod

Si on reprend mon schéma pour n=4 , il y a trois façon d'obtenir un paquet unique en passant par 1 , 2 ou 3 . Les probabilités sur chaque branche de l'arbre se calculent comme je l'ai déjà indiqué . A cause des boucles sur la position initiale la longueur moyenne du parcours s'obtient avec une sommation du type . Chacune des trois sommes est de la forme   , on peut donc la calculer .  On recommence à l'identique pour l'étape n=5 , c'est un travail de machine

Imod

Finalement j'ai fais le calcul, en flottants donc approximatif.
S(6)5,959 377 732
S(7)7,134 358 537
S(8)8,265 215 709
S(9)9,382 595 752
S(10)10,487 774 655

En fait le calcul exact est possible en général mais plutôt pénible à la main

En partant d'un jeu à n cartes , un regroupement se résume à une diminution du nombre de cartes . La première difficulté est de trouver le nombre de blocs correspondant à une répartition donnée . On peut remarquer dans un premier temps que réaliser k blocs parmi n cartes c'est placer k-1 séparateurs dans les n-1 espaces entre les cartes ordonnées . Ensuite il faut répartir les blocs sans que deux d'entre eux ne fusionnent . Le nombre de permutations des n cartes aboutissant à k blocs est donc , O(k) étant défini par la relation de récurrence O(1)=O(2)=1 et O(n+2)=(n+1)O(n+1)+nO(n) . Comme il y a n ! façons de répartir les cartes , il est facile de calculer la probabilité de trouver k blocs à l'issue du premier lancer . La suite se fait récursivement , on suppose donné le nombre moyen de lancer L(i) pour aboutir avec i=1,2,…, n-1 cartes et on construit l'arbre des probabilités qui est relativement simple avec sur chaque branche une sommation sur k d'une expression du style imposée par la boucle initiale et qu'il est facile de calculer .

Même si on voit apparaître régulièrement des L(i)+1 dans les sommations qui donne envie de sauter la première étape , il me semble bien plus reposant pour l'esprit de commencer par un lancer de cartes avant de les grouper .
Imod

Bonjour,

Je vois que ma première réponse (01/04 16h35) semble confirmée.
Ma dernière ne tient pas compte de ton arborescence  et est donc
plus grande (env 16.2)
J'ai du mal avec les boucles ,mais ce qui est certain c'est que chaque fois qu'on obtient un bloc on retombe sur une réponse précédente:
exemple    4,(123 ) ,5    correspond à  2,1,3.

Je ne suis fan de tableur ni de serpent constricteur et à la main les calculs deviennent très vite cause de maux de tête . Si on admet que Bilbo sait de quoi il parle même s'il parle peu , il y a une symétrie entre les données fournies et la question posée . Disons que l'on parte d'un bloc de 10 cartes et qu'on le casse aléatoirement en un ou plusieurs blocs ...
Imod    

J'ai fini par trouvé le schéma complet du calcul , j'essaie de rédiger quelque chose de compréhensible et je laisserai finir les courageux qui gèrent les robots bien mieux que moi  .
Imod

Je commence à l'étape 2 , il faut donc enlever 1 au résultat obtenu pour avoir la réponse à la question initiale . La probabilité de passer de n cartes à k cartes est donnée par :
La suite est définie par la récurrence : et .
Pour n donné , le jeu peut boucler sur n ou descendre à un nombre de cartes inférieur , on procède donc par récurrence et on peut construire l'arbre des probabilités qui comporte une boucle et n-1 branches . Si on regarde la branche k passant directement de n à k , la longueur moyenne du parcours est , avec . Il ne reste plus qu'à moyenner les différentes branches .
Imod

Avec les notations d'Imod ( et ses résultats ) on a



or
donc

en multipliant tout par on a



En faisant faire le calcul par un programme je trouve



Le programme

 Cliquez pour afficher

from fractions import Fraction
import math as m
def liste_s(n=10):
    # création de la liste Q, Q[k] est le nbr de permutations sans suite
    # de nombres consécutifs.
    O=[0,1,1] 
    for k in range(3,n+1):
        O.append((k-2)*O[-2]+(k-1)*O[-1])
    # liste des espérances : S.
    S=[0,0,Fraction(1)] # initialisation
    for k in range(3,n+1):
        f=m.factorial(k)
        denom=f-O[k]
        num=f-1+sum([m.comb(k-1,i-1)*O[i]*S[i] for i in range(2,k)])
        S.append(num/denom)
    return S

Merci Verdurin pour ta réponse , je commençais à croire que je parlais tout seul  

Je suppose que tu as vérifié ta formule pour les valeurs de S(i) avec i inférieur 10 . Ce serait vraiment sympa de les donner pour que je vérifie mes calculs effectués à la main .

Je crains que dans sa généralité le problème soit  complexe et la présentation initiale laisse vraiment interrogatif .  D'autre part , il semblerait que ...

Imod

Salut Imod.
S(6)=2 154 409/357 9816,018
S(7)=2 499 728 567/ 348 554 1677,172
S(8)=68 409 917 553 569/ 8 237 380 628 7118,305
Je m'excuse d'avoir été aussi peu réactif, j'étais vraiment fatigué.

En fait j'ai vérifié ton calcul de O(k) et de P_n(k) par un décompte en force brute (vérification en explorant toutes les permutations ).
C'est le tableau que je donnais ici mélange de cartes à jouer.

Sinon il me semble que S(n) croit un peu plus vite que n. Par exemple S(25)26,443.

Et j'ai regardé quelques sujets ouverts par bilbo.
Je ne pense pas qu'il interviendra encore. On ne peut pas dire que la politesse caractérise ses interventions.

Tes résultats sont en accord avec les miens

J'ai trop souvent tendance à monter en tension quand un problème m'intéresse mais je ne suis jamais agressif même si mes propos peuvent le laisser croire , chacun fait comme il le souhaite avec sa forme et son emploi du temps . Même si la formulation du problème proposé par Bilbo est un peu trop verbeuse , le problème est intéressant . Après on balance des données et une question qu'on est sensé mettre en relation mais rien ne vient : quel est l'objectif de l'exercice ???

En bref , Dpi et toi avez accepté le jeu et proposé des réponses sans la moindre réaction de l'auteur , ne serait-ce que pour recadrer le débat .

Le résultat final que tu as obtenu est tout de même relativement simple vu la complexité de la question  

Imod

Salut Imod.
J'ai aussi trouvé le problème intéressant. Ce pourquoi j'ai un peu cherché.
Pour le résultat je n'ai presque rien fait d'autre qu'exploiter tes résultats. Et faire une moulinette très simple. Que je n'ai fait que parce que tes messages ont réussi à me motiver.

Je te remercie, ainsi que dpi, de m'avoir permis de surmonter la paresse intellectuelle qui me gagne.

Nous avons tous des coups de mou et le clown qui dirige la première puissance du monde nous met vraiment le moral dans les chaussettes . Je sais par expérience qu'un joli problème à résoudre peut vite relancer la machine ( je ne parle évidemment pas de ceux posés par l'autre zèbre ).

Imod