Perles, colliers et congruences — Les-mathematiques.net The most powerful custom community solution in the world

Perles, colliers et congruences

CidrolinCidrolin
Modifié (April 2022) dans Combinatoire et Graphes
Bonjour
Règles
On fabrique un collier de longueur $n$ avec des perles de deux types. Les perles de type $A$ sont de diamètre $1$, celles de type $B$ ont $5$ pour diamètre. Deux colliers qui se déduisent l'un de l'autre par une rotation (ou une symétrie) sont considérés comme distincts. On note $u_n$ le nombre de colliers de longueur $n$.

Exemple $n=11$
Il y a un collier sans perle $B$.
Il y a onze colliers avec une seule perle $B$ Elle occupe les places $1$ à $5$, ou de $2$ à $6$ ou de ....$11$ à $4$.
Il y a onze colliers avec deux  perles $B$. On choisit la place de la perle $A$.
Conclusion $u_{11}=23$.

Question
Montrez que si  $p>5$ est premier alors $u_p \equiv 1 \pmod{p}$.

Réponses

  • jandrijandri
    Je pense avoir démontré plus généralement que si les perles de type $A$ sont de diamètre $1$ et celles de type $B$ sont de diamètre $d$ avec $d>2$ alors pour tout nombre premier $p$ tel que $p>d$ le nombre de colliers de longueur $p$ est congru à $1$ modulo $p$.
  • CidrolinCidrolin
    Modifié (April 2022)
    Bravo jandri. On peut même prendre $d=2$, dans ce cas $u_n=L_n$ (nombre de Lucas).
    On retrouve $L_p\equiv 1 \pmod{p}$, pour tout premier.
  • jandrijandri
    Merci pour ce lien avec les nombres de Lucas. J'ai écrit $d>2$ mais je voulais écrire $d\geqslant2$.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!