Divisions dans les successions

Cidrolin

Bonjour,

Combien y a-t-il de nombres de vingt chiffres (non nuls) dont l'écriture décimale est

$\overline {a_1a_2\dots a_{20}}$ et tels que chacun des nombres $\,\overline{a_1a_2}\,$, $\,\overline{a_2a_3}\,$, $\,\overline{a_3a_4}\,$, . . .,$\,\overline{a_{19}a_{20}}$

soit divisible par $13$, ou $17$, ou $23$ ou $37$ ?

soland

Souvenir, souvenir...

Cidrolin

Il y a confusion Soland. Je pose juste un problème de dénombrement.

soland

Ma réponse est

Il y a $9\,437\,184$ nombres de 20 chiffres tels que...

Cidrolin

Je ne trouve pas $9\times2^{20}$ mais la moitié.

Math Coss

sage: L = [k*l for k in [13,17,23,37] for l in range(1,10) if k*l<100]
sage: def arete(m): return m//10, m%10
sage: D = DiGraph(map(arete,L))
sage: A = D.adjacency_matrix()
sage: print A
[0 0 1 0 0 0 1 0 0]
[0 0 1 0 0 1 0 0 0]
[0 0 0 1 0 0 1 0 1]
[0 0 0 0 0 1 0 0 0]
[1 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 1 1]
[0 0 0 1 0 0 0 1 0]
[0 0 0 0 1 0 0 0 0]
[1 1 0 0 0 0 0 0 0]
sage: add(add(A^20))
9437184

Cidrolin

Je considère les $18$ nombres : $13;26;39;52;65;78;91;17;34;51;68;85;23;46;69;92;37;74$.

On peut en disposer pour construire $9$ couples :

$(91,51);(52,92);(13,23);(34,74);(65,85);(26,46);(37,17);(78,68);(39,69)$

Pour le dernier chiffre $a_{20}$ on a $9$ choix : $1,2,...,8,9$,

pour $a_{19}$ on a alors $2$ choix, puis $2$ choix pour $a_{18}$, ainsi de suite . . .

D'où ma réponse $9\times 2^{19}$.

Math Coss

Exact ! Soland et moi nous sommes trompés d'un indice ! Un nombre à $20$ chiffres, c'est un chemin à $19$ arêtes et pas $20$, bien sûr. Encore l'histoire du poteau dans l'œil du voisin et du fil prêt à se rompre. Rectificatif...

sage: add(add(A))
18
sage: add(add(A^19))
4718592