Équilibrage

lesmathspointclaires
lesmathspointclaires
dans Combinatoire et Graphes
Soit $ n $ et $k$ deux entiers naturels et $u= (u_1,\ldots,u_n) $ une liste d'entiers strictement positifs dont la somme des termes est $ kn$.
$M(u)$ est une matrice d'entrées $0,1$ telle que pour tout $ j,i<n+1$, $M(u)_{i,j}=1$ ssi le plus petit entier positif égal à $j-i \pmod n$ est au plus $u_i$.
(On a donc en particulier $(1,1,\ldots,1)M(u)=u$).
Et on définit $f(u):=(1,1,\ldots,1).M(u)^t$
Je souhaite montrer que $f^r(u)=(k,k,\ldots,k)$ pour un $r$ assez grand.


Imaginer un tore quadrillé n case par n cases, pour chaque $i$ on commence sur la case i,i du tore et on place $u_i$ uns consécutivement au dessus de la diagonale. Ensuite on "regrouppe" les 1 des lignes et on applique le traitement dual, on a fait agir $ f$une fois....

Réponses

  • lesmathspointclaires
    lesmathspointclaires
    Je pense qu'en généralisant un poil on a le resultat de façon evidente par recurrence sur $n$

    pour tout $k$ entier plus petit que $n$ et tout $u$ comme dans l'hypothèse, on définit $M=M_k(u)$ comme suit:
    $M_{i,j}=1$ ssi le reste modulo $n$ de $j-i-k$ est au plus $u_i$
    On definit $f_k:=(1,1,...,1).M^t$ et on se demande si $f_k^r$ est constante pour tout k et pour tout r assez grand

    On voit qu on se ramène, si c'est possible au cas où on enleve un 1 à toutes les termes de u, si ce n'est pas possible c'est'une colonne est identiquement nulle, on applique alors la transformation pour n'obtenir que des colonne non id. nulles et ainsi de suite jusqu'à 0 partout


    DIT UN POIL AUTREMENT ET POUR ALLER VITE : LE PB EST INVARIANT PAR TRQNSLATION (on s en fout du point de depart) ET TOUT TRANSLATER D UNE UNITÉ EQUIVAUT A ENLEVER SANS AFFECTER LE RESULTAT, UNE DIAGONALE DE 1
  • lesmathspointclaires
    lesmathspointclaires
    On peut sans doute generaliser ceci à une fonction de [0,1] dans lui même au bout d'un nombre eventuellement transfinies d'étape on obtient une flnction constante, cet ordinal serait le degré de platitude de la fonction...


    On pourrait utiliser ça pour par exemple harmoniser les tables d'un tournois de poker en ligne, et peut etre que le degres de platitude a des vertus interssantes d un point de vue mathematique.


    Une autre chose amusante (dans le cas fini mais peut etre que ça marche aussi en généralusant) est qu'il semble que si la somme des des terme d'un n-upplé u, d'entiers positifs n(n-1)/2, alors f(u) est la liste des degrès sortant des sommets d'un graphe orienté complet (à verifier)
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

3 Invités